April 2007
Ponder This Solution:
The answer is ((3-sqrt(5))/2)**2 = (7-3*sqrt(5))/2 = .145898+
This can be derived as follows.
First we consider the frog at the origin and ask what is the probability, p, that the frog will ever occupy -1 in the future. It is easy to see that p satisfies the equation p=.5+.5*p**3 since with the next hop the frog will either be at -1 immediately or at 2 and if it is at 2 then in order to return to -1 it will have to go back to 1, then 0, then -1 each part of which will occur independently with probability p. Selecting the appropriate root gives p=(-1+sqrt(5))/2.
Next we select a hop of +2 from the frog's path and ask what is the probability that the middle point was never hit. Clearly going forward in time, from the above, the middle point will be hit with probability p. A little thought shows that going backward in time the middle point had been hit with probability p also. These probabilities are independent so the probability that the middle point from a hop of +2 in the frog's path was never hit is (1-p)**2.
Now if the frog takes 2*n hops (when n is large) about n of the hops will be +2 and about n will be -1. So the frog will move about n units in the positive direction. So to get past a section of integers n long will require about n hops of +2 for each of which the middle point has probability (1-p)**2 of never being hit. So the expected number of points which are never hit is n*(1-p)**2 which means the fraction of points which are never hit is (1-p)**2. Now 1-p = (3-sqrt(5))/2 so the result follows.
Thanks for the acknowledgement (in the top right column of the last page) of the Physical Review Letters paper "Critical Scaling in Standard Biased Random Walks" (http://www.cbpf.br/~celia/paper47.pdf) by Celia. Anteneodo and W. A. M. Morgado.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com