Ponder This Challenge - April 2007 - Random walk of a frog

This month's puzzle concerns a frog who is hopping on the integers from minus infinity to plus infinity. Each hop is chosen at random (with equal probability) to be either +2 or -1. So the frog will make steady but irregular progress in the positive direction. The frog will hit some integers more than once and miss others entirely. What fraction of the integers will the frog miss entirely? Please find an exact answer.

Update, 4/20/07: You may consider the answer to be the limit as N goes to infinity of the fraction of integers between -N and N a frog starting at -N and randomly hopping as described misses on average. Also an answer correct to six decimal places is good enough.

Solution

• Click here to view the solution

  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

Solvers

• V Balakrishnan (04.04.2007 @02:22:47 PM EDT)
• Frank Yang (04.05.2007 @10:35:20 AM EDT)
• Michael Quist (04.05.2007 @11:08:35 AM EDT)
• Alan Murray (04.05.2007 @12:54:18 PM EDT)
• Dan Dima (04.05.2007 @02:31:45 PM EDT)
• Dion Harmon (04.05.2007 @04:17:21 PM EDT)
• Mark Perkins (04.05.2007 @06:23:28 PM EDT)
• Joseph DeVincentis (04.05.2007 @09:57:57 PM EDT)
• Tom Gutman (04.06.2007 @03:06:13 AM EDT)
• ariel flat (04.06.2007 @07:54:11 PM EDT)
• John T. Robinson (04.07.2007 @12:43:06 AM EDT)
• Ed Sheppard (04.07.2007 @02:29:28 AM EDT)
• zhou guang (04.09.2007 @01:11:50 AM EDT)
• David McQuillan (04.10.2007 @02:29:08 PM EDT)
• John G. Fletcher (04.11.2007 @10:50:51 PM EDT)
• Celia Anteneodo (04.11.2007 @11:15:18 PM EDT)
• Chris Danielian (04.12.2007 @06:13:32 PM EDT)
• Christian Blatter (04.13.2007 @05:44:06 AM EDT)
• Gale Greenlee (04.13.2007 @03:49:20 PM EDT)
• Koen Vossen (04.15.2007 @06:39:55 PM EDT)
• Ashish Srivastava (04.18.2007 @05:01:22 PM EDT)
• Ron Yu (04.18.2007 @08:13:01 PM EDT)
• Nyles Heise (04.19.2007 @02:27:09 AM EDT)
• Renato Fonseca (04.19.2007 @09:31:20 PM EDT)
• Yurun Liu (04.21.2007 @12:33:42 PM EDT)
• Rob Berger (04.22.2007 @02:35:48 PM EDT)
• Xianchao Xie (04:23:2007 @09:47:35 AM EDT)
• Mark Thornquist (04.23.2007 @07:53:56 PM EDT)
• Marcus Hedbring (04.24.2007 @10:02:48 AM EDT)
• Teodora Baeva (04.24.2007 @03:14:43 PM EDT)
• Adel El-Atawy (04.25.2007 @06:17:16 PM EDT)
• Roberto Tauraso (04.26.2007 @04:15:46 PM EDT)
• Wolf Mosle (04.27.2007 @05:08:13 PM EDT)
• Andreas Eisele (04.27.2007 @05:55:33 PM EDT)
• Dharmadeep Muppalla (04.28.2007 @06:40:47 AM EDT)
• Paulo Sousa (04.29.2007 @10:01:27 AM EDT)
• Pedro Fonseca (04.29.2007 @10:13:46 AM EDT)
• Jiri Navratil (04.30.2007 @02:42:54 AM EDT)
• Phil Muhm (04.30.2007 @03:38:26 PM EDT)
• Hsiu-Khuern Tang (04.30.2007 @09:03:26 PM EDT)