probability of deck of cards

Question

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.