Random Permutations: Cycles, Fixed Points, and Shuffles

Random permutations sit under an outsized share of famous problems — the 100 prisoners, hats and envelopes, card shuffling — and they yield to a small set of structural facts. This capstone lesson collects them.

Cycle structure: the skeleton

Every permutation decomposes into disjoint cycles (follow $1 \to \pi(1) \to \pi(\pi(1)) \to \cdots$ until it closes). For a uniform random permutation of $n$:

• P(element 1 lies in a cycle of length $k$) = $1/n$ for every $k$ — cycle length is uniform, a lovely and non-obvious fact.
• P(a cycle longer than $n/2$ exists) = $\sum_{k>n/2} 1/k \approx \ln 2 \approx 0.69$ — exactly the failure probability in the 100-prisoners strategy; that celebrated puzzle is this bullet.
• Expected number of cycles $= H_n \approx \ln n$ — a 52-card deck's permutation has about 4.5 cycles. (Proof by linearity with the right indicators — the recurring trick.)

Fixed points: the 1/e cluster

Fixed points are 1-cycles — "people who got their own hat." Three facts that travel together:

• Expected fixed points $= 1$, for any $n$ (indicators: each position matches with probability $1/n$).
• P(no fixed point) $\to 1/e \approx 37\%$ (derangements, via inclusion-exclusion from the combinatorics lesson).
• The number of fixed points converges to Poisson(1) — rare-events logic from the distribution zoo, applied to matching. So P(exactly two people get their own hats) $\approx \frac{e^{-1}}{2!} \approx 18\%$, computable at a whiteboard in seconds.

The trio {mean 1, void 1/e, Poisson} answers essentially every hats/envelopes/gift-exchange variant an interviewer can compose.

Records and relative order

Any question about ranks — comparisons, not values — is secretly a uniform-random-permutation question: the $k$-th draw is a running maximum with probability $1/k$, expected records are $H_n$ (the order-statistics lesson), and the secretary problem's analysis runs entirely on this observation. When an interviewer strips numbers from a problem and leaves only "better/worse than what came before," switch to permutation thinking immediately.

Shuffling: how randomness is manufactured

Two results with real content:

• Fisher–Yates: the correct way to shuffle in code — walk $i$ from $n-1$ down, swap position $i$ with a uniform position in $[0, i]$. Exactly uniform over all $n!$ orders, $O(n)$. The classic bug (swap with a uniform position in $[0, n-1]$ every time) produces a biased shuffle — $n^n$ equally likely paths can't map evenly onto $n!$ outcomes since $n! \nmid n^n$; spotting that is a known quant-dev screen.
• Seven riffle shuffles. Gilbert–Shannon–Reeds modeling of human riffle shuffles gives the famous result (Bayer–Diaconis): a 52-card deck needs about 7 riffles before it's close to uniform — fewer leaves detectable structure (exploited historically by card counters and magicians alike). The deeper point for quants: "mixing time" — how long until a Markov chain forgets its start — is a measurable, sometimes surprisingly large quantity; the Markov-chains lesson's convergence has a rate, and rates matter.

The interview version

"30 people throw their badges in a pile and each takes one at random. Expected number who get their own? Probability nobody does? Probability exactly one does?" — 1; $\approx 1/e$; $\approx 1/e$ again (Poisson(1) at $k=0$ and $k=1$ are equal — a pleasing flourish). "Why does your prisoner strategy work?" — cycle-following turns independent guesses into one event about the permutation's longest cycle. If you can narrate cycles, fixed points, and records fluently, this whole genre — among the most-asked at Jane Street — is banked.