For the case with 2 elements in the wrong position: The expected number of permutations needed to get them in the correct position is 2. The expected number of new elements in the correct position after each permutation is 1.
For the case with N elements in the wrong position: The expected number of permutations needed to get them in the correct position is N. The expected number of new elements in the correct position after each permutation is 1. On May 15, 2:00 am, Eagle <[email protected]> wrote: > @Pedro, > Are you contradicting yourself or the contest analysis, in the > following statement?> E[X] = p(X=0) * 0 + p(X=2) * 2 = 0.5 * 0 + 0.5 * 2 = 1 > > Until now, you were saying E[2] = 2. Now, you are saying it is 1. > Check your last mail to me, you have given following-> E[n=3] = 1 + (1/6 * 0 > + 0 * E[n=1] + 1/2 * E[n=2] + 1/3 * E[n=3]) = 1 + (1/2 * E[n=2] + 1/3 * > E[n=3]) > > The dimension (units) on the LHS & RHS of the equation are not > matching. I have read the links about > expected value that you have given. The problem is, I am also having > the same feeling (please do not > get offended) that you are not using the concept properly. > Thanks again for your patience to continue the discussion. > > Eagle > > On May 14, 8:27 pm, 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.
