Sorry, its not linear search in my previous reply. Its a type of search where u randomly ask a person each time, with possibility of asking the same person again.
On 16 May 2011 13:58, Bharath Raghavendran <[email protected]> wrote: > You are completely right in saying that the expected number of hits to > get exactly 1 element in place is 2. Note that here, you are assuming > that if all 3 go into place, thats as good as none are in place. > > In probability, expected value is tied with definition of random > variable. Based on what you define your random variable as, your > expected value (of the random variable) will change. > For example, > If X is the random variable that says number of hits to get exactly > one element in place and other 2 in wrong places, then E(X) = 2. > If X is the random variable that says number of hits to get atleast > one element in place, then E(X) = 1.5 > If X is the random variable that says number of elements that go in > place in one hit, then E(X) = 1 > > For the third case, you can imagine a class of 6 people who are given > a test. Among the 6 people, 1 scores 3 marks, 3 score 1 mark, 2 score > 0 marks. Then, what would be the average marks in the class? If you > say 1, are you losing the significance of people who scored 0? > > Similarly, if you are doing a linear search among the 6 people to find > someone who scored 1 mark, what would be the expected number of people > you ask their marks? Wouldn't it be 2? > > On 16 May 2011 13:08, Eagle <[email protected]> wrote: >> @Bharath >> >>> Another way to look at this is, if you are uncomfortable multiplying >>> with a 0, >> No, I am not uncomfortable about about mathematical process of >> multiplying by zero; >> I am uncomfortable with loosing the significance of effect of some >> cases. >> If somebody asks me, how many hits are required to bring one element/ >> number >> in its correct position for N=3, sample space being >> 1 2 3 >> 1 3 2 >> 2 1 3 >> 2 3 1 >> 3 1 2 >> 3 2 1 >> I would like to answer that on an average 2 hits are required (3 out >> of 6 cases/events have >> one number at its correct position; probability 1/2). >> This is where I become uncomfortable. >> >> Eagle >> >> >> On May 16, 1:19 am, Bharath Raghavendran <[email protected]> wrote: >>> 1. >>> You aren't omitting the case where none are sorted. Its just that when >>> none are sorted, the value of the random variable is 0. >>> >>> For example, if you are finding average of 0 and 10, you do (1/2)*0 + >>> (1/2)*10. Even though you are multiplying by 0, you arent omitting it, >>> and getting the right answer. >>> If probability for 0 is 3/4 and probability for 10 is 1/4, you find >>> the average (or expected value) as (3/4)*0 + (1/4)*10 = 2.5. See that >>> even though the value of random variable is 0, it affects the final >>> output for expected value. >>> If probability of 0 is ~1 and probability of 10 is ~0, you will have >>> expected value as 0. >>> >>> Another way to look at this is, if you are uncomfortable multiplying >>> with a 0, You can find E(1+X) instead of E(X) and then subtract 1. >>> For n=3, E(1+X) will be (1/6)*4 + (1/2)*2 + (1/3)*1 = 2. >>> So, E(X) = 2-1 = 1. >>> >>> 2. >>> >>> > There, we did not say, that in one hit one number is expected to >>> > come at appropriate position, and because the remaining number does >>> > not require any hit (it gets automatically sorted) >>> >>> This statement is wrong. If we say 1 element has come in the >>> appropriate place, we mean that exactly 1 element has come in its >>> place and rest of the elements are not in the appropriate place. Note >>> that this outcome is not possible for n=2, because either 0 elements >>> can fall in place or 2 elements can fall in place. No other outcome is >>> possible. However, from calculations, you will see that the expected >>> value for number of elements to fall in place is still 1 (by >>> calculations). For n=2, you can calculate expected number of hits as >>> E(n=2) = (1/2)*(1 + expected number of hits when none of them fell in >>> place) + (1/2)*(1 + expected number of hits when both of them fell in >>> place) >>> = (1/2)*(1 + E(n=2)) + (1/2)*(1+0) >>> = 1/2 * E(n=2) + 1 >>> So, E(n=2) = 2. >>> >>> On 16 May 2011 10:24, Eagle <[email protected]> wrote: >>> >>> > Thanks Pedro, Bharath, & others; finally I have fully >>> > understood how the calculation of expected number of numbers that land >>> > in the correct position after X hits, is done. Comments by John & Paul >>> > Smith also helped in filling the communication gaps, Thanks! I think, >>> > I have also understood the logic of your method. It goes something >>> > like this (correct me, if I am wrong)- >>> > The expected value of the numbers that fall in correct position after >>> > a hit is 1. If we have problem of sorting, say, 5 numbers, i.e., N=5, >>> > then after first hit, one of the five numbers gets sorted; Goro now >>> > puts a finger on it, and the problem is reduced to N=4. By similar >>> > process, in second hit we come to N=3, in third hit we come to N=2. >>> > For N=2, the solution is already given in the problem statement >>> > itself, and that is 2 hits. So, total 5 hits are required for sorting >>> > N=5 numbers. >>> >>> > For the sake of science, please ponder over the following >>> > points- >>> >>> > 1) Is 'expected value' which is average (albeit weighted) value, >>> > appropriate in the present problem? The way we are calculating this >>> > value, it so happens that the effect of cases where none of the >>> > numbers is sorted, becomes zero. >>> > For N=3, E(sorted numbers) = (1/6)*3 + (1/2)*1 + (1/3)*0 = 1 >>> > For N=4, E(sorted numbers) = (1/24)*4 + (1/4)*2 + (1/3)*1 + (9/24)*0 = >>> > 1 >>> > We are ignoring the significance of 2 out of 6 events of the sample >>> > space for N=3, and 9 out of 24 for N=4, because of the way we are >>> > doing calculation. I have not checked, but I think this ratio must be >>> > increasing for N=5, 6, etc. The omission of these cases makes me >>> > uncomfortable. Can we afford to take such a risk? >>> >>> > 2) We have not omitted the significance of unsorted numbers case for >>> > N=2. There, we did not say, that in one hit one number is expected to >>> > come at appropriate position, and because the remaining number does >>> > not require any hit (it gets automatically sorted), the expected >>> > number of hits (for N=2) is one. We appropriately took the number of >>> > required hits for N=2 as two. >>> >>> > Thanking you in advance for your learned and thoughtful >>> > comments, >>> >>> > Eagle >>> >>> > On May 14, 11:18 pm, Pedro Osório <[email protected]> wrote: >>> >> I am not offended at all. I'm however starting to get a bit annoyed that >>> >> you >>> >> don't pay attention to what I write. >>> >>> >> I have explicitly defined X in that post as "elements that go into the >>> >> right >>> >> position after one hit for the array [2 1]" (because that's what you were >>> >> asking about in your last question " the expected number of elements that >>> >> are put into position by the first hit is exactly 1") >>> >>> >> Meanwhile, whenever I wrote E[n=whatever], I was talking about the >>> >> expected >>> >> number of hits required to sort an array that has "whatever" elements >>> >> out of >>> >> position. >>> >>> >> E[n=2] - expected number of *hits* required to sort an array that has 2 >>> >> elements out of place >>> >> X - expected number of *elements* that go into the right position >>> >> after one hit for the array [2 1] >>> >>> >> As you can see, the random variables whose expected values we are >>> >> computing, >>> >> don't even refer to the same kind of object. I don't see how you could >>> >> confuse them. Please pay more attention before complaining. >>> >>> > -- >>> > You received this message because you are subscribed to the Google Groups >>> > "google-codejam" group. >>> > To post to this group, send email to [email protected]. >>> > To unsubscribe from this group, send email to >>> > [email protected]. >>> > For more options, visit this group >>> > athttp://groups.google.com/group/google-code?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
