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 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.
