You have a drawer with n shoelaces in it. You reach into the drawer and select two lace ends at random, and tie them together. Repeat this until there are no more untied lace ends left.
If the two ends are from the same lace, or from the same group of laces already tied at their ends, it will form a loop, and therefore no longer have any free ends.
Continue this until all laces are parts of loops, of either 1 lace, 2 laces, etc.
When you're finished, a certain number of loops will have been formed in this fashion, consisting of one or more laces.
What is the expected number of loops?
We have n shoelaces in the drawer. Each of the laces has 2 ends, making 2n lace ends in total. So, we reach into the drawer and grab one of these ends at random. Now, there are 2n-1 ends left in the drawer to choose from at this point. We are going to choose one of these 2n-1 ends, randomly, and tie it to the one we're already holding. Obviously this can result in one of two distinct outcomes. Either (a)we end up tying the shoelace back to itself and creating a loop, or (b)we tie two different laces together, simply forming a longer, unlooped piece made of two individual laces.
The probability of case (a) is 1/(2n-1), because only one of the 2n-1 lace ends will complete the loop. In this case, we have created a loop and must add one to the final count.
The probability of case (b) is not really important to the problem; however, it is obviously just (2n-2)/(2n-1). In this case, we have not formed a loop.
Therefore, the expected number of loops created during this first tying is 1(1/(2n-1)) + 0((2n-2)/(2n-1)) = 1/(2n-1)
The important thing to notice, however, is that no matter which of these two cases eventuates, we end up with n-1 unlooped laces left in the drawer! Notice here that it doesn't matter that one of the unlooped laces may be made up of two individual laces; this won't affect the probability of its ends being selected in further iterations hereafter.
So, at this point, we just repeat the procedure. At this point we have n-1 laces in the drawer, with a total of 2n-2 lace ends. Therefore the probability of forming a loop on the second tying will be one out of 2n-3 (think about it!), and so the expected number of loops created during the second tying is 1/(2n-3).
We have to contine tying ends until there are none left. This means that the above procedure has to be repeated n times in total (as we started with 2n lace ends, and each iteration joins 2 ends and hence decreases the number of ends remaining by 2). The expected number of loops that we end up with at the end of all the n tyings is just the sum of the expected number of loops produced during each individual step. Hence this expected number is
1/(2n-1) + 1/(2n-3) + ... + 1/5 + 1/3 + 1/1
This is just the sum from i = 1 to n of 1/(2i-1).
The reader may easily test a few small values of n to convince himself of the validity of this argument.
-John
Solution with explanation
