Expected vertex in a tetrahedron The following is taken from this problem sheet for quant interviews

A bug crawls along the edges of a regular tetrahedron ABCD with edges
length 1. It starts at A and at each vertex chooses its next edge at random
(so it has a $1/3$ chance of going back along the edge it came on, and a $1/3$ chance of going along each of the other two). Find the probability that
after it has crawled a distance 7 it is again at A.

Numerical simulations suggest that the answer is $1/4$, but I'm not sure if that's right. On the first step the distribution is $(0,1/3,1/3,1/3)$, and on the second step it is $(1/3,2/9,2/9,2/9)$. I can continue doing this but my interviewer would be bored out of his/her mind! Is there a slick way to do this?
 A: This is a simple example of a Markov chain. The wanted probability is $M_{11}$ where
$$ M = \begin{pmatrix} 0 & \frac{1}{3}& \frac{1}{3}& \frac{1}{3}\\ \frac{1}{3} & 0 & \frac{1}{3}& \frac{1}{3}\\ \frac{1}{3}& \frac{1}{3}& 0& \frac{1}{3}\\ \frac{1}{3}& \frac{1}{3}& \frac{1}{3} & 0\end{pmatrix}^7 $$
hence the answer is $\color{red}{\frac{182}{729}}$, very close to one fourth. If you group together the vertices $B,C,D$ in a single state (this is known as lumping, sometimes) you may check that the wanted probability can be computed as $N_{11}$, too, where:
$$ N = \begin{pmatrix}0 & 1 \\ \frac{1}{3} & \frac{2}{3}\end{pmatrix}^7.$$
Even trickier: since the eigenvalues of the last $2\times 2$ matrix are $1$ (no wonder, it is a stochastic matrix) and $-\frac{1}{3}$, the probability of going from $A$ to $A$ in $n$ steps is
$$ p_n = k_1 + k_2\left(-\frac{1}{3}\right)^n $$
where $p_0=1$ and $\lim_{n\to +\infty}p_n=\frac{1}{4}$, hence the answer is given by
$$ \frac{1}{4}+\frac{3}{4}\left(-\frac{1}{3}\right)^7 = \color{red}{\frac{1}{4}\left(1-\frac{1}{3^6}\right)}.$$
