Loops of Spaghetti


You are given a plate of spaghetti and told to do the following: Pick up one end of a spaghetti noodle and tie it to another end of a noodle. Continue to do this until all the ends have been tied together. If there were originally N pieces of spaghetti, what is the expected number of loops of spaghetti you would form? A loop may consist of any number of pieces of spaghetti tied together, and the loops could be linked to one another.

An "expected number" is the average number if the procedure were to be carried out many times.

Source: Stanford EE Ph.D. qualifying exam study questions.


Solution:
Two solutions were received from readers. The first from Adlai Waksman (waksman@cfar.umd.edu):
(Why didn't I get such "logical" questions in my Penn CS Ph.D. comps??? :)

The expected number of loops from N pieces of spaghetti is
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2N-1).

Explanation:

Call the expected number of loops from N (possibly spliced-together
but unlooped) pieces of spaghetti e(N).

Obviously e(1) = 1.

For N>1 you begin by picking up one end of one piece of spaghetti
(out of the 2N ends) and tying it to a random other end.  That end
belongs to the same piece with probability 1/(2N-1), in which case
you have one loop and N-1 pieces to continue playing with, OR it
belongs to a different piece, in which case you have N-1 "pieces"
with no extra loops.  

(In other words, whenever you tie two of the 2N ends together,
you have probability 1/(2N-1) of creating a loop.)

Therefore,

e(N)  =  e(N-1) + 1/(2N-1)  =  1 + 1/3 + 1/5 + ... + 1/(2N-3) + 1/(2N-1).

e(1) = 1;  e(2) = 4/3;  e(3) = 23/15;  etc.
The second from Matthew Daly (daly@ppd.kodak.com):
Let F(x) be the expected number of loops from tying together all ends
from x strands of spaghetti.  Obviously, F(1)=1.  Now, let x>1 be
given.  Choose any one end.  Now, choose another.  There is a 1/2x-1
chance that these will be ends of the same strand and (2x-2)/(2x-1)
chance that they won't.  In the first case, you'll have a loop and x-1
untied strands, and in the latter case you'll effectively have x-1
strands (even though one of them will be longer than the others!)  So,
in the former case there will be 1 + F(x-1) expected loops, and F(x-1)
expected loops in the latter case.  Therefore,

F(x) = (1/2x-1)(1 + F(x-1)) + ((2x-2)/(2x-1)) F(x-1)
     = F(x-1) + 1/(2x-1)
     = 1 + 1/3 + 1/5 + 1/7 + ... + 1/(2x-1) (to be vulgar! *grin*)

An interesting followup question is: what is the smallest number of
spaghetti strands needed to expect more than 5 loops.  The answer is
over 3000 strands!

Mail to Ken