A pawn moves across the fields of the board in the figure below, in each move, moving to one of the fields bordering a side or corner (each of the available fields has the same probability, the choices for different moves are independent). At the initial moment, the pawn is on field A.
a) Calculate the probability that the pawn will return to A before reaching B or C.
b) Calculate the expected value of the number of moves after which the pawn will visit all fields.
The first subproblem is fairly easy. I create a system of equations containing:
- imaginary point A' that is the point where the pawn starts and point A marking pawns return
- point L – that is the 'left one' without label – the one that borders A
- point R – that is the 'right one' without label – the one that borders L, C and B
Here are the equations:
- $p_{A'} = p_L$
- $p_L = \frac{1}{3}p_A + \frac{1}{3}p_R + \frac{1}{3}p_C$
- $p_R = \frac{1}{3}p_L + \frac{1}{3}p_C + \frac{1}{3}p_B$
- $p_A = 1$
- $p_C = 0$
- $p_B = 0$
From that I get: $p_{A'} = \frac{3}{8}$ and that result seams to be pretty sensible.
I have problem solving the second subproblem. I'm not sure how to track the progress in 'visiting all fields'. I know that I can track the number of steps by adding $+1$ to every equation, that way I get. I can write the whole system of possible moves with counting steps like that:
- $p_A = p_L + 1$
- $p_L = \frac{1}{3}p_A + \frac{1}{3}p_R + \frac{1}{3}p_C + 1$
- $p_R = \frac{1}{3}p_L + \frac{1}{3}p_C + \frac{1}{3}p_B + 1$
- $p_C = \frac{1}{3}p_L + \frac{1}{3}p_R + \frac{1}{3}p_B + 1$
- $p_B = \frac{1}{2}p_R + \frac{1}{2}p_C$
But how to tackle the challenge of counting only those steps that lead to new field?
That question is similar to other two that I've asked before (I needed my solution to be verified in those):
Best Answer
Let's call the vertices $1,2,3,4,5$ (left to right, with "5" being C and "1" being A). In the first step, the walker visits both "1" and "2", and then the "interesting" story begins. Once the walk at "2", it takes on average $2$ steps before it jumps to either "3" or "5" (a sort of modified geometric distribution, $\frac23\left(1+3\frac13+5\left(\frac13\right)^2+7\left(\frac13\right)^4+...\right)=2$ using loops $2\to1\to2$.)
You can also notice the symmetry between "3" and "5", so w.l.o.g. assume that after leaving site "2" not to "1", the walker went to "3". It has spent on average $3=1+2$ units of time by now. Let denote the remaining expected time by $x$.
where:
Let
$y$ be the expected remaining time when all sites but "4" are visited and the walker is at "5" (or at "3", which is the same by symmetry) at the moment;
$z$ be the expected remaining time when all sites but "5" are visited and the walker is at "4" at the moment;
$w$ be the expected remaining time when all sites but "5" are visited and the walker is at "3" at the moment.
Then $$ x=1+\frac13\left[2+\frac{x+y}2\right]+\frac13z+\frac13y $$ The three last summands above correspond to steps $3\to2$, $3\to4$ and $3\to5$ respectively.
We also have $$ y=1+\frac13\left[2+y\right]+\frac13y+\frac13\times 0. $$ The three last summands above correspond to steps $5\to2$, $5\to3$ and $5\to4$ respectively.
Similarly, $$ z=1+\frac12 w +\frac12\times 0. $$ (the two last summands above correspond to steps $4\to3$ and $4\to5$ respectively) and $$ w=1+\frac13\left[2+\frac{w+0}2\right]+\frac13z+\frac13\times 0. $$ (corresponding to steps to "2", "4", and "5" respectively).
The solution of this system gives $$ w = 3, \ x = 6,\ y = 5,\ z = 5/2 $$ and the answer is $x+3=9$.