Solution:
Initially there are 200 free ends. The number of free ends decreases by 2 each time since either two separate pieces are tied together, or a new loop is formed. So exactly 100 steps are always needed. Let Ij be the indicator r.v. for whether a new loop is formed at the jth step. At the time when there are n unlooped pieces (so 2n ends), the probability of forming a new loop is n/(2n C 2) = 1 / (2n - 1) since any 2 ends are equally likely to be chosen, and there are n ways to pick both ends of 1 of the n pieces. By linearity, the expected number of loops is summation of 1 / (2n - 1) over n = 1 to 100.

Copyright © 2011 Stat 110 Harvard.
Website layout by former Stat110'er.