Random Walk on a Cube

Question

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.

Answer 1

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$

Answer 2

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$

Answer 3

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.