A deck of \(n\) cards, numbered 1 through \(n\), is randomly shuffled so that all
\(n !\) possible permutations are equally likely. The cards are then turned over
one at a time until card number 1 appears. These upturned cards constitute the
first cycle. We now determine (by looking at the upturned cards) the lowest
numbered card that has not yet appeared, and we continue to turn the cards
face up until that card appears. This new set of cards represents the second
cycle. We again determine the lowest numbered of the remaining cards and turn
the cards until it appears, and so on until all cards have been turned over.
Let \(m_{n}\) denote the mean number of cycles.
(a) Derive a recursive formula for \(m_{n}\) in terms of \(m_{k}, k=1, \ldots,
n-1\).
(b) Starting with \(m_{0}=0\), use the recursion to find \(m_{1}, m_{2}, m_{3}\),
and \(m_{4}\).
(c) Conjecture a general formula for \(m_{n}\).
(d) Prove your formula by induction on \(n\). That is, show it is valid for
\(n=1\), then assume it is true for any of the values \(1, \ldots, n-1\) and show
that this implies it is true for \(n\).
(e) Let \(X_{i}\) equal 1 if one of the cycles ends with card \(i\), and let it
equal 0 otherwise, \(i=1, \ldots, n\). Express the number of cycles in terms of
these \(X_{i}\).
(f) Use the representation in part (e) to determine \(m_{n}\).
(g) Are the random variables \(X_{1}, \ldots, X_{n}\) independent? Explain.
(h) Find the variance of the number of cycles.
