Fall 2011 Strategic Practice 4: Section 2 (Indicator Random Variables and Linearity of Expectation) - Question 3
There are 100 shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops? (This is a famous interview problem; leave the latter answer as a sum.) Hint: for each step, create an indicator r.v. for whether a loop was created then, and note that the number of free ends goes down by 2 after each step.
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.
"Mathematics is the logic of certainty, but
statistics is the logic of uncertainty."
Copyright © 2011 Stat 110 Harvard.
Website layout by former Stat110'er.