### A bowl of k number of noodles are cooked and are flexible. A trial consists of randomly choosing an end of a noodle for each hand, then gluing them together. Suppose you do k trials (same as number of noodles). What is the expected number of closed circuits?

Answer: 1+1/3+1/5+...+1/(2k-1)

Consider 1 trial where there are t non-closed noodles. After glueing the 2 ends, you can either:

ReplyDelete(1) form a new closed circuit

(2) glue 2 different noodles to form 1 long noodle

In both the cases, the final number of noodles non-closed noodles are t-1.

There are binomial(2t,2)=t(2t-1) possible ways of pairing. Out of these, only t ways result in forming a single circuit. Representing E(t) to be the expected number of closed circuits formed when you have t noodles to start with, we have

E(t)=t/(t(2t-1))*[1+E(t-1)]+[1-t/(t(2t-1))]*E(t-1) implying

E(t)=1/(2t-1)+E(t-1)

Hence

E(k)=1/(2k-1)+E(k-1)=1/(2k-1)+1/(2k-3)+....+1

hmm

ReplyDelete