Section 4.2

Symmetry in a Shuffled Deck

Position arguments in a random permutation: the card after the first ace, which colour runs out first or last, whether a set of cards precedes a marker card.

Toolkit

A random permutation of a finite set of distinguishable objects is exchangeable: any relabelling of positions, or restriction to a subset of the objects, is again uniformly random on its own set of relative orders. This lets you discard irrelevant objects and reason only about the relative order of the objects that matter.

Key facts:

If $n$ distinguishable objects are placed in uniformly random order, every one of the $n!$ orderings (equivalently, every relative order of any subset) is equally likely.
For $k$ marked items and one marker among $n$ positions, each of the $k+1$ relative placements of the marker is equally likely with probability $\frac{1}{k+1}$ .
“Which type runs out last/first” is equivalent to asking the colour of the last (or first) item in a uniformly random full ordering of all items.
Conditioning on the identity/position of one special item (e.g. the first ace) leaves the remaining items uniformly randomly ordered among the remaining positions.

Problems