This can be explained with the coin toss too. If you are trying to calculate expected number of heads in a single toss, you will get 0.5, even though its impossible to actually get a half-head in a toss. Similarly, in goro sort for N=2, expected number of pieces that fall in place is 1, even though its impossible to actually have just one piece fall in right place.
On 14 May 2011 20:57, Pedro Osório <[email protected]> wrote: > You are saying that it is impossible to put "exactly one element into the > right position" when N=2, right? I agree, obviously, we have 2 elements in > the right position, or 0 elements in the right position. > What you don't seem to understand is that this doesn't contradict the > statement "The expected number of elements that are put into position is > exactly 1". The reason why you don't understand it, is because you don't > understand the concept of expected value (I won't link it again, since you > refuse to read and try to understand what it means). > What baffles me is that for the case N=2, it is trivial to understand that, > even though "having exactly one element in the right position" is > impossible, the expected value of elements put into the right position is > exactly 1: > Initial: 2 1 > Possible outcomes: > 1 2 - 0.5 probability - 2 elements in the right position > 2 1 - 0.5 probability - 0 elements in the right position > X - elements that go into the right position after one hit for the array [2 > 1] > E[X] = sum(p(X=x) * x) = p(X=0) * 0 + p(X=1) * 1 + p(X=2) * 2 + ... = > All elements with p(X=x)=0 will be eliminated so only x=0 and x=2 matter (as > you have repeatedly said): > E[X] = p(X=0) * 0 + p(X=2) * 2 = 0.5 * 0 + 0.5 * 2 = 1 > > Do you understand now that p(X=E[X]) can be 0? > > > -- > 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.
