Question

It s difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 13 years ago.

for(i=1;i<=n;i++)
{
    pick a random index j between 1 and n inclusive;
    swap card[i] and card[j];
}

for the above code am trying to find the probability of original card[k] winding up in slot n is 1/n? I guess it s (n-1)/n * 1/(n-1)=1/n. But can u help me proving this?

Answer 1

The reason the probability that the k^th card will end up in slot n is 1/n is because the n^th iteration completely determines what card ends up in slot n! (<--- that s an exclamation point, not a factorial :-).

Think about it. On the last iteration of the loop, you have some random permutation... and the k^th card is sitting in some slot. The probability it moves into slot n is just the probability that you pick that k^th card at random. Assuming you pick cards with equally likely probability, that probability is 1/n.

Hope this helps.

-Tom

UPDATE

You might be thinking I made a faulty assumption. Namely, you might be wondering... what if the k^th card can end up in different slots with different probabilities? What if the "random shuffling" isn t really random? This is why only the last iteration matters:

Let p_i denote the probability that the k^th card is in slot i on the n-1 iteration (ie - it is in slot i right before the end).

Then the probability that card k ends up in slot n (on the n^th iteration) is:

(1/n)p₁ + (1/n)p₂ + ... + (1/n)p_n

But notice we can factor the (1/n), so we have:

(1/n)(p₁ + p₂ + ... + p_n)

And because these are probabilities, it should be obvious that the sum of the p_i s (i = 1 to n) must equal 1. So we are left with just (1/n).

That is just being a bit more formal to show that the randomness of the state of affairs before the n^th iteration really does not matter.

友情链接