A particle performs a randowm walk on the vertices of a cube. At each step it remains where it is with probability 1/4, or moves to one of its neighbouring vertices each having probability 1/4.
Let A and D be two diametrically opposite vertices. If the walk starts at A, find:
a. The mean number of steps until its first return to A.
b. The mean number of steps until its first visit to D.
c. The mean number of visits to D before its first return to A.
I have solved a & b. Im grouping together the vertices thats one step from A, calling them B, two steps from A, calling them C and then we have D. Then i let $\psi(i, j)$ be the expected number of steps to reach state j from state i, where i,j ={A,B,C,D}.
Then for b, i get these equations
$\psi(A,D) = 1+\frac{1}{4}\psi(A,D)+\frac{3}{4}\psi(B,D)$
$\psi(B,D) = 1+ \frac{1}{4}\psi(B,D)+\frac{1}{4}\psi(A,D)+$
$\frac{1}{2}\psi(C,D)$
$\psi(C,D) = 1+\frac{1}{4}*0+\frac{1}{4}\psi(C,D)+\frac{1}{2}\psi(B,D)$
and i solve the system to find $\psi(A,D)$
Question: I cant figure out how to solve part c though.
Best Answer
The critical thing to figure is the probability $p$ it gets to D before it returns to A. Then you have a Markov chain with states $A,D$ and probabilities $p$ for $A \to D$ and $D \to A$ and $1-p$ for $D \to D$ and $A \to A$