| hard | probability |
You have 100 noodles in your soup bowl. You are told to take two ends of some noodles (each end on any noodle has the same probability of being chosen) in your bowl and connect them. You continue until there are no free ends. What is the expected number of loops? What is the probability of making one large loop which includes every noodle?
Expected number of noodles come from linearity of expectation. Probability comes from multiplying independent probabilities.
First calculate expected number of loops: Denote X1 = identity variable, which takes value 1 every time a (long) noodle becomes a loop by connecting to its end, (if its own end is connected to some other noodle, then that other noodle's end will be considered). Thus, number of loops = X1 +...+ X100, thus, expected number of loops = E(X1) + ... + E(X100). This will give answer = 1/(2N-1) + 1/(2N-3) + ... + 1/3 + 1 where N = 100. This formula can also be proved using induction.
Calculating Probability of single large loop: If you followed last result, this one is simple, this time all the identitiy variables are zero except last one. Thus probability is [1 - 1/(2N-1)] * [ 1 - 1/(2N-3)] * ... * [1-1/3] = Product ( i = 2 to N) [ (2i-2) / (2i-1)]