(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} $$
Best Answer
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$.