Here’s a problem I’ve seen in a number of places: Consider a bowl of spaghetti with *N* strands, all tangled. We randomly select two ends from the bowl, and tie them together. We then randomly draw two more ends, and tie them together; this repeats until the last two free ends are joined. This process will have created a number of closed loops; specifically, a minimum of one loop and a maximum of *N* loops. What, then, is the expected number of loops?

Let us denote by *P _{N}*(

*k*) the probability of forming

*k*loops starting from

*N*strands. Then we see that this is nonzero only for 1≤

*k*≤

*N*, and the expected number of loops created from

*N*strands is

.

Now, when we select one of the 2

*N*ends of the

*N*strands, we then leave 2

*N*-1 possibilities for the second end. One of these is the other end of the same strand, causing us to form a loop; while the other 2

*N*-2 belong to other strands, causing us to join two strands into a single (larger) strand. In both cases, we now have

*N*-1 strands. We have one loop added with probability and zero loops added with probability , meaning that this first step should add an average of loop, implying .

More rigorously, we see that to get

*k*loops overall, the initial split creates two cases:

1. We form one loop (with probability ) in our first joining, and then form

*k*-1 loops from the remaining

*N*-1 strands (with probability

*P*

_{N-1}(

*k*-1)).

2. We do not form a loop (with probability ) in our first joining, and then form

*k*loops from the remaining

*N*-1 strands (with probability

*P*

_{N-1}(

*k*)).

Combining these, we see that

*P*(

_{N}*k*) obeys the recursive formula

.

Plugging this into our sum for the expected value,

we see

.

Since

*P*

_{N-1}(

*N*)=0, we can remove the last term of the last sum:

,

and we note that this latter sum is the expected value for

*N*-1 strands,

so

,

and for that first sum, we note that

,

where the last step uses the fact that the probabilities for all values of

*k*must sum to unity.

This, then, means

,

just as we reasoned earlier.

Now, for the case that when we start with only one strand, we are guaranteed to create exactly one loop, so . This combines with our recursive formula above to give

,

and so

,

the sum of the reciprocals of the first

*N*odd numbers.

Now, in terms of the harmonic numbers

*H*, we see that by splitting the sum

_{n}*H*

_{2N}between odd and even integers

.

For large

*n*, one has the approximation , where

*γ*is the Euler-Mascheroni constant. Using this on our expected value, we see

.

Inverting, we see that to get an expected value of

*L*, we need to begin with strands.

_{N}Tags: Euler-Mascheroni, Expected Value, Harmonic Number, Math, Monday Math, Probability, Recurrence Relation

## Leave a Reply