All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
The Celebrated Jumping Frog of Perplexus County (Posted on 2020-03-04) Difficulty: 3 of 5
Your task is to determine the expected value of the time taken by each of 2 frogs to reach the river (defined as distance from the water's edge = 0).

A frog is sitting k meters North of the water's edge of an infinite straight river that runs West to East. A flat area for frog jumping extends North from the water's edge for m meters, and just North of that is a vertical wall that prevents frogs from jumping any farther North. Our frogs jump once per second, but can only jump exactly 1 meter in any of the 4 cardinal directions (N, S, E, or W) which is done randomly with equal probability. At the end of any hop, frogs can only be an integer number of meters from the water from 0 to m, inclusive.

Consider 2 cases:

(case 1) Magoo Frog, who is very nearsighted, cannot see the wall even when he is m meters from the river. He will still try to jump in any of the 4 directions with equal probablity. If he happens to be at m meters and then tries to jump North, he will hit the wall and slide harmlessly down to where he started that jump, still m meters from the river. This "wasted" jump will take 1 second just like all the other jumps.

(case 2) Michigan Frog, who has good vision, will see the wall when he is m meters from the river, and he will jump with 1/3 probability either South, East, or West. If his distance from the water is < m, he jumps in any of the 4 directions.

Determine the expected values E_Magoo(k,m) and E_Michigan(k,m) for the time needed to reach the river.

Analytic and computer simulations welcome.

No Solution Yet Submitted by Larry    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution analysis and simulation Comment 2 of 2 |
Let's start with case 2: Michigan Frog, as it seems to be more concrete.

If he is at distance m from the river, right at the wall, he has a probability of 2/3 of staying at that distance and a probability of 1/3 of moving one unit toward the river. Thus the expexted time, x1, of advancing for the first time to distance m-1 from the river, 
  x1 = (2/3)*x1 + (1/3)*0 + 1
  x1 / 3 = 1
  x1 = 3
  
Let's switch notation (sorry): x1 will be x(1), as we will be referring recursively to x(n), x(n-1) and x(n+1) with the n subscript referring to distance from the wall this time.

After getting away from the wall, consider x(n), the expected number of seconds to advance from n meters from the wall to n+1 meters from the wall for the first time:

x(n) = (x(n-1) + x(n))/4 + x(n)/2 + (1/4)*0 + 1

Note the extra x(n) upon the retreat, as x(n-1) only gets the frog back to the current position; the advance to the next position is also needed.

x(n)/4 = x(n-1) / 4 + 1

x(n) = x(n-1) + 4

Remember, this is the expected length of time to get from position n, measured from the wall, to position n+1, not necessarily all the way to the river.

What does the series look like?

3, 7, 11, 15, 19, 23, ...

But remember each of these is just the expected time to get to the next position. For example, if the wall is just 2 meters from the river, the expected time to get to the river from the wall is 3 + 7 = 10 seconds. Suppose the wall is 3 meters from the river, but the frog starts already one meter from the wall to the river: the expected time is then 7 + 11 = 18 seconds.

Michigan Frog starts m - k meters from the wall and intends to land m meters from the wall. We need Sigma{i= m-k to m-1} x(i).  Unfortunately I've switched from 1-based subscripts to zero-based subscripts, as this clarifies the distance relationship; also the last subscript is m-1 as it's the expected length of time to get to the next distance: there is one less distance involved than the number of positions occupied.

x(i)= 3 + 4*i

There are k members of the series to be added, starting at 3+4*(m-k) and ending at 3+4*(m-1). The sum is 3*k + 4*(m-k/2-1/2)*k. This checks out with the 18 found with m=3 and k=2.

How about case 1, Magoo Frog?

Only the first number changes. This frog has 3/4 probability of staying at the wall when at the wall and 1/4 of advancing instead of the 2/3 and 1/3 respectively. So, going back to the old notation:

x1 =  (3/4)*x1 + 1
x1/4 = 1
x1 = 4

This corresponds to x(0) = 4 in our final notation, so each number in the sequence is higher by 1 meter. His sum is 4*k + 4*(m-k/2-1/2)*k, as there are k terms being added in the sum.

When simplified, both formulae agree with tomarken's. 

Simulations: (annotated results)

5 4  (m and k)
56   (by formula for case 1 Magoo)
5605796/100000        56.05796  (average for 100,000 trials)

52   (by formula for case 2 Michigan)
5206564/100000        52.06564  (average for 100,000 trials)

changing m and k:

5 3
48
4783356 /100000        47.83356

45
4518279/ 100000        45.18279


7 4
88
8797569 /100000        87.97569

84
8392538 /100000        83.92538


4 4
40
3982149 /100000        39.82149

36
3611746 /100000        36.11746


DefDbl A-Z
Dim crlf$
 

Private Sub Form_Load()
 Text1.Text = ""
 crlf$ = Chr(13) + Chr(10)
 Form1.Visible = True
  
  m = 4: k = 4
  
  Text1.Text = Text1.Text & m & Str(k) & crlf
   
  Text1.Text = Text1.Text & 4 * k + 4 * (m - k / 2 - 1 / 2) * k & crlf
  Randomize Timer
  trials = 0
  Do
   d = m - k: moves = 0
   Do
    r = Int(Rnd(1) * 4)
    Select Case (r)
      Case 0
        If d = 0 Then dd = 0 Else dd = -1
      Case 1, 2
        dd = 0
      Case 3
        dd = 1
    End Select
    d = d + dd: moves = moves + 1
    If d = m Then
     totmoves = totmoves + moves
     trials = trials + 1
    End If
   Loop Until d = m
   DoEvents
  Loop Until trials = 100000
  Text1.Text = Text1.Text & totmoves & Str(trials) & "        " & totmoves / trials & crlf & crlf
  
  Text1.Text = Text1.Text & 3 * k + 4 * (m - k / 2 - 1 / 2) * k & crlf
   
  trials = 0: totmoves = 0
  Do
   d = m - k: moves = 0
   Do
    If d = 0 Then ch = 3 Else ch = 4
    r = Int(Rnd(1) * ch)
    If r = ch - 4 Then
      dd = -1
    Else
      If r = ch - 1 Then
        dd = 1
      Else
        dd = 0
      End If
    End If
    d = d + dd: moves = moves + 1
    If d = m Then
     totmoves = totmoves + moves
     trials = trials + 1
    End If
   Loop Until d = m
   DoEvents
  Loop Until trials = 100000
  Text1.Text = Text1.Text & totmoves & Str(trials) & "        " & totmoves / trials & crlf
  
   
  Text1.Text = Text1.Text & crlf & " done"
  DoEvents

End Sub


  Posted by Charlie on 2020-03-04 12:34:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information