Ponder This Challenge - October 2008 - Jumping frog

Ponder This Challenge:

Consider a frog starting from 0 and jumping from integer to integer. With probability p he makes a jump of +1, with probability (1-p) a jump of -1. Assume .5 < p < 1. Assume each jump is independent. Let B(n,k) denote the binomial coefficient n choose k.

1. a. How fast will the frog move towards +infinity?

   b. How many times on average will the frog visit each non-negative integer?

2. What is the probability the frog will be at 0 after 2*n jumps?

3. Combine 1b and 2 to find the sum from 0 to infinity of (x**n)*B(2*n,n). (0 < x < .25).

As usual we ask that you only submit your original work.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  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.

Solvers

• Dan Dima (10.02.2008 @06:23 PM EDT)
• V Balakrishnan (10.02.2008 @08:57 PM EDT)
• Alan Murray (10.02.2008 @09:51 PM EDT)
• Henry Bottomley (10.02.2008 @09:55 PM EDT)
• John T. Robinson (10.02.2008 @11:13 PM EDT)
• Nyles Heise (10.03.2008 @04:53 AM EDT)
• Hongcheng Zhu (10.03.2008 @07:58 AM EDT)
• Joseph DeVincentris (10.03.2008 @10:28 AM EDT)
• Wu Hao (10.03.2008 @10:28 AM EDT)
• Jonathan Campbell (10.03.2008 @11:58 AM EDT)
• Frank Yang (10.03.2008 @12:04 PM EDT)
• Luke Pebody (10.03.2008 @12:17 PM EDT)
• Gary M Gerken (10.03.2008 @01:11 PM EDT)
• Krunoslav Kovac (10.03.2008 @02:10 PM EDT)
• Wolf Mosle (10.03.2008 @05:27 PM EDT)
• Jesse Kolman (10.03.2008 @11:29 PM EDT)
• Alvaro Begue and John Tromp (10.04.2008 @02:54 PM EDT)
• Fred Batty (10.04.2008 @04:32 PM EDT)
• Frank Vernaillen (10.04.2008 @05:51 PM EDT)
• Wolfgang Kais (10.04.2008 @08:58 PM EDT)
• Andreas Eisele (10.05.2008 @06:13 PM EDT)
• John G. Fletcher (10.05.2008 @06:44 PM EDT)
• Ariel Flat (10.06.2008 @03:06 AM EDT)
• Michael Liepelt (10.06.2008 @01:38 PM EDT)
• Albert Stadler (10.06.2008 @03:24 AM EDT)
• Abhishek Kumar (10.06.2008 @04:21 PM EDT)
• James Dow Allen (10.06.2008 @04:40 PM EDT)
• Michel Speiser (10.06.2008 @04:57 PM EDT)
• Ya Liu (10.06.2008 @04:59 PM EDT)
• Arthur Breitman (10.06.2008 @05:11 PM EDT)
• Muharrem Gorkem (10.06.2008 @06:47 PM EDT)
• Yu Yat Hong (10.06.2008 @11:20 PM EDT)
• Paul Shearer (10.06.2008 @12:47 PM EDT)
• Dani Gluck (10.07.2008 @08:59 AM EDT)
• C A Subramanian (10.07.2008 @12:57 PM EDT)
• Mark Perkins (10.08.2008 @04:07 PM EDT)
• Tomas Schiffauer (10.07.2008 @06:38 PM EDT)
• Dmitry Litvinenko (10.09.2008 @05:49 AM EDT)
• Javier Rodriguez Soler (10.08.2008 @09:21 PM EDT)
• Zhou Guang (10.09.2008 @08:08 AM EDT)
• Ben Tarlow (10.09.2008 @01:13 PM EDT)
• Karl D'SOUZA (10.09.2008 @03:30 PM EDT)
• David Meiri (10.09.2008 @10:54 PM EDT)
• Maris van Sprang (10.10.2008 @08:45 AM EDT)
• Uri Yanover (10.10.2008 @02:46 PM EDT)
• Boris Nikolaus (10.13.2008 @08:50 PM EDT)
• Alex Wagner (10.14.2008 @01:31 PM EDT)
• Frank E. Mullin (10.14.2008 @11:59 PM EDT)
• Mithil Ramteke (10.15.2008 @01:38 PM EDT)
• Will Hasenplaugh (10.15.2008 @07:19 PM EDT)
• Nancy Schwarzkopf (10.16.2008 @06:05 PM EDT)
• Michael Schaaf (10.17.2008 @04:12 PM EDT)
• Greg Janoe (10.17.2008 @06:56 PM EDT)
• Rickard Bjorklund and Carl Hammarlund (10.18.2008 @3:17 AM EDT)
• David Friedman (10.18.2008 @09:43 PM EDT)
• Xiaoyang Guan (10.20.2008 @07:14 PM EDT)
• Martin Giese (10.21.2008 @11:16 AM EDT)
• Michael Traut (10.21.2008 @10:50 PM EDT)
• Andea Andenna (10.22.2008 @08:54 PM EDT)
• Amos Guler (10.23.2008 @10:51 AM EDT)
• Martin Thiim (10.24.2008 @05:59 AM EDT)
• Naji Ashry (10.24.2008 @10:38 AM EDT)
• Jimmy He (10.25.2008 @03:05 AM EDT)
• Ashish Mishra (10.27.2008 @08:28 PM EDT)
• Jan van Delden (10.28.2008 @09:03 AM EDT)
• Jiri Navratil (10.28.2008 @08:40 PM EDT)
• Radu Borza (10.29.2008 @11:22 AM EDT)
• Jean-Pascal Harroch and Travis Craig (10.30.2008 @06:18 PM EDT)
• Kai Guttmann (10.30.2008 @7:10 PM EDT)
• Joyo Caldeira (10.30.2008 @07:36 PM EDT)
• Timothy Eller (10.31.2008 @06:41 AM EDT)
• Qin Chen (10.31.2008 @07:56 PM EDT)
• Mate Bartalos (10.31.2008 @08:28 PM EDT)