Come every Monday, something will puzzle you. Come every Monday, something will challenge you. Come every Monday, something will sound interesting. Come every Monday, the beauty of the random world will engage you!
So, come every Monday.

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.

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

This looks like a porn website!!! :P

ReplyDeleteLet S(k) be the number of steps needed to go to the destination when k is the distance from it.

ReplyDeleteWhen 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