... If you have 2 elements, then there is 1/2 chance of getting them right [in one hit], and 1/2 of not. Of those last 1/2 you have 1/2 (that is a 1/4 of the whole) to get it right [in two hits] and 1/2 (that's the other 1/4 of the whole) not. Of that 1/4 you have 1/2 (that is a 1/8 of the whole) to get it right [in three hits] and the other 1/2 (that is 1/8 of the whole) not.
So, you do the pondered sum of the N first iterations and you will see that it converges to 2 (that's the average number of hits). See: first iteration = 1/2 * 1 hit = 1/2 hits second iteration = 1/2 * 1 hit + 1/4 * 2 hits = 1 hit third iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits = 1 hit + 3/8 hits fourth iteration = 1/2 * 1 hit + 1/4 * 2 hits + 1/8 * 3 hits + 1/16 * 4 hits = 1 hit + 5/8 hits No finite number of iterations is right because they only get as close to cover all the posibilities, but you see the form: sum (i/2^i), you may find that it converges to 2. I did ask wolfram alpha. Now... if you have 3 elements, then there is a 1/6 chance of getting them right [in one hit], 3/6 of getting one element right, since Goro holds those that are right, you can take this as a two element escenario so it becomes a 3/6 chance of getting it right in three hits (the one he did to the three elements plus the two average for the two element case). And lastly the other 2/6 you get nothing right. Of those 2/6... well you get the idea, when you do the pondered sum of the N first iterations and you will see that it converges to 3 (that's the average number of hits). I had to use excel for that. I did trust that that would work for the rest of cases, it took me a long time... bad for me. You may be wondering, how comes the pondered sum is the average? well, the classic average is the sum of the values over the total: [(A + B + C) / Total], you can also express it like this: [(A / Total) + (B / Total) + (C / Total)]. In a grouped average you multiply the values by the number of times they appear [(A * timesA / Total) + (B * timesB / Total) + (C * timesC / Total)]. In our case the total is 1 (that is the 100% of cases) the number of times it appears is the probability and the value is the number of cases. So you see that I don't need to divide by 1 as it gives me the same value... so as it turns out the pondered sum of the number of hits by it's probability is the group average of the number of hits. 2011/5/8 Lei Huang <[email protected]>: > Including the 2-elements array. > There is 50% possibility that no elements will land in its position, > and 50% possibility both of the elements are in the right position. > So the expected is 50% * 2 + 50% * 0 = 1 > > 2011/5/8 Jin Mingjian <[email protected]>: >> "So we can expect that in any random permutation, one element will land in >> its correct sorted pos." except for the 2-elements array? >> >> >> On Sun, May 8, 2011 at 3:20 PM, rajatag12 <[email protected]> wrote: >>> >>> Yes. First thing to see is that Goro would never hit the table with open >>> elements that *could not* land in their correct position for any >>> permutation. Once it is understood, it will be easy to see that solving the >>> prob for each permutation cycle is an independent one. Answering the main >>> question, observe that each element in a sequence of N elements appears in >>> its correct place (N-1)! times out of the N! permutations. So we can expect >>> that in any random permutation, one element will land in its correct sorted >>> pos. So after each hit, Goro should include the last element placed >>> correctly in his set of elements to hold before he hits. Hence, expected >>> number of hits = n. >>> Formal proof has already been provided above. >>> >>> On Sunday, May 8, 2011 7:22:39 AM UTC+5:30, Balajiganapathi wrote: >>>> >>>> I meant: Is n the expected number of hits to sort a n-element *cycle*. >>> >>> -- >>> 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. >> > > -- > 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.
