A frog hops along the number line according to the following rules:
- It starts at 0.
- If it is at 0, then it moves to 1 with probability 21 and disappears with probability 21.
- For n=1,2,3, if it is at n, then it moves to n+1 with probability 41, to n−1 with probability 41, and disappears with probability 21.
What is the probability that the frog reaches 4?
Answer Choices:
A. 1011
B. 1001
C. 991
D. 981
E. 971
💬 Join the Discussion
Stuck on this problem or want to share your approach?
Continue the conversation and see what others are thinking: View Forum Thread
Let pn be the probability that the frog eventually reaches 4 given that it starts at position n.
Once the frog reaches 4, we are done, so
p4=1.
From 0, the frog either moves to 1 with probability 21 or disappears with probability 21:
p0=21p1+21⋅0=21p1.
For n=1,2,3, from position n the frog moves to n+1 with probability 41, to n−1 with probability 41, and disappears with probability 21, so
pn=41pn+1+41pn−1+21⋅0=41(pn+1+pn−1).
Writing these explicitly for n=1,2,3 and using p4=1 gives
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧p0p1p2p3=21p1,=41(p2+p0),=41(p3+p1),=41(p4+p2)=41(1+p2).
From p0=21p1 we have
p0=21p1.
Substitute into the equation for p1:
p1=41(p2+21p1)⟹4p1=p2+21p1⟹8p1=2p2+p1.
Thus
7p1=2p2⟹p2=27p1.
Use p2 in the equation for p2:
p2=41(p3+p1)⟹4p2=p3+p1.
Substitute p2=27p1:
4⋅27p1=p3+p1⟹14p1=p3+p1⟹p3=13p1.
Now use the equation for p3:
p3=41(1+p2)⟹4p3=1+p2.
Substitute p3=13p1 and p2=27p1:
4⋅13p1=1+27p1⟹52p1=1+27p1.
We can further simplify with
2104p1=1+27p1⟹(2104−27)p1=1⟹297p1=1.
Hence
p1=972.
Finally, from p0=21p1,
p0=21⋅972=971.
Therefore, the probability that the frog reaches 4 is
(E) 971
Alternate Solution (using a transition table / Markov chain).
We model the frog as a Markov chain with the following states:
0,1,2,3,4,D,
where D is a "dead" state (the frog disappeared). We treat 4 and D as absorbing states: once the frog reaches 4 or disappears, it stays there forever for the purposes of this problem.
From the rules of the problem, the one-step transition probabilities are:
From\To01234D004100001210410002041041003004100040004110D2121212101
Let pn be the probability that the frog is eventually absorbed in state 4 (i.e., eventually reaches 4) given that it starts in state n.
For the absorbing states:
p4=1,pD=0.
For a non-absorbing state n, the Markov property gives
pn=states s∑P(go from n to s in one step)⋅ps.
Using the rows of the transition table:
- From 0: it goes to 1 with probability 21 and to D with probability 21:
p0=21p1+21pD=21p1.
- From 1: it goes to 0 with probability 41, to 2 with probability 41, and to D with probability 21:
p1=41p0+41p2+21pD=41(p0+p2).
p2=41p1+41p3.
- From 3: it goes to 2 with probability 41, to 4 with probability 41, and to D with probability 21:
p3=41p2+41p4+21pD=41p2+41.
Thus, we again obtain the system
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧p0p1p2p3=21p1,=41(p0+p2),=41(p1+p3),=41(p2+1).
We can regard this as a linear system coming from the transition table, and solve it systematically (for example, by substitution as in Solution 1, or by Gaussian elimination on the augmented matrix). Solving yields
p0=971.
Therefore, by the table/Markov-chain method as well, the probability that the frog reaches 4 is
(E) 971
The problems on this page are the property of the MAA's American Mathematics Competitions