Ant walking on an icosahedron

probability

(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.

Best Answer

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$.