You can't add probabilites, but you can add expected values. The expected value isn't a probability, it's the weighted mean.
For a coin it's true it can be confusing because it is one element, the value is 0 or 1 and you are counting successes. For a dice roll, the expected value is 3.5, all of them have the same chance, so the mean is the expected value. For Goro, the random variable used is the number of elements in the correct order. The probabilities of each outcome are different, as people have shown examples of 3 and 4 unsorted arrays. Since expected value isn't a probability, it has a property that E(aX + bY) = a E(X)+ b E(Y) Going back to Goro, each element does have 1/N probability to fall in the correct place. This is because there are N places, and only one is correct. So the expected value for the number of elements sorted in each one position is 1/N. This is 1 when the correct element lands, and 0 when any other. You can add the EXPECTED values for numer of elements sorted in each position to get the expected value of number of elements in the correct place in the whole array. We are adding expected values, not probabilities, it's true that the number is the same for 1 element but it has different meaning. So you get N*1/N=1. On Tue, May 10, 2011 at 8:41 AM, Eagle <[email protected]> wrote: > P[X_1 @ 1] = 1/N, P[X_2 @ 1] is also = 1/N, ... P[X_N @ 1] = > 1/N > If you add all these, 1/N + 1/N + 1/N .... N times, it is equal to 1. > i.e. N x 1/N = 1. This is telling that when the table is hit > definitely some number is bound to fall at position 1. It is like > saying, when you toss a coin, either heads or tails is definitely > going to show; or if you roll a dice, definitely 1 or 2 or 3 or 4 or 5 > or 6 is going to show up!! > > Eagle > > > On May 10, 9:38 am, darthur <[email protected]> wrote: >> For those of you who are interested, here is a little more background >> on Linearity of Expectation, which is what the analysis uses. >> >> A "random variable" is any measurement you make after some random >> events have occurred. The "average value" discussed in this problem is >> officially called "expected value". The expected value of an integer- >> valued random variable X is defined by the following equation: >> >> E[X] = 0 * P[X=0] + 1 * P[X=1] + ... + n * P[x=n] >> >> P[X=2] means the probability that X ends up being 2 after all your >> random events are done. >> >> Here are some random variables in the GoroSort problem: >> - X is the number of elements that Goro moves into the correct >> position after permuting a group of size n. >> - X_1 is 1 if element #1 is moved into the correct position, and 0 >> otherwise. >> - X_2 is 1 if element #2 is moved into the correct position, and 0 >> otherwise. >> - etc. >> >> No matter what happens, it will always be true that X = X_1 + X_2 >> + ... + X_n. There is a theorem called "Linearity of Expectation" that >> says that E[X] = E[X_1] + E[X_2] + ... + E[X_n]. If you get used to >> the notation and write down the formulas for expected values, it is >> actually pretty obvious. Now, let's think E[X_1]. Element #1 can end >> up in n different places, exactly one of which is correct. Therefore >> P[X_1=1] is exactly 1/n, and P[X_1=0] is exactly (n-1)/n. Therefore, >> plugging into the previous formula, E[X_1] = 1/n. Similarly, E[X_k] = >> 1/n for all k. Adding these all up, we get E[X] = 1! >> >> It's a very handy trick when you get the hang of it. Anyway, I hope >> you all enjoyed the contest, and good luck on the next round! > > -- > 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.
