Consider the following technique for shuffling a deck of n cards

For any 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?

My approach is that the coin flipping as an arity-relation of either heads or tails. Therefore, some multiplication factor by $$2^n$$, in this case the order is $$1, 2, 3, 4,$$ so $$2^4$$.

A deck has 52 cards. If I go through each card at turn, and for every head I leave the card, or tail I place the card at the end of the deck, then I must calculate the total order, though I'm stuck on how to proceed from here!

Edit:

I'm thinking that when a card is left when the coin tosses head, perhaps I can confirm this probability as $$\frac{1}{52}$$ multiplied by an arity relation like $$2^n$$, where if the coin is heads, then I leave the card as: $$P(H) = P(H|L)P(L) + P(H|L^c)(1-P(L))$$ where $$H$$ is heads and $$L$$ is card is left undisturbed. Then given that I flip four times, and I want to find out the probability that I flip heads:

$$H = 0.5; L = 0.2$$

$$P(H) = 2^4[(0.5)(0.2)+(0.5)(1-0.5)]$$

Though I'm unsure if I reasoned correctly.

• Consider the (very few) ways in which the original top card can end up at the top after one round. One of the ways is to keep it there, in which case you can recursively solve this problem for the remaining $n-1$ cards.
– whuber
May 1 '21 at 18:54

How many sequences of coin flips preserve the deck? Call this number $$p(n)$$ for $$n=1, 2, 3,$$ and so on. Since there are $$2^n$$ equiprobable sequences, your answer to the question (about probability) will be $$2^{-n}\,p(n).$$

Obviously $$p(1)=2,$$ because no matter what the outcome of that one flip is, the deck is the same afterwards.

Consider $$p(n+1)$$ for $$n\ge 1.$$ To preserve the deck, either

1. The sequence begins with a heads and the remainder of the sequence preserves the remainder of the deck; or

2. The sequence begins with a tails (which puts the first card at the end) and, after that, every flip must be a tail.

There are $$p(n)$$ ways to complete (1) and only $$1$$ way to complete (2), whence

$$p(n+1) = p(n)+1.$$

You will have no trouble finishing the problem from here.

BTW, the question does not concern any particular deck of cards: it is about arbitrary decks of $$n\ge 1$$ distinguishable cards. But once you have obtained the general answer you are free to apply it to a 52-card deck.