[Math] Connecting noodles probability question

harmonic-numbersprobability

I don't know how to solve this. You have 100 noodles in your soup bowl. Being blindfolded, you are told to take two ends of some noodles (each end of any noodle has the same probability of being chosen) in your bowl and connect them. You continue until there are no free ends. The number of loops formed by the noodles this way is stochastic. Calculate the expected number of circles.

Best Answer

Let's do it in a more general case. Let the expected number of loops from $n$ noodles be $E(n)$.

Obviously, $E(1)=1$.

For $n>1$, if you pick up two ends, the possibility for those two ends belongs to the same noodle will be $\frac{1}{2n-1}$. Then you have one loop now and there are $n-1$ noodles to keep on going. Otherwise you get no loop and still have $n-1$ noodles to go(The two you pick before are now connected as one). Hence $E(n)=E(n-1)+\frac{1}{2n-1}$

Inductively you may expect that $E(n) = 1+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{2n-1}$.

Related Question