It's quite interesting that you choose the example of two coins, which exactly resembles the game of goro for N=2, as in that case, p(hits<=2) = 0.75.
The problem in your reasoning is that you are computing the cumulative distribution function (cdf)<http://en.wikipedia.org/wiki/Cumulative_distribution_function> at N where the random variable is "number of hits needed to sort an array that has N values out of place initially". You assume that, since for N=2 the cumulative distribution at N is 0.75 (your "probability of winning") and the expected value of hits is 2, then for every N, the cumulative distribution at N must be 0.75 for the number of expected hits to be N. Since the cumulative distribution at N is getting smaller (69.91%, 67.19%, etc) you assume that the expected number of hits must be bigger for such N (it must be big enough such that a game of goro that allows M hits, gives you 75% chance of winning). That is, you are mixing two different concepts and assuming that they MUST be related. Why do you do this? Well, the answer is obvious, you are used to simple probability distributions. For example, the Discrete uniform distribution <http://en.wikipedia.org/wiki/Uniform_distribution_(discrete)>, defined at any interval, has the same expected value (mean) and 50th percentile (median), and so you assume that, for all distributions, the mean must be in some fixed percentile (not necessarily the 50th), every time. This is not true for every distribution, and if you can't understand the numerous arguments that prove it for N=3, do a simulation yourself: (0) nsim=0 (we have done 0 simulations) (1) Start with the array 2 3 1 (completely unsorted), hits=0 (2) Perform a random hit (distribute all the numbers which are in the wrong positions randomly) hits=hits+1 (3) If the numbers aren't sorted, go to (2) (4) total = total + hits, nsim=nsim+1, If nsim is not big enough (10000, or something), go to (1) (5) Compute total/nsim, this is the approximated expected value using these simulations To understand the final step please note that the expected value of hits is always sum(hits * probability(hits)). If you do a lot of simulations, you can approximate probability(hits) by count(hits)/nsim (where count(hits) is the number of simulations where goro hit the table 'hits' times). So you can say that E[hits] = sum(hits * count(hits)/nsim) = sum(hits * count(hits)) / nsim = total / nsim. After you do these simulations, you will get something very close to 3. Which destroys your "casino argument", since by simulating it, you have (I hope) convinced yourself that the expected value is 3 and yet the probability of winning the game of goro for N=3 is not 75%, and this is perfectly natural. -- 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.
