@Eagle Have you even bothered to read what I wrote about the same case, just before you?...
On May 9, 7: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.
