Ant walking on an icosahedron (Source: My Own Question. Influenced by 2018 AIME #10)
Let's say we have a regular icosahedron. Say a bug starts on one vertex. Say the bug travels on vertices, going to an adjacent vertex each turn. With 6 turns, what's the probability that the bug ends up on its starting point
I don't have a darn idea how to do this problem. Could anyone help. 
 A: There are four different classes of vertices: the initial vertex, its neighbours, their neighbours, and the opposite vertex. The matrix of transition probabilities (with the classes in that order) is
$$
\frac15\pmatrix{0&1&0&0\\5&2&2&0\\0&2&2&5\\0&0&1&0}\;.
$$
This matrix happens to have a reasonably simple eigensystem. The initial state decomposes as
$$
\pmatrix{1\\0\\0\\0}=\frac1{12}\left(\pmatrix{1\\5\\5\\1}+3\pmatrix{1\\\sqrt5\\-\sqrt5\\-1}+3\pmatrix{1\\-\sqrt5\\\sqrt5\\-1}+5\pmatrix{1\\-1\\-1\\1}\right)
$$
with eigenvalues $5^0$, $5^{-\frac12}$,$-5^{-\frac12}$ and $5^{-1}$, respectively. Thus, after $6$ steps, the components are multiplied by $5^0$, $5^{-3}$, $5^{-3}$ and $5^{-6}$, respectively, and the resulting distribution is
$$
5^{-5}\pmatrix{273\\1302\\1302\\248\\}\;.
$$
Thus, the probability to return to the starting point is $\frac{273}{3125}=\frac1{12}+\frac{151}{37500}\approx\frac1{12}+0.004$.
A: Denote $v_i$ the vertices, $\mathbf{A}$ the adjacency matrix of the corresponding graph and $\mathbf{A}^6=(b_{ij}).$ 
Recall that $b_{ij}$ is the number of paths of length $6$ from $v_i$ to $v_j$.
The probability to return to $v_i$ if the ant started in this same vertex, is $$p_i=\frac{b_{ii}}{\sum_{j=1}^{12}b_{ij}}.$$
