What is wrong with this answer to: expected time of return to origin in random walk on edges of a cube

Question

(Quant Job interviews Questions and Answers Q3.22)

Suppose we have an ant travelling on edges of a cube going from one vertex to the other. The ant never stops and it takes it one minute to go along one edge. At every vertex the ant randomly picks one of the three available edges and starts going along that edge. We pick a vertex of the cube and puts the and there. What is the expected number of minutes that it will take to treturn to that vertex?

Reading up on this it seems I need to learn about Markov chains to answer this properly, however for now here is my incorrect attempt : please could you tell me why it is incorrect ?

Assuming 'randomly' means uniformly with $p=\frac{1}{3}$ , and observing that returning to the vertex must take an even number of steps then by brute force: $$ \mathbb E (T) = \sum_{n=1}^{\infty} 2n * (\frac{1}{3})^{2n} = 2 \sum_{n=1}^{\infty} n* (\frac{1}{9})^{n} = 2 \frac{1\over9}{({1-{1\over9}})^2} = {9 \over 4} $$

Answer 1

Look at the distance from the origin after an even number $2k$ of minutes. This distance can only be 0 or 2. In two minutes the ant can do the following :

$0 \rightarrow 1 \rightarrow 0$ with probability $1\cdot1/3$

$0 \rightarrow 1 \rightarrow 2$ with probability $1\cdot2/3$

$2 \rightarrow 1 \rightarrow 0$ with probability $2/3\cdot1/3$

$2 \rightarrow 3 \rightarrow 2$ with probability $1/3\cdot1$

$2 \rightarrow 1 \rightarrow 2$ with probability $2/3\cdot2/3$

The probability of going from distance 2 to distance 2 in 2 minutes without passing the start vertex is then $7/9$.

The probability of returning after $2k$ minutes is then

$p_{2}=1/3 $

$p_{2k}=\frac{2}{3}\cdot\left(\frac{7}{9}\right)^{k-2}\cdot\frac{2}{9}$ when $k\geq2$, we can check that these actually sum to 1.

The expectation time to return to the origin is then $$ E(T) = \frac{2}{3} +\sum_{k=2}^{\infty}\frac{8k}{27}\left( \frac{7}{9}\right)^{k-2} = 8 $$

Answer 2

To model this as a Markov chain, let $$S=\{(0,0,0),(0,1,0),(0,0,1),(0,1,1),(1,0,0),(1,1,0),(1,0,1),(1,1,1)\}$$ and $P$ an $8\times8$ matrix with $P_{ij}=\frac13$ if $i$ and $j$ vary in exactly one digit, $0$ otherwise. Let $\{X_n:n\geqslant 0\}$ satisfy $$\mathbb P(X_{n+1}=j\mid X_0=i_1, \ldots, X_{n-1}=i_{n-1},X_n=i)=\mathbb P(X_{n+1}\mid X_n=i)=P_{ij}. $$ Then $\{X_n:n\geqslant 0\}$ is a Markov chain, and by symmetry, both the rows and columns of $P$ sum to $1$. Since $S$ is finite, $X$ has the unique stationary distribution $\pi$ being the uniform distribution over $S$ (i.e. $\pi_i = \frac18$ for each $i\in S$). Let $$\tau_{ij} = \inf\{n>0:X_n=j\mid X_0=i\} $$ for each $i,j\in S$. It is known that $$\mathbb E[\tau_{ii}] = \frac1{\mathbb\pi_i}, $$ so in this case the expected number of minutes to return to a vertex would be $8$.