Ponder This

October 2008

<<September October November>>

The answers are:

1.  
   1. 2*p-1
   2. 1/(2*p-1)
2. ((1-p)**n)*(p**n)*B(2*n,n)
3. 1/sqrt(1-4*x)

They can be derived as follows:

1.  
   1. With each step the expected movement is p*(1)+(1-p)*(-1)= 2*p-1. So over many steps the frog will move towards plus infinity at a speed of (2*p-1).
   2. After n jumps the frog will have moved from 0 to about (2*p-1)*n. So it will have visited each number is this range about n/((2*p-1)*n)=1/(2*p-1) times.
2. In order to be at 0 after 2*n jumps the frog must have made n +1 jumps and n -1 jumps. There are B(2*n,n) ways of ordering these jumps. Each of them will occur with probability ((1-p)**n)*(p**n). The result follows.
3. The expected number of times (including the start) the frog visits 0 is the sum over n of the expression in 2. This will equal 1/(2*p-1). Let x=(1-p)*p. Then p**2-p+x=0. So p=(1+sqrt(1-4*x))/2 (taking this root as p>.5). So 2*p-1=sqrt(1-4*x). The result follows.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com