7
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ So roughly spoken we have $E(75)\approx \pi$. $\endgroup$ – principal-ideal-domain Sep 1 '15 at 20:47
  • $\begingroup$ If you are familiar with harmonic numbers you can express $E(n)$ in such terms as $E(n)=H_{2n}-\frac{1}{2}H_n$. $\endgroup$ – principal-ideal-domain Sep 2 '15 at 20:45
4
$\begingroup$

The accepted answer is correct, but I think should be more carefully detailed.

$E(1) = 1$

Pick up two ends. They either belong to the Same Noodle ($S$) or they don't ($\bar{S}$). The $S$ event can be used to "compute expectations by conditioning" in the same spirit of this question. So:

$$E(n) = E(n-1 | S)p(S) + E(n-1| \bar{S}) p(\bar{S})$$

Now $p(S) = \frac{1}{2n-1}$ and $p(\bar{S}) = 1-\frac{1}{2n-1}$. Now the trick is that $E(n-1|S) = E(n-1)+1$ (i.e. if you picked the two ends from the same noodle you've added one loop to the bowl) and $E(n-1|\bar{S}) = E(n-1)$ (i.e if you've picked two ends from different noodles you didn't increase the number of loops).

$$E(n) = E(n-1 | S)p(S) + E(n-1| \bar{S}) p(\bar{S}) = \\ = \left[E(n-1)+1\right]\frac{1}{2n-1} + E(n-1)\left[1-\frac{1}{2n-1}\right] = \\ = E(n-1) + \frac{1}{2n-1}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.