Here is an exercise from Introduction to Probability (Blitzstein, Hwang):

There are 100 shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops?

Hint: For each step, create an indicator r.v. for whether a loop was created then, and note that the number of free ends goes down by 2 after each step.

As it proposed, I've created an indicator r.v.:

\begin{equation} L_i=\begin{cases} 1, & \text{if loop created on i-th step}.\\ 0, & \text{otherwise}. \end{cases} \end{equation}

I guess that in this problem it is not required to take into account shoelaces lengths and probability to pull "long" lace created from several laces is the same as for "short" laces. Therefore, we can treat all shoelaces equally. In other words, on each step we just loose one lace from the box: either it forms a loop and is removed from the box or it "merges" into another lace. Anyway, each step means minus one shoelace from the box.

If this reasoning is correct, on each step the probability to create a loop is equal to probability to pull one of shoelaces twice, or:

$$ P(L_i=1)=\frac{1}{(100-i + 1)^2} $$

Then, the expected number of loops: $$ E(X)=E(L_1 + L_2 + ... + L_{100})=\sum_{i=1}^{100}\frac{1}{(100 - i + 1)^2}=\sum_{k=0}^{99}\frac{1}{(100 - k)^2} $$

And therefore, expected number of steps until everything is in loops is equal to 100 i.e. the number of shoelaces at the beginning because on each step we loose exactly one shoelace.

Do you think these answers are correct, or at least "close" to the correct solution?

Note: The authors provided an answer for this exercise, but I do not want to look it up because don't want to accidentally discover right answer if my solution is wrong.

  • 1
    $\begingroup$ I think your reasoning for $P(L_i = 1)$ isn't quite right, since you're not picking two shoelaces (with replacement), you're picking two ends (without replacement). At step $i$, there are $101 - i$ shoelaces left, meaning $2(101 - i)$ ends, so if you pick two random ends, there are $\binom{2(101-i)}{2}$ choices of ends in total, and $101 - i$ choices that result in a loop (one choice for each remaining shoelace). $\endgroup$ – user125932 Mar 31 '17 at 5:23
  • $\begingroup$ @user125932 Yes, you are right. I've added the answer below. Actually, this approach seems much more reasonable. $\endgroup$ – devforfu Apr 8 '17 at 6:24

Ok, as @user125932 correctly noted my reasoning was wrong and we need to pick random ends of shoelaces. Here is an explanation from the textbook:

At the time when there are n unlooped pieces (so `2n ends), the probability of forming a new loop is: $$P(I_n = 1) = \frac{n}{\binom{2n}{2}}=\frac{1}{2n-1}$$ The expected number of loops is: $$\sum_{n=1}^{100}\frac{1}{2n - 1}$$

Or using my indexes: $$P(L_i = 1)=\frac{(100 - i + 1)}{\binom{2(100 - i + 1)}{2}}$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.