Where did you read "probability of getting at least one number in its correct position is becoming 1.0"? It says "expected number of elements that end up in the correct position is N * 1/N = 1"..
ulzha On May 9, 9:38 am, Eagle <[email protected]> wrote: > I fail to understand the logic of the proof given in the 'contest > analysis'. > For the three unsorted numbers 3 1 2, the sample set of arrangements > is- > > 1 2 3 > 1 3 2 > 2 1 3 > 2 3 1 - Not even one in correct position > 3 1 2 - Not even one in correct position > 3 2 1 > The probability of at least one number being at its sorted position is > 2/3, while the probability of not getting even one number in its > correct position is 1/3. So, how come, all of a sudden, the > probability of getting at least one number in its correct position is > becoming 1.0? If at all, average hits are to be calculated (being > average, it can be non-integer real number), then it would be > reciprocal of 2/3, that is, 3/2, that is 1.5 and not 1. > Also, while calculating total probability of dependent events, you > MULTIPLY the individual probabilities, and NOT add them. > In the present example, the P(exactly one element in correct position) > is 3/6 = 1/2. After that event is realized, Goro will hold that > number, and only two unsorted numbers are there. This time, the > P(correct sorting) is 1/2. So, the combined probability is 1/2 x 1/2 = > 1/4. Thus, total 4 hits would be required on average. > (If my analysis is correct, I will have the life-time joy of catching > Google employees making logical error! Ha ha ha!!) > > Eagle > > On May 8, 7:41 pm, rnld <[email protected]> wrote: > > > > > Yes, that seems correct. > > > Let's say M is the number of unsorted elements in the array of length > > N. > > > If you randomly permute the M unsorted elements once, the expected > > number of elements that fall into its right place equals exactly 1. > > Hence, on average you'll have to do this M times (after each > > permutation you freeze everything that's in place, and repeat until > > number of unsorted elements equals zero), which makes that the > > expected number of hits is M. > > > Consider the following examples. > > > A = [2 3 1] > > --> all 3 not in their right place > > --> random shuffle gives one of the following permutations: > > > 3 2 1 -> 1 element in correct place (the "2") > > 3 1 2 -> 0 element in correct place > > 2 3 1 -> 0 element in correct place > > 2 1 3 -> 1 element in correct place > > 1 2 3 -> 3 elements in correct place > > 1 3 2 -> 1 element in correct place > > > All are equally likely, so the expected number of elements in it's > > correct place equals 1/6 * (1+0+0+1+3+1) = 1. I'm not sure how to > > proof this, but it always gives 1, no matter how many elements you > > permute. For 2 it's easy to see as well: > > > 1 2 -> 2 elements in right place > > 2 1 -> 0 elements in right place > > > 1/2 * (2+0) = 1. > > > 1 -> 1 elements in right place > > > 1 * 1 = 1. > > > Hope his helped. -- 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.
