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,
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 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.

Advertisements

Tags: , , , , , ,

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: