Section 10.5

Cycles and Loops

Cycles of a random permutation, loops formed by tying noodle ends, pruning a random tree: harmonic-sum answers.

Toolkit

These problems share one trick: write the target count as a sum of indicator random variables, each capturing a “fresh start” or “new structure” event, and compute $\mathbb{E}$ by linearity, summing the individual probabilities. Each indicator’s probability is a simple reciprocal, so the final expectation collapses to a harmonic-type sum.

Key facts:

\sum_{k=1}^n \frac1k = H_n \sim \ln n+\gamma,\qquad \sum_{k=1}^n \frac1{2k-1} = H_{2n}-\tfrac12 H_n,

\sum_{k=m}^n \frac1k \to \ln\frac{n}{m}\ \text{as both grow}.

Typical constructions:

Random permutation: processing elements in order, a new cycle starts at step $k$ (among the $k$ remaining unplaced elements) with probability $1/k$ ; a cycle of length exactly $k$ occurs at a given start with probability $1/n$ summed appropriately, giving expected count $1/k$ .
Random matching (noodle ends): with $n$ pairs of ends remaining, a chosen end self-closes with probability $1/(2n-1)$ .
Random tree / recursive structure: a node survives or is selected exactly when it is the first among itself and its ancestors in a random order, probability $1/\text{depth}$ .

Problems