Jump frog, jump!
An infinite line of stepping stones stretches out into an infinitely large lake.
A frog starts on the second stone from the shore.
Every second, he takes a jump to a neighboring stone. He has a 60% chance of jumping one stone closer to the shore and a 40% chance of jumping one stone further away from the shore.
What is the expected value for the number of jumps he will take before reaching the first stone (the one closest to the shore)?
Other Expected Value Quizzes
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
ould you elaborate?
Why E2 = 1 + 0.6E1 + 0.4E3? I thought it should be E2 = 0.6 + 0.4E3 because with 0.6 probability it attains success. Can you please clarify this.
Log in to reply
Well the 1 is because he makes one move, the 0.6E1 is because there is a .6 chance of ending up in state 2, and the 0.4E3 is because there is a 0.4 probability of ending up in state 3.
Make sense?
It is true that with 0.6 probability it attains success. Your equation is almost correct in that E2 = 0.6 + 0.4(E3 + 1) would be a valid way to solve. This is essentially E1 = 0; E2 = 0.6(1 + E1) + 0.4(1 + E3).
The thing your equation is missing is 0.4(E3+1). The 1 is important as we are letting E(X) be the average number of jumps required to move X-1 steps to the right. So to account for all steps, E2 to E3 is 1 step to the left + average number of steps to move two steps to the right, i.e. 1 + E3
This solution is nice, I like it, but it assumes that E_2 is finite, which we don't know in the first place. Is there an easy way to see it? (I see it in a complicated way, I wonder if there is a simple one)
I was able to write down this equation. But I am not able to get the 2nd part of your solution. How did the expected value double?
Log in to reply
So you are wondering how I came up with this?
E 2 = 1 + 0 . 4 ∗ E 3
Log in to reply
No, the part in which you argue that the consecutive expectations would double as we move ahead.
Log in to reply
@Mohit Aneja – So, do you agree that the expected number of jumps to go from 3 to 2 is the same as the expected number of jumps to go from 2 to 1.
Log in to reply
@Geoff Pilling – No. I didn't say that. Whatever the relation between the expected value is, will come from the equations. I just want to know how did you figure it out "intuitively" that the expectation would double?
Although this problem can be solved using states, it can also easily be solved similarly to one of the problems in "Introductory Problem Solving".
The question of "How many jumping events n results in the frog being an expected value of x stones closer to the shore?" can be solved by answering the question "How much closer to the shore is the frog expected to be after n jumping events?" and using the solution of the latter problem to solve the former.
The answer to the latter problem is x= (0.6 (1) + 0.4 (-1))*n = 0.2n stones.
if we set x=1 stone and solve for n, we get n=5.
The closer:further jumping ratio is 60:40 or 3:2.
This gives a net movement of 1 closer per 5 jumps.
Let S n be the position of the frog after n jumps, with S 0 = 2 . Now consider the sequence of random variables X n = S n + 5 n , with the usual filtrations { F n } . We have, E ( X n + 1 ∣ F n ) = S n − 5 1 + 5 n + 1 = X n Also, it is trivial that E ∣ X n ∣ < ∞ . Hence, the sequence of random variables constitute a Martingale Sequence . Define the stopping time τ to be the first time such that S τ = 1 . Hence, using the optional stopping theorem (Condition 2 holds here for the validity of OST), we have E ( X τ ) = E ( X 0 ) = 2 Hence, E ( S τ ) + 5 E ( τ ) = 2 Which yields E ( τ ) = 5 .
Let E n = Expected number of jumps to reach the first stone from the n th stone.
From the second stone he has a 0 . 6 probability of jumping backward (to the first stone) and a 0 . 4 probability of jumping forward (to the third stone). So,
E 2 = 1 + 0 . 6 ∗ E 1 + 0 . 4 ∗ E 3
Since, E 1 = 0 , this becomes,
E 2 = 1 + 0 . 4 ∗ E 3
However, by symmetry, if he gets to the third stone, his expectation value has doubled from when he was on the second stone, since the the expected number of jumps to go from 3 to 2 is the same as the expected number of jumps to go from 2 to 1.
So, E 3 = 2 ∗ E 2 .
Therefore, E 2 = 1 + 0 . 4 ∗ ( 2 E 2 )
Or, E 2 = 5