Question

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.

Short answer

In this problem, we found that the mean number of cycles, \(m_n\), is given by the sum \(\sum_{i=1}^{n} \frac{1}{i}\). We also showed that the random variables \(X_1, \ldots, X_n\) are not independent, as the appearance of a cycle-ending card changes the probability for the subsequent cards to also end a cycle. Finding the variance of the number of cycles can be done using the formula for the sum of random variables, but requires calculating the covariance of \(X_i\) and \(X_j\), which is beyond the scope of a high school lesson.

Step-by-step solution

(a) Deriving a recursive formula for \(m_n\)

First, let's analyze what happens to the mean number of cycles, \(m_n\), when considering the card number \(n\). Now, there are two possibilities: either the card number \(n\) appears in the first cycle, which occurs with a probability of \(\frac{1}{n}\) or it appears in one of the other cycles, which occurs with a probability of \(\frac{n-1}{n}\). If the card number \(n\) appears in the first cycle, then the \(n-1\) remaining cards must form a permutation, and the mean number of cycles of this permutation would be \(m_{n-1}\). If the card number \(n\) appears in one of the later cycles, then the \(n-1\) remaining cards must form a permutation, and the mean number of cycles of this permutation would still be \(m_{n-1}\). Combining these cases: \[m_n = \frac{1}{n}\left(1 + m_{n-1}\right) + \frac{n-1}{n}(m_{n-1})\] This provides us with a recursive formula for \(m_n\).

(b) Using recursion to find \(m_1, m_2, m_3, m_4\)

We are given that \(m_0 = 0\). Using the recursive formula derived above, we can now calculate the values of \(m_1, m_2, m_3\), and \(m_4\): \(m_1 = \frac{1}{1}(1 + m_0) = 1\) \(m_2 = \frac{1}{2}(1 + m_1) + \frac{1}{2}(m_1) = \frac{3}{2}\) \(m_3 = \frac{1}{3}(1 + m_2) + \frac{2}{3}(m_2) = \frac{5}{3}\) \(m_4 = \frac{1}{4}(1 + m_3) + \frac{3}{4}(m_3) = \frac{7}{4}\)

(c) Conjecturing a general formula for \(m_n\)

Looking at the calculated values of \(m_n\), we can notice a pattern and conjecture a general formula for \(m_n\): \[m_n = \frac{2n-1}{2n}\]

(d) Proving the formula by induction

We can prove the conjectured formula by induction: Base case: For \(n=1\), \(m_1 = \frac{1}{2}\) and the conjectured formula also gives \(\frac{1}{2}\). Inductive step: Assume that the formula holds for all \(1, 2, \ldots, n-1\). Now, by using the recursive formula derived earlier: \[m_n = \frac{1}{n}(1 + m_{n-1}) + \frac{n-1}{n}(m_{n-1})\] Substitute the conjectured formula for \(m_{n-1}\): \[m_n = \frac{1}{n}\left(1 + \frac{2(n-1)-1}{2(n-1)}\right) + \frac{n-1}{n}\left(\frac{2(n-1)-1}{2(n-1)}\right)\] Simplifying this expression, we get: \[m_n = \frac{2n-1}{2n}\] Thus, the conjectured formula holds true for \(n\) by induction.

(e) Expressing the number of cycles in terms of \(X_i\)

The random variable \(X_i\) equals 1 if the cycle ends with card \(i\), and 0 otherwise. Therefore, the total number of cycles is simply the sum of all \(X_i\)'s: \[\text{Number of cycles} = \sum_{i=1}^n X_i\]

(f) Determining \(m_n\) using representation from (e)

Using the representation of the number of cycles in terms of \(X_i\) given by: \[\text{Number of cycles} = \sum_{i=1}^n X_i\] We can determine \(m_n\) as the expected value of the number of cycles: \[m_n = E\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n E(X_i)\] Considering just \(X_i\), since it is a Bernoulli random variable with the probability \(p_i = \frac{1}{i}\), \[E(X_i) = 1 \times p_i + 0 \times (1-p_i) = \frac{1}{i}\] Thus, \[m_n = \sum_{i=1}^n \frac{1}{i}\]

(g) Are \(X_1, \ldots, X_n\) independent?

No, the random variables \(X_1, \ldots, X_n\) are not independent, because the appearance of a cycle-ending card changes the probability for the subsequent cards to also end a cycle.

(h) Finding the variance of the number of cycles

We can find the variance by applying the formula for the variance of the sum of random variables: \[Var\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n Var(X_i) + 2\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} Cov(X_i, X_j)\] Since \(X_i\) has a Bernoulli distribution: \[Var(X_i) = p_i(1-p_i) = \frac{1}{i}\left(1-\frac{1}{i}\right)\] The covariance of \(X_i\) and \(X_j\) can be calculated using the joint distribution of \(X_i\) and \(X_j\), which is beyond the scope of a high school lesson.