A Frog is at C. The purple numbers are the probability that the frog jumps in that direction when it is at certain place. The frog stops at A or E. What is the probability that the frog stops at A?
Good Luck!
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
1
It's easy to see by transforming the problem into a symmetric one - instead of a 1/3 vs. 2/3 jump to B or D, make a third branch so it's a uniform 1/3 chance of going to B, D, or D' (which in turn has a 50-50 chance of ending on E' or going back to C). The frog now has three identical branches with identical transition probabilities, and only one ends on A, so by symmetry it must have probability
1/3.
$\begingroup$
$\endgroup$
3
The answer is
1/3
because
The second jump returns to C half of the time, regardless of the first jump. And returning to C is like restarting the game. We might as well ignore all moves that return to C after leaving C.
So, the last time at C, either the frog jumps to B (prob. 1/3) then A, or it jumps to D (prob. 2/3) then E. Clearly the frog stops at A with probability 1/3.
note
Note that the argument is a bit delicate. It is not just the fact that the frog returns to C that resets the game in a way that the moves before can be ignored. It is the fact that it returns to C with the same probability regardless of whether it started left or right.
-
$\begingroup$ Nice, I never thought of that! $\endgroup$ Commented Sep 24, 2023 at 13:57
-
$\begingroup$ Small elaboration: consider throwing (B or D) dice before C dice (NOTE: must be P(B)=P(D)), - if it is 'back', we are don't need P(C), and can forget the history, so, can stick (B or D) to 'escape', reducing all action to single C test. $\endgroup$ Commented Sep 25, 2023 at 14:31
-
$\begingroup$ Yes, that makes the argument more obvious. $\endgroup$ Commented Sep 25, 2023 at 14:35
$\begingroup$
$\endgroup$
1
Let's make every state in the game worth an amount of money to be in:
A B C D E
$6 $4 $2 $1 $0
With the way that the prices are chosen,
Every time that the frog jumps, the expected change in money value is 0. (For example, from state C, the frog has a 1/3 chance to win 2 dollars and a 2/3 chance to lose 1 dollar). Going from right to left, setting E to \$0 and D to \$1, it is easy to determine what the prices of C, B, and A must be for this to hold.
The frog starts the game with \$2, and ends the game with either \$6 or \$0.
Because each jump is fair, the overall game is fair, so the expected amount of money the frog has at the end must be \$2: the amount it has at the start. Therefore the probability of having \$6 must be 1/3.
-
$\begingroup$ This is an interesting way to explain it! $\endgroup$– justhalfCommented Sep 25, 2023 at 8:51
$\begingroup$
$\endgroup$
The transition probability matrix is $$ P = \begin{pmatrix} 1& 0& 0& 0& 0\\ 1/2& 0& 1/2& 0& 0\\ 0& 1/3& 0& 2/3& 0\\ 0& 0& 1/2& 0& 1/2\\ 0& 0& 0& 0& 1\\ \end{pmatrix}. $$ Let $x_i$ be the desired absorption probability into state $A$, starting from state $i$. The recurrence is $$ x_i = \begin{cases} 1 & \text{if $i=A$}, \\ 0 & \text{if $i=E$}, \\ \sum_j P_{ij} x_j & \text{otherwise}. \\ \end{cases} $$ The solution is
$$x=(1,2/3,1/3,1/6,0).$$
In particular,
$$x_C=1/3.$$
$\begingroup$
$\endgroup$
Let $p$ be the probability that a frog standing on C ultimately reaches A, as required.
This probability $p$ will therefore apply both to a frog starting out its journey, and to a frog who has returned to C - effectively restarting their journey.
In order to reach A, the frog can:
- visit B and then A directly, or,
- visit B and then return to C [and later reach A], or,
- visit D and then return to C.
As such:
$p = \frac{1}{3}\frac{1}{2} + \frac{1}{3}\frac{1}{2}p + \frac{2}{3}\frac{1}{2}p$
Giving a linear equation resulting in:
$p = \frac{1}{3}$
$\begingroup$
$\endgroup$
Consider the set $S$ of all paths from $C$ to $A$, where a path is represented by a concatenation of $B$, $C$, and $D$ ending with $A$. For instance, $BCDCBA$ represents the path $C->B->C->D->C->B->A$.
So we can solve by considering that:
$S$ can be decomposed into $BCS \cup DCS \cup \{BA\}$. The probability of a path ending in $A$ is the sum of all the probabilities of paths in $S$ according to its decomposition.
Then:
$$P_{A}=\sum_{s\in S}{Prob(s)}$$ $$=\sum_{t\in BCS}{Prob(t)}+\sum_{t\in DCS}{Prob(t)}+Prob(BA)$$ $$=\sum_{s\in S}{Prob(BCS)}+\sum_{s\in S}{Prob(DCs)}+Prob(BA)$$ $$=\sum_{s\in S}(1/6){Prob(s)}+\sum_{s\in S}(1/3){Prob(s)}+(1/6)$$ $$P_{A}=(1/6)P_{A} +(1/3)P_{A}+(1/6)$$ $$P_{A}=1/3$$
$\begingroup$
$\endgroup$
3
This already has a solution but for the sake of variety, here's a numerical solution in Google Sheets (also applicable to Excel).
Numerical solution 1: Trace from A to C
| A | B | C | D | E |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 |
| 1 | =1/2 * A1 + 1/2 * C1 | =1/3 * B1 + 2/3 * D1 | =1/2 * C1 | 0 |
Then drag row 2 down, to fill rows 3-20. Each row is a step. After about step 18 it should converge on the value 0.33 for C, which is your answer.
Numerical solution 2: Trace from C to A (this is an alternative suggested by @Florian F) Calculates the probability of each position after each step
| A | B | C | D | E |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| =A1 + 1/2 * B1 | =1/3 * C1 | =1/2 * B1 + 1/2 * D1 | =2/3 * C1 | =E1 + 1/2 * D1 |
As before, drag row 2 down, to fill rows 3-20. For this alternative solution, the answer 0.33 is given in column A.
-
$\begingroup$ Funny, I would have started with a 1 in C and computed the probability of each position after each step. The formulas are then less obvious I have to admit. $\endgroup$ Commented Sep 25, 2023 at 15:35
-
$\begingroup$ It's crazy how many different approaches there are to this problem, looking at some of the other answers they are quite diverse. $\endgroup$ Commented Sep 26, 2023 at 0:00
-
$\begingroup$ I've implemented your solution alongside mine. It looks like it's the exact inverse, with the data flowing in the opposite direction, from C to A. $\endgroup$ Commented Sep 26, 2023 at 0:19
$\begingroup$
$\endgroup$
The probability that the frog stops at A after two jumps is $\frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$.
The probability that the frog lands at C after two jumps is $\frac{1}{2}$ because no matter whether the first jump is to the left or to the right, there is a 50% chance that the frog will return to C on its second jump.
The frog can stop at A after four jumps if after two jumps it has landed at C and then it jumps twice towards A.
Therefore, the probability that the frog stops at A after four jumps is $\frac{1}{2} \times \frac{1}{3} \times \frac{1}{2} = \frac{1}{12}$.
Similarly, the probability that the frog stops at A after six jumps is $\frac{1}{2} \times \frac{1}{2} \times \frac{1}{3} \times \frac{1}{2} = \frac{1}{24}$.
So the probability that the frog will eventually stop at A (after $2, 4, 6, 8, \dots$ jumps) is:
$$\frac{1}{6} + \frac{1}{12} + \frac{1}{24} + \dots$$
The above probability is an infinite geometric series with an initial term of $\frac{1}{6}$ and a common ratio of $\frac{1}{2}$ and has a sum of:
$$\frac{ \frac{1}{6} }{ 1-\frac{1}{2} } = \frac{1}{3}$$
answered Sep 26, 2023 at 8:51