@ Bharath Linearity of expectation: http://en.wikipedia.org/wiki/Expected_value#Linearity
"Note that the second result is valid even if X is not statistically independent of Y." On May 10, 3:22 pm, Bharath Raghavendran <[email protected]> wrote: > 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 > >> athttp://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 > > athttp://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.
