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.
