Monday, January 11, 2010

Monday Probability 1 : Noodles

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)

2 comments:

  1. Consider 1 trial where there are t non-closed noodles. After glueing the 2 ends, you can either:
    (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

    ReplyDelete

Old Problems

Follow me