"A flea hops randomly on the vertices of a triangle with vertices labeled 1,2 and 3, hopping to each of the other vertices with equal probability. If the flea starts at vertex 1, find the probability that after n hops the flea is back to vertex 1."
Could someone provide a hint to help me start this?
After hop $i$, if the flea is at vertex $1$, then it has $0$ probability to be at vertex $1$ next; if the flea is not at vertex $1$, then it has $0.5$ probability to be at vertex $1$ next.
Let $p_i$ be the probability of the flea at vertex $1$ after $i$ hops, and $q_i = 1-p_i$.
$$\begin{align*} \begin{pmatrix}p_{i}\\q_{i}\end{pmatrix} &= \begin{pmatrix}0&0.5\\1&0.5\end{pmatrix}\begin{pmatrix}p_{i-1}\\q_{i-1}\end{pmatrix}\\ \begin{pmatrix}p_0\\q_0\end{pmatrix} &= \begin{pmatrix}1\\0\end{pmatrix} \end{align*}$$
Then simplifying the recurrence, for example with eigendecomposition, $$\begin{align*} \begin{pmatrix}p_n\\q_n\end{pmatrix} &= \begin{pmatrix}0&0.5\\1&0.5\end{pmatrix} \begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix}\\ &= \begin{pmatrix}1&1\\-1&2\end{pmatrix} \begin{pmatrix}-0.5&0\\0&1\end{pmatrix} \begin{pmatrix}1&1\\-1&2\end{pmatrix}^{-1} \begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix}\\ &\vdots\\ &= \begin{pmatrix}1&1\\-1&2\end{pmatrix} \begin{pmatrix}-0.5&0\\0&1\end{pmatrix}^n \begin{pmatrix}1&1\\-1&2\end{pmatrix}^{-1} \begin{pmatrix}p_0\\q_0\end{pmatrix}\\ &= \frac13 \begin{pmatrix}1&1\\-1&2\end{pmatrix} \begin{pmatrix}(-0.5)^n&0\\0&1^n\end{pmatrix} \begin{pmatrix}2&-1\\1&1\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}\\ &= \frac13 \begin{pmatrix}(-0.5)^n&1\\-(-0.5)^n&2\end{pmatrix} \begin{pmatrix}2&-1\\1&1\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}\\ &= \frac13 \begin{pmatrix}2(-0.5)^n+1&-(-0.5)^n+1\\-2(-0.5)^n+2&(-0.5)^n+2\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}\\ &= \frac13 \begin{pmatrix}2(-0.5)^n+1\\-2(-0.5)^n+2\end{pmatrix}\\ p_n &= \frac13 + \frac23\cdot\frac1{(-2)^n} \end{align*}$$