Monday Math 145

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 PN(k) the probability of forming k loops starting from N strands. Then we see that this is nonzero only for 1≤kN, and the expected number of loops created from N strands is

Now, when we select one of the 2N ends of the N strands, we then leave 2N-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 2N-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 PN-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 PN-1(k)).
Combining these, we see that PN(k) obeys the recursive formula
Plugging this into our sum for the expected value,

we see
Since PN-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,
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 Hn, we see that by splitting the sum H2N 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 LN, we need to begin with strands.


Tags: , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: