I am not an expert in probability, but I don't think we can just say that each element has probability 1/n to fall in the correct place and hence, the expected value is n*1/n which is 1. This is because each of these probability events are not independent events. For example, if its given that the first (n-1) elements have fallen in the right place, then infact, the probability for the nth element is 1 and not 1/n. The expected value calculation should be a little more complicated.
If you take coin toss example, each toss outcome is independent of previous events. So, among n throws, if probability of head is 1/2, its completely fair to add the expectation for each of the tosses as (1/2) + (1/2) + ... n times for each toss for getting expected value. But if the toss outcome were not independent but the outcome probability changed with previous outcomes, the above calculation is no longer valid. Am I wrong somewhere? On 10 May 2011 19:20, Brian Curcio <[email protected]> wrote: > 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. > > -- 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.
