A Bucket Of Shoelaces

Relevant wiki: Expected Value - Problem Solving

We can set up a recurrence relation for the expected number of loops. Let E(n) be the expected number of loops for n shoelaces. I imagine the laces are black. Now let us introduce one more lace (I imagine it is red) and start with our bucket of n+1 laces. The probability that the red lace ends up looped with just itself is $p=\frac{1}{2n+1}$ . This follows because one end of the red lace must be tied to one of the other 2n+1 ends in the bucket. Each end is equally likely and just one of those ends is the other red end! If the red lace does not form a one lace loop with itself it must be incorporated into one of the loops formed by n laces. These observations lead to the recurrence relation

$E(n+1)=(1-p)E(n)+p(E(n)+1)=E(n)+p=E(n)+\frac{1}{2n+1}$

and obviously E(1) = 1

Now just crank the handle to get $E(5)=1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{9}=\frac{563}{315}=\boxed{1.787}$

For linguistic ease, I shall refer to a chain of shoelaces that has not formed a loop simply as a shoelace.

Every time two ends are joined, the number of shoelaces decreases by $1$ , and the number of loops formed either stays the same or else increases by $1$ , since either two shoelaces are joined into a single one, or else one shoelace is turned into a loop.

Suppose there are $n$ shoelaces in the bucket to begin with, and let $X_j$ be the number of loops formed when the $j^\mathrm{th}$ pair of ends is joined. The random variable $X_j$ can only take the values $0$ and $1$ . Just before the $j^\mathrm{th}$ pair of ends is joined, there are $n+1-j$ shoelaces and therefore $2(n+1-j)$ free ends in the bucket.

Anton picks one of these ends. The probability that $X_j=1$ is simply the probability that Anton chooses the unique end that is the other end of the shoelace to which Anton's first pick belongs, out of the $2(n+1-j)-1$ other ends that he has to choose from. Thus $E[X_j] \; = \; P[X_j = 1] \; = \; \frac{1}{2(n-j) + 1} \qquad \qquad 1 \le j \le n \;.$ The total number of loops formed is clearly $Y \; =\; X_1 + X_2 + \cdots + X_n \;,$ and so the expected number of loops formed is thus $E[Y] \; =\; E[X_1] + E[X_2] + \cdots + E[X_n] \; = \; \sum_{j=1}^n \frac{1}{2(n-j) + 1} \; =\; \sum_{j=0}^{n-1} \frac{1}{2j+1}$ For this problem we have $n=5$ , so the answer is $\tfrac11 + \tfrac13 + \tfrac15 + \tfrac17 + \tfrac19 = \tfrac{563}{315} \,=\, \boxed{1.787}$ .