Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
    
When you put the first card back in the deck, where in the deck do you put it? Do you mean it switches places with the random card chosen to replace it? And what do you mean, "cards once selected and replaced aren't to be put back in the deck"? If a card is replaced and not put back in the deck, then the deck has fewer than 52 cards, which is not what's usually meant by shuffling. –  Gerry Myerson May 17 '12 at 6:50
    
@GerryMyerson Cards once replaced aren't put back. Its a biased shuffle (shuffle may be the wrong term). So for the first card I pick from the next 51 cards, for the second card, I leave the first card and select from the remaining 50 cards and so on. So there would be no selection for the last card since it is automatically select. And just 2 options for the 51 st card. –  Ubermensch May 17 '12 at 9:16
    
I'm still not with you. You write that you replace the first card, and that you put the first card back in the deck, but now you write that cards once replaced aren't put back. So, is the first card put back in the deck, or isn't it? If it isn't, you only have 51 cards in the deck (and as you continue, you'll have fewer and fewer), and the chance of the first card ending up in any position is zero, because, once replaced, it wasn't put back. So what is going on here? –  Gerry Myerson May 17 '12 at 11:31
    
@GerryMyerson For the first card (7C), I pick any card from the remaining 51 cards (6S). Now I am going to put the original card (7C) back in the deck. And for the next card (6D), I am going to select from the remaining 50 cards excluding 6S and 6D and so on. So what is the probability that 6S,6D,7C or any other card would end up in the list and is it same for all the cards in the pack? –  Ubermensch May 17 '12 at 11:49
    
OK, so where in the deck do you put that 7C when you put it back in the deck? Might you put it on top? Do you always put it on the bottom? Where? –  Gerry Myerson May 17 '12 at 12:53
show 4 more comments

2 Answers

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!

share|improve this answer
    
Thanks. The second case(the interesting one) is the one I am working on. Got the intuition. Would work towards the proof. –  Ubermensch May 18 '12 at 7:34
add comment

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?

share|improve this answer
    
@RossMilikan The first card can be selected in 1/51 ways, the second in 1/50 ways and so on. But I can't think beyond it as to what's the chance of each card being anywhere in the shuffled deck –  Ubermensch May 17 '12 at 4:46
    
@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. –  Ross Millikan May 17 '12 at 5:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.