Let me try:
For the two unsorted numbers 2 1, the posible arranglements are:
1 2 -> 1/2 * 1 hit (solved)
2 1 -> 1/2 * 1 hit
1 2 -> 1/4 * 2 hits (solved)
2 1 -> 1/4 * 2 hits
1 2 -> 1/8 * 3 hits (solved)
2 1 -> 1/8 * 3 hits
1 2 -> 1/16 * 4 hits (solved)
2 1 -> 1/16 * 4 hits
...
Now, the chances of getting the set sorted are:
1/2 of getting it in 1 hit
1/4 of getting it in 2 hit
1/8 of getting it in 3 hit
1/16 of getting it in 4 hit
...
We must calculate the average of that.
For the first iteration (2 cases) it's straightforward:
average = (1 hit * 1 case) / 2 case
average = (1 hit) * (1 case / 2 case)
average = (1 hit) * 1/2
average = 1/2 hits
But you have only took into account 1/2 of the cases.
For the second iteration (4 cases):
average= (1 hit * 2 case + 2 hits * 1 case) / 4 case
average= (1 hit * 2 case) / 4 case + (2 hits * 1 case) / 4 case
average= (1 hit) * (2 case / 4 case) + (2 hits) * (1 case / 4 case)
average= (1 hit) * 2/4 + (2 hits) * 1/4
average= (1 hit) * 1/2 + (2 hits) * 1/4
average= 1/2 hits + 2/4 hits
average= 1/2 hits + 1/2 hits
average= 1 hit
But you have only took into account 3/4 of the cases.
Also note, it's the previous value + 1/2 hits.
For the third iteration (8 cases):
average= (1 hit * 4 case + 2 hits * 2 case + 3 hits * 1 case) / 8 case
average= (1 hit * 4 case) / 8 case + (2 hits * 2 case) / 8 case + (3 hits *
1 case) / 8 case
average= (1 hit) * (4 case / 8 case) + (2 hits) * (2 case / 8 case) + (3
hits) * (1 case / 8 case)
average= (1 hit) * (4/8) + (2 hits) * (2/8) + (3 hits) * (1/8)
average= (1 hit) * 1/2 + (2 hits) * 1/4 + (3 hits) * 1/8
average= 1 hit + 1/8 hits
I hope, you can notice the pattern, you have:
first iteration -> average = 1/2 hits
second iteration -> average = 1/2 hits + 1/4 hits
third iteration -> average = 1/2 hits + 1/4 hits + 1/8 hits
fourth iteration -> average = 1/2 hits + 1/4 hits + 1/8 hits + 1/16 hits
and so on...
That's the same of doing the pondered sum of the hits by the probability of
solving it at that number of hits. This also applies for the 3 elements
scenario. [This is becase the number of cases over the total of cases is
also the probability, and to calculate the average we must multiply the
value by the number of cases it appears, then sum that up and divide over
the total of cases].
So, the average is of the form: sum x/2^x from x = 1 to n where n is the
number of iterations.
This serie is known to have a value of 2 when n = infinite.
So the average for two elements is 2 hits.
For the three unsorted numbers 3 1 2, the posible arrangements are:
1 2 3 -> 1/6 * 1 hit (solved)
1 3 2 -> 1/6 * 1 hit (1 item in the right spot)
We take this case a 2 elements scenario as Goro holds the 1
... so it will take 2 more hits on average to solve.
1/6 * 3 hits (solved)
2 1 3 -> 1/6 * 1 hit (1 item in the right spot)
We take this case a 2 elements scenario as Goro holds the 3
... so it will take 2 more hits on average to solve.
1/6 * 3 hits (solved)
3 2 1 -> 1/6 * 1 hit (1 item in the right spot)
We take this case a 2 elements scenario as Goro holds the 2
... so it will take 2 more hits on average to solve.
1/6 * 3 hits (solved)
2 3 1 -> 1/6 * 1 hit
3 1 2 -> 1/6 * 1 hit
So we have for the first iteration only (4/6 of the cases):
1/6 of chance of solving it in 1 hit
3/6 of chance of solving it in 3 hits
[2/6 for next iteration]
Up to here the average is: 1/6 hits + 3/6 * 3 hits = (1/6 + 9/6) hits = 1
hit + 4/6 hits
But we have only taken into account 4/6 of the cases
For the next iteration as you know, we must multiply by the chance of the
remaining cases.
That is:
2 3 1 -> 1/6 * 1 hit
1/6 * 1/6 = 1/36 of chance of solving it in 2 hits
1/6 * 3/6 = 3/36 of chance of solving it in 4 hits
[1/6 * 2/6 = 2/36 for the next iteration]
3 1 2 -> 1/6 * 1 hit
1/6 * 1/6 = 1/36 of chance of solving it in 2 hits
1/6 * 3/6 = 3/36 of chance of solving it in 4 hits
[1/6 * 2/6 = 2/36 for the next iteration]
So we have:
1/6 of chance of solving it in 1 hit
3/6 of chance of solving it in 3 hits
2/36 of chance of solving it in 2 hits
6/36 of chance of solving it in 4 hits
[4/36 for the next iteration]
average= 1/6 * 1 hit + 3/6 * 3 hits + 2/36 * 2 hits + 6/36 * 4 hits
average= 1/6 hits + 9/6 hits + 4/36 hits + 24/36 hits
average= 10/6 hits + 28/36 hits
average= 60/36 hits + 28/36 hits
average= 88/36 hits
average= 2 hits + 16/36 hits
But we have only taken into account 30/36 of the cases.
I did not search the form of this serie, but I did the iteration on Excel to
find it converges to 3.
So the average for 3 elements is 3.
I haven't read that article of google about the explanation, but this didn't
come "all of a sudden" for me... I took a lot of time calculation and
re-checking to make sure I was doing it right. I don't know how people
figured it all out in a less than an hour. In fact I didn't continue to the
4 elements case because it would have taken too much time, so I did take the
risk that 2 and 3 where special cases... I guess I could have made up a
general demostration buy my math is not as good.
I hope this helps.
2011/5/9 Eagle <[email protected]>:
> 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.
>
>
--
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.
