Monday, January 25, 2010

Monday Probability 3 : Drunkard on a Polygon

A drunkard is on a n sided polygon, where n is even. He can go to either of the adjacent edges with equal probability. Find the expected number of steps he need to take to reach the opposite edge from where he started.

Answer: n^2/4

2 comments:

  1. This looks like a porn website!!! :P

    ReplyDelete
  2. Let S(k) be the number of steps needed to go to the destination when k is the distance from it.
    When k<n/2, we have S(k)=1+1/2*[S(k-1)+S(k+1)]
    or
    S(k+1)=2*S(k)-S(k-1)-2.
    The solution to this recursion is of the form
    S(k)=k^2+b*k+c. Clearly S(0)=0 implying c=0
    Also, due to symmetry S(k)=S(-k) implying b=0
    So S(k)=k^2 or S(n/2)=n^2/4

    ReplyDelete

Old Problems

Follow me