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.
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 |
analysis and simulation
