Clutching at Strings

Let’s do a problem together.

Problem. There are 100 pieces of string placed in front of you. You randomly grab two free ends and tie them together. You continue to do this until there are no free ends left. Now, there are just loops. How many loops do you expect to have in front of you?

I’ve said it before and I’ll say it again: scale your problems down. So let’s come up with an easier version of the same problem.

In this case, the obvious way to scale down is to work with fewer pieces of string.

One String

So let’s consider the same problem but for one piece of string. This is trivial as there are only two free ends (the two different ends of the same string) and so the only thing you can do in this case is to tie these two ends together to make a single loop.

Therefore, the answer to our problem for the simple case of one string is one loop.

Notation

Being mathsy folk, we should create some notation to help with our record-keeping. Let’s write $E_n$ to mean the expected number of loops in the $n$ -string scenario.

So far, we have worked out that $E_1 = 1$ . The original problem is asking us to determine the value of $E_{100}$ .

The one-string scenario was not particularly illuminating, so let’s step it up.

Two Strings

What about if we have two pieces of string? Here, we can follow one of two paths:

You grab two ends of the same piece of string and then tie them together. This makes a loop. The rest of this scenario is locked in as you have to grab the remaining two free ends of the other piece of string and tie them together to make a loop. This gives you two loops.
You grab two free ends, each belonging to a different piece of string. You tie these ends together and this leaves you with a single long piece of string. Then your next and only move is to tie the ends of this long piece of string together. This gives you one loop.

There are two paths to follow in the two-string experiment and they each give a different result.

To calculate the expected value $E_2$ , we need to multiply the probability of each path with the result of that path. We could write something like this:

$E_2 = p_1 L_1 + p_2 L_2.$

In the above equation, $p_1$ means the probability that we go down path 1, which is where we start by grabbing two ends of the same string. We use $L_1$ to denote the number of loops we end up with when we go down this path (we already know that $L_1 = 2$ .)

Similiarly, $p_2$ and $L_2$ denote the probability and the number of resulting loops when we go down the second path (we already know that $L_2 = 1)$ .

Really, we just need to work out the probabilities and then we can calculate our expected value of loops for the two-string case.

What is the probability $p_1$ , that is, what is the probability that we grab two ends of the same piece of string?

I like to live my maths problems, so I’m going to imagine that my left hand has grabbed the end of a piece of string. I want to know the probability that my right hand grabs the other end of that same piece of string. There is a $1/3$ chance of this happening, as there are three free ends remaining and only one of those is the free end on the same piece of string. Therefore, $p_1 = 1/3$ .

Immediately, we also know that $p_2 = 1 - p_1 = 2/3$ . And so we have that

$E_2 = \frac{1}{3} \cdot 2 + \frac{2}{3} \cdot 1 = \frac{4}{3}.$

The two-string problem is now solved!

At this point, it might feel like we are grasping at straws (or strings!) to find an idea that will help us solve the 100-string problem.

But it is there. Think about the two paths we could follow when we were sitting there with two free pieces of string. After one step, we would either have one long piece of string, or a loop and a piece of string.

This idea scales quite well to the case with 100 pieces of string.

100 Strings

Consider this. You are sitting there with 100 pieces of string. Just like in the two-string experiment, one of two things can happen when you tie two ends together.

You grab two ends of the same piece of string and then tie them together. This makes a loop. Now you have one loop and 99 pieces of string.
You grab two free ends, each belonging to a different piece of string. You tie these ends together to make a longer piece of string. Now you have 99 pieces of string.

Something smells like recursion. From looking at the above two paths, it’s clear that a solution to the 99 string problem will yield a solution to the 100 string problem.

As there are two paths we can go down, again we may write something like this:

$E_{100} = p_1 L_1 + p_2 L_2.$

Just like before, $p_i$ means the probability that we go down path $i$ and we use $L_i$ to denote the number of loops we end up with when we go down this path.

Note that for path 1, we end up with 1 loop plus 99 pieces of string. Therefore, we have that $L_1 = 1 + E_{99}$ .

For path 2, we end up with 99 pieces of string, and so we have that $L_2 = E_{99}$ .

We can calculate $p_1$ and $p_2$ in a similiar way to the 2-string problem. You can double check my working, but I get that $p_1 = 1/199$ and $p_2 = 198/199$ .

We now have all the information we need to substitute this into the equation

$E_{100} = p_1 L_1 + p_2 L_2.$

We get

$E_{100} = \frac{1}{199} (1 + E_{99}) + \frac{198}{199} E_{99}.$

A smidge of expansion gives us that

$E_{100} = E_{99} + \frac{1}{199}.$

Now, we need to find $E_{99}$ . It’s looking pretty likely that we can express $E_99$ in terms of $E_{98}$ . Indeed, if you go through all the working yourself, you will surely find that

$E_{99} = E_{98} + \frac{1}{197}.$

We can throw the previous two equations into the oven together to get:

$E_{100} = E_{98} +\frac{1}{197} + \frac{1}{199}.$

At this point, you are likely seeing the problem open up before your own eyes. You might even guess that

$E_{100} = E_{97} + \frac{1}{195} +\frac{1}{197} + \frac{1}{199}$

and certainly you would be correct.

You can do some mathematical induction, or you can just live on the wild side like me and jump to the bit where

$E_{100} = E_{1} + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{195} +\frac{1}{197} + \frac{1}{199}.$

Fortunately, we have already figured out $E_1$ , and so we have that

$E_{100} = 1 + \frac{1}{3} + \frac{1}{5} + \cdots + \frac{1}{195} +\frac{1}{197} + \frac{1}{199}$

or, in shorthand:

$E_{100} = \sum_{n=1}^{100} \frac{1}{2n-1}$

So we have our answer in the form of a sum.

You can punch this into a computer or (if you think all maths should be done by hand) you can use the integral

$\int_1^{100} \frac{dx}{2x-1}$

as an approximation. The integral gives you an answer of 2.65 but the real answer from the sum is actually 3.28.

In any case, it’s quite a small number of expected loops!

3 comments

Jack Neubecker says:

November 16, 2022 at 4:36 pm

Lovely problem, I certainly wouldn’t have guessed harmonic sums had much to do with it. I would like to point out that there is a lovely little unstated use of the tower rule of expectation somewhere in here, in a form I don’t think I’ve ever seen it before. Bonus points if you can spot it.

LikeLike

- Adrian W. Dudek says:
  
  January 5, 2023 at 1:23 pm
  
  I will level with you. I had to Google the tower rule of expectation. When I saw the wiki page and definition I was like “oh it’s that thing that I just assume to be true”. Proof is very quick though, once you write everything as sums.
  
  LikeLike
  
  - Jack Neubecker says:
    
    January 5, 2023 at 8:35 pm
    
    Yep, like most “laws” in probability and statistics, they’re true because they damn well should be, and the ‘should be’ usually pops out of a few basic properties of sums/integrals/measures(take your pick given the sample space at hand).
    
    LikeLike