0
$\begingroup$

I have a pack of cards and use the following method to shuffle them

  • Pick a random card from the deck and replace the first card with it
  • Put the first card back in the deck
  • Move to the second card and repeat the process till the final card

So I select any one of 51 cards to replace the first card, 50 for the second, 49 for the third and so on till the 51st card. Cards once selected and replaced aren't to be put back in the deck

Given the above method

  • Does all cards have equal probability of ending up in any position?
  • If the answer is yes or no, how to calculate and prove it?
  • 0
    Ignore the alert. Anyway, it's bedtime here. Maybe I'll come back to it tomorrow.2012-05-17

2 Answers 2

2

Hint: Can the first choice be the first card, which then stays put? Given your answer, what is the probability that a given card ends up first? What is the probability that a given card ends up second?

  • 0
    @Ubermensch: If the first card can't be the one that starts out on top, the shuffle isn't totally random and you are done. Looking at the starting pack there are many arrangements that are forbidden (probability 0). To have a random shuffle each card has to have 1/52 chance of being in each place and beyond this there cannot be any correlation between which cards end up in each position. More interesting is the case where the first selection includes the top card.2012-05-17
0

As Ross Millikan points out, if you must swap the first card with some card strictly below it, then the card that starts out on top has probability zero of winding up on top, so the answer to your (first) question is, no. As Ross also suggests, things are more interesting when you allow the first card (and each subsequent card) to stay put; make the top card swap with the $k$th card with probability $1/52$ for each $k$, $1\le k\le52$, then make the second card swap with the $k$th card with probability $1/51$ for each $k$, $2\le k\le52$, etc. etc. Then indeed all cards have equal probability of ending up in any given position; in fact, more is true, as all 52-factorial possible permutations of the deck are equally likely.

This is most easily seen by proving that it's true not just for a 52-card deck, but for an $n$-card deck, for any positive integer $n$, using induction on $n$. The base case is easy. Then assume it's true for $n$-card decks, and assume you have an $n+1$-card deck. Make the first swap; any card could now be on top, all with equal probability, and the card that's now on top never gets moved after this, so you are now dealing with just the remaining $n$ cards. Now apply the induction hypothesis!

  • 0
    Thanks. The second case(the interesting one) is the one I am working on. Got the intuition. Would work towards the proof.2012-05-18