Currently I am following Sheldon Ross' A first course in probability. And I got stuck in this question:

Consider the following technique for shuffling a deck of $n$ cards: For any initial ordering of the cards, go through the deck one card at a time and at each card, flip a fair coin. If the coin comes up-heads, then leave the card where it is; if the coin comes up-tails, then move that card to the end of the deck. After the coin has been flipped $n$ times, say that one round has been completed. For instance, if $n=4$ and the initial ordering is $(1,2,3, 4)$, then if the successive flips result in the outcome $(H,T,T,H)$ then the ordering at the end of the round is $(1,4,2,3)$. Assuming that all possible outcomes of the sequence of $n$ coin flips are equally likely, what is the probability that the ordering after one round is the same as the initial ordering?

The book says the answer is $\frac{n+1}{2^n}$, but the answer I got is $\frac{2}{2^n}$ since we have two successive flips that will produce the same ordering (I.e. $(H,H,...,H)$ and $(T,T,...,T)$)?

Thanks on any hint/help.


Any flip sequence where all heads come before all tails will preserve the initial ordering. For example, if $n = 4$, then each of the following will work: $$ (H, H, H, H) \\ (H, H, H, T) \\ (H, H, T, T) \\ (H, T, T, T) \\ (T, T, T, T) $$ It's easy to see that in general, this can happen in $n + 1$ ways.

  • $\begingroup$ Thanks. I didn't got that. $\endgroup$ – MathNerd Oct 29 '14 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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