@Pedro, As per you and the contest analysis- > In English, this is saying that the expected number of elements that are out > of position after the first hit > is exactly N - 1, or equivalently, the expected number of elements that are > put into position by the first > hit is exactly 1. This follows from "linearity of expectation":
Would you please explain that for N=2, why not the first hit put exactly one element in correct position? Eagle On May 14, 6:47 pm, Pedro Osório <[email protected]> wrote: > 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.
