An ant is initially at some vertex of a cube. The ant can only traverse along the edge of the cube. The ant has a probability of 0.25 of staying at the same vertex. It has a 0.75 probability of going to 1 of the 3 adjacent vertices, with equal probability. What is the expected number of steps it will take for the ant to return to the initial vertex? If the ant stays at the same vertex, that also exhausts 1 step.
So first, the problem does not state whether a "return" can be from the initial vertex, i.e., the ant is sitting at the initial vertex and with probability 0.25, it doesn't move, and we're done. I decided to assume that this does not entail a return. In other words, I assumed that the ant must move to some other vertex before returning to the initial vertex.
To solve this problem, I took advantage of symmetry and used Markov chains. The symmetry condition relies on the fact that there are 3 unique distances away from the initial vertex: 1,2,3. So instead of representing all 7 corners, we reduce this down to 3 states.
We have an additional state, which is the initial state, and we have the absorbing state, which is when the ant returns.
So the 5 states are:
state 0) Final (absorbing) state
state 1) Initial state
state 2) Distance 1 away from initial state
state 3) Distance 2 away from initial state
state 4) Distance 3 away from initial state
The transition probability matrix is
\begin{align}
\begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
0 & 0.25 & 0.75 & 0 & 0 \\
0.25 & 0 & 0.25 & 0.50 & 0 \\
0 & 0 & 0.50 & 0.25 & 0.25 \\
0 & 0 & 0 & 0.75 & 0.25
\end{bmatrix} \\
\end{align}
Let $\mu_i$ represent the expected number of steps it takes to go from state state i to state 0.
Then we find that $\mu_1 = 10\frac{2}{3}$ (work shown below). When I simulated this with monte carlo, I obtain 12 steps. I double checked my analytical work and don't see an error. Could some else solve this problem and let me know what they get?
Work:
\begin{align}
\mu_4 = 1 + 0.25\mu_4 + 0.75\mu_3 \\
0.75\mu_4 = 1 + 0.75\mu_3 \\
\mu_4 = \frac{4}{3} + \mu_3 \\
\mu_3 = 1 + 0.50\mu_2 + 0.25\mu_3 + 0.25\mu_4 \\
\mu_3 = 1 + 0.50\mu_2 + 0.25\mu_3 + 0.25 \left(\frac{4}{3} + \mu_3 \right) \\
\mu_3 = 1 + 0.50\mu_2 + 0.25\mu_3 + \frac{1}{3} + \frac{1}{4}\mu_3\\
\mu_3 = \frac{4}{3} + 0.50\mu_2 + 0.5\mu_3 \\
\mu_3 = \frac{8}{3} + \mu_2\\
\mu_2 = 1 + 0.25\mu_2 + 0.5\mu_3\\
\mu_2 = 4/3 + 2/3\mu_3\\
\mu_2 = 4/3 + 2/3(8/3 + \mu_2)\\
\mu_2 = 4/3 + 16/9 + 2/3\mu_2\\
\mu_2 = 4 + 16/3 \\
\mu_1 = 1 + 0.25\mu_1 + 0.75\mu_2 = 1 + 0.25\mu_1 + 0.75(4 + 16/3) \\
\mu_1 = 10\frac{2}{3}
\end{align}
Best Answer
I agree with that answer.
To see it in a (somewhat) different way, note that there are only $4$ types of vertices. Type $0$ is the start, type $1$ are the three vertices a distance one from the start, type $2$ are the three vertices a distance two from the start, and type $3$ is the single vertex a distance three from the start. For $i\in \{1,2,3\}$ we let $E_i$ denote the expected number of steps to get to the Start. $E=E_0$ is the desired answer and we note that $$E=E_1+\frac 43$$
We easily see that $$E_1=.25\times (E_1+1)+.25\times (1)+.5\times (E_2+1)$$ $$E_2=.25\times (E_2+1_+.5\times (E_1+1)+.25\times (E_3+1)$$ $$E_3=.25\times (E_3+1)+.75\times (E_2+1)$$
This is easily solved and yields $E_1=\frac {28}{3}$ which implies that $E=\frac {32}3$, confirming your result.