Q. 2.22 - A First Course in Probability

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?

Step-by-Step Solution

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 1 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.

Step 2 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.

Step 3 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$.