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.
