[Math] Number of Spaghetti loops

popular-mathprobabilityprobability theorypuzzle

From Peter Winkler's book:

the 100 ends of 50 strands of spaghetti are paired at random and tied togethed. How many pasta loops should you expect from this process on average?

I took ages because I misunderstood the question. The answer in the book asks for the expected number of loops when the ends of a given strand are tied together :

when you make your knot $i$ (0f 50) you pick an end, and of the $101-2i$ remaining ends you can choose to tie to this one, only one (the other end of the strand) makes a loop. It follows that the probability that your knot ends in a loop is $1/(101-2i)$, hence the expected average is $1/99 + 1/97 +… + 1/3+1/1$

In other word a loop is defined to be as per the first row in the picture below , where each each ends of a strand are tied together.

But what if the definition of a loop allowed longer loops like in the second row of my drawing ?

What would be the expected number of loops then ?

enter image description here

Best Answer

I'll explain the thought process more explicitly. We can model random choice of tying with the following algorithm that ties knots one at a time:

Label the spaghetti strings $S_1, \dots, S_{50}$.

Begin with one end of $S_1$. Tie it to a random end of the $99$ remaining. If it makes a knot (there is only one end that does), then start again with any of the remaining spaghetti strings, for simplicity we can just choose $S_2$. If it doesn't make a knot, let's say we tie it to $S_i$. Now choose which end to tie the remaining end of $S_i$.

Notice that no matter whether or not we made a knot on the first tying, we have $97$ ends remaining and still only $1$ of them causes a knot. Hence, we can justify simply adding up the expectations from each step and the answer will end up just being $1/99 + 1/97 + \dots + 1$.