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.
Best Answer
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.