This problem is a typical application of: http://en.wikipedia.org/wiki/Optional_stopping_theorem. Reading the "Applications" section may ease your concerns about using expectations. In particular, look at the third bullet point.
On May 15, 11:54 pm, 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 at http://groups.google.com/group/google-code?hl=en.
