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.
