Random Walk on a Cube 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.
 A: 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$
A: I have a solution for this problem now. Write 
$$E[D_{AA}], E[D_{BA}], E[D_{CA}], E[D_{DA}]$$ 
for the mean number of visits to D before next visit to A when starting at A, B, C and D, respectively.
$$E[D_{AA}] = (1/4) · 0 + (3/4) · E[D_{BA}]$$
$$E[D_{BA}] = (1/4) · 0 + (1/4) · E[D_{BA}] + (1/2) · E[D_{CA}]$$
$$E[D_{CA}] = (1/2) · E[D_{BA}] + (1/4) · E[D_{CA}] + (1/4) · (E[D_{DA}]+ 1)$$
$$E[D_{DA}] = (3/4) · E[D_{CA}] + (1/4) · (E[D_{DA}]+ 1)$$
with solution $E[D_{AA}] = 1$
A: I think this problem is more natural to solve if you think in terms of invariant measures:
a) The invariant measure can be found from $\pi P = \pi$. However, we know that $\displaystyle \lim_{n \rightarrow \infty} p^n = \pi$.  And in this case, we can see that all vertices are equally likely when you go to infinity. So we have that the invariant measure is: $\pi_A = \frac{1}{8}, \pi_B = \frac{3}{8}, \pi_C = \frac{3}{8}, \pi_D = \frac{1}{8}$.
The return time is nothing but $m_A = \frac{1}{\pi_A}$.  
Therefore the return time is: $m_A = \frac{1}{1/8} = 8$
b) I don't see how I can use the invariant measure for this. So I'll leave it alone.
c) Define the $\textit{expected time spent in i between visits to A}$ as: 
$\gamma_i^A = \mathbb{E}\displaystyle \sum_{n=0}^{T_A - 1}\mathbb{1}_{\{X_n = i\}}$. Where $T_A$ is the first passage time back to A.
Using the theorem 1.7.6 from the book Markov Chains by J.R. Norris, which I will enunciate here without proof:
"Let $P$ be irreducible and let $\lambda$ be an invariant measure for $P$ with $\lambda_A = 1$. Then $\lambda \geq \gamma^A$. If in addition $P$ is recurrent, then $\lambda = \gamma^A$". 
(Here $\lambda_A = 1$ is just a way to say that when you come back it counts as 1 unit of time spent in A)
Our chain is irreducible and recurrent. And we also found an invariant measure $(1/8, 3/8, 3/8, 1/8)$ in numeral a; we know that any multiple of this measure will satisty the equation $\pi P = \pi$. In particular $(1,3,3,1)$ is another invariant measure with the property $\lambda_A^A = 1$. 
Therefore we can say that $\gamma_A^A =1, \gamma_B^A =3, \gamma_C^A =3$ and in particular we can say:
$\gamma_D^A =1$. Which is the final answer.
