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.
(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!