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$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?

Short answer

The probability that the ordering after one round is the same as the initial ordering is$(n+1){\left(\frac{1}{2}\right)}^n$.

Step-by-step solution

Given Information.

If $n=4$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.

Explanation.

$\sum _{k=0}^n{\left(\frac{1}{2}\right)}^k{\left(\frac{1}{2}\right)}^{(n-k)}=\sum _{k=0}^n{\left(\frac{1}{2}\right)}^n=(n+1){\left(\frac{1}{2}\right)}^n$

If we let the first $k$trails be heads and remaining to be tails, then the order will remain unchanged.

Explanation.

Therefore,

the probability that the ordering after one round is the same as the initial ordering is

$(n+1){\left(\frac{1}{2}\right)}^n$.