Problem 10.33 Medium Free 1 variation

Cycles of a Random Permutation

Fifty guests at a party each write their name on a slip of paper and drop it into a hat; then, one by one, each guest draws a random slip (without replacement). Two guests are placed in the same group if there is a chain of draws linking them: for instance if A draws B’s name, B draws C’s name, and C draws A’s name, then A, B and C form one group, and such a cycle can never be joined by anyone else. Equivalently, the groups are exactly the cycles of the random permutation sending each guest to the guest whose name they drew. Find the expected number of groups, rounded to the nearest tenth.

Work it out, then compare with the answer.

SolutionShow the worked solution

Key idea. Reveal the permutation one cycle at a time. At each step exactly one of the remaining names closes the current cycle.

Let $\sigma$ be the uniformly random permutation of the $n=50$ guests, where $\sigma(i)$ is the guest whose name $i$ drew. Reveal $\sigma$ as follows.

Start at guest $1$ and reveal $\sigma(1)$ , then $\sigma(\sigma(1))$ , and so on.
When the chain returns to its starting guest, the current cycle is complete.
Then restart from the lowest-numbered guest not yet visited.

There are $n$ reveals in total. Suppose $k$ names have not yet been revealed as images when a reveal is made. By symmetry, the next image is uniform over those $k$ names. Exactly one of them is the name of the guest who started the current cycle, since that name cannot yet have been used. So this reveal closes a cycle with probability $1/k$ , whatever happened before.

As the reveals proceed, $k$ runs through $n, n-1, \dots, 1$ . The number of groups $C$ is the number of reveals that close a cycle. By linearity of expectation,

\mathbb{E}[C]=\sum_{k=1}^{n}\frac1k = H_n .

Alternative. Count $k$ -cycles directly. A given set of $k$ guests can be arranged in a cycle in $(k-1)!$ ways. Each such cycle occurs in $\sigma$ with probability $(n-k)!/n!$ . Hence

\mathbb{E}[\#\,k\text{-cycles}]=\binom{n}{k}(k-1)!\,\frac{(n-k)!}{n!}=\frac1k .

Summing over $k$ again gives $H_n$ .

For $n=50$ , $H_{50}\approx 4.4992$ , which rounds to $4.5$ .

\boxed{\mathbb{E}[C]=H_{50}=\sum_{k=1}^{50}\frac1k\approx 4.5}

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 10.33a

Fifty guests at a party each write their name on a slip of paper and drop it into a hat; then, one by one, each guest draws a random slip (without replacement). Two guests are placed in the same group if there is a chain of draws linking them (so the groups are exactly the cycles of the resulting random permutation). Find the average size of a group, rounded to the nearest tenth.

Work it out, then compare with the answer.

Solution

We interpret “average size of a group” as the mean size of a group chosen uniformly from all groups occurring across all $n!$ equally likely draws.

From the alternative above, the expected number of $k$ -cycles is $1/k$ . So the $n!$ permutations together contain $n!/k$ cycles of length $k$ , and $n!\,H_n$ cycles in total. A uniformly chosen cycle therefore has length $k$ with probability

\frac{n!/k}{n!\,H_n}=\frac{1}{kH_n}.

Its expected length is

\sum_{k=1}^{n}k\cdot\frac1{kH_n}=\frac{n}{H_n}.

This equals the total number of guests divided by the expected number of groups. Other readings of “average” give different answers:

$\mathbb{E}[50/C]\approx 13.3$ ;
the group containing a fixed guest has size uniform on $\{1,\dots,n\}$ , so its mean is $\frac{n+1}{2}=25.5$ .

For $n=50$ , $50/H_{50}\approx 11.11$ .

\boxed{\frac{50}{H_{50}}\approx 11.1}

Spotted an error? Email us