Year: 2008
Paper: 3
Question Number: 13
Course: LFM Stats And Pure
Section: Discrete Probability Distributions
Most candidates attempted five, six or seven questions, and scored the majority of their total score on their best three or four. Those attempting seven or more tended not to do well, pursuing no single solution far enough to earn substantial marks.
Difficulty Rating: 1700.0
Difficulty Comparisons: 0
Banger Rating: 1500.0
Banger Comparisons: 0
A box contains $n$ pieces of string, each of which has two ends. I select two string ends at random and tie them together. This creates either a ring (if the two ends are from the same string) or a longer piece of string. I repeat the process of tying together string ends chosen at random until there are none left.
Find the expected number of rings created at the first step and hence obtain an expression for the expected number of rings created by the end of the process.
Find also an expression for the variance of the number of rings created.
Given that $\ln 20 \approx 3$ and that
$1+ \frac12 + \cdots + \frac 1n \approx \ln n$ for large $n$, determine approximately the expected number of rings created in the case $n=40\,000$.Let $X_i$ be the indicator variable a loop is formed when there are $i$ strings in the bag, so $\mathbb{P}(X_i = 1) = \frac{1}{2i-1}$. Therefore
\begin{align*}
&& Y_n &= X_n + Y_{n-1} \\
&& Y_n &= X_n + \cdots + X_1 \\
\Rightarrow && \E[Y_n] &= \frac{1}{2n-1} + \frac{1}{2n-3} + \cdots + \frac{1}{1} \\
&& \var[Y_n] &= \sum_{i=1}^n \frac{1}{2i-1} \frac{2i-2}{2i-1} \\
&&&= 2\sum_{i=1}^n \frac{i-1}{(2i-1)^2}
\end{align*}
\begin{align*}
&& \E[Y_{n}] &= 1 + \frac13 + \cdots + \frac{1}{2n-1} \\
&&&= 1 + \frac12 + \cdots + \frac1{2n} - \frac12\left (1 + \frac12 + \cdots + \frac1n \right) \\
&&&\approx \ln 2n -\frac12 \ln n \\
&&&= \ln 2 \sqrt{n} \\
\\
&& \E[Y_{40\,000}] &= \ln 2 \sqrt{40\,000} \\
&&&= \ln 400 \\
&&&= 2 \ln 20 \approx 6
\end{align*}
About a ninth tried this. Apart from those who had no idea, there were three categories of attempt. The first group obtained the first result but did not spot that regardless of what happens in the first step, immediately after it there are 2n - 2 free ends. The second group safely navigated the results for the general case but could not see how to apply the approximation to obtain the result in the specific case, and the final group had the satisfaction of finding the result. Most fell into the first category, with fewer in the second, and a small number in the third.