0
$\begingroup$

Consider a truncated icosahedron with 12 pentagons and 20 hexagons. Starting from a hexagonal face, we go to any neighboring polygon randomly with equal probability. What is the expected number of steps it takes for us to visit the starting hexagon a second time?

I know that this is easily solvable with a Markov Chain, but the question specifically requires little computation, stating that the problem can be finished with just simple mental math. I know the answer to be 30, but I cannot find an elegant way to assert so.

One argument is that since 3/2 is the expected number of steps from one hexagon to another, and there are 20 hexagons, that the answer is simply 3/2 times 20, which is 30. However, this clearly lacks rigor.

$\endgroup$

1 Answer 1

0
$\begingroup$

The symmetry of the Markov chain associated with the random walk enables you to calculate the expected return time fairly easily. The chain has $\ 32\ $ states $\ h_1,h_2,\dots,h_{20},p_1,p_2,\dots,p_{12}\ ,$ where $\ h_i\ $ are the hexagonal faces and $\ p_i\ $ the pentagonal faces. If $\ \pi\ $ is the stationary distribution of the chain, then by symmetry we must have $$ \pi_{h_i}=\pi_{h_j}=\mathfrak{h}\ , $$ say, for all $\ i,j\in\{1,2,\dots,20\}\ ,$ and $$ \pi_{p_i}=\pi_{p_j}=\mathfrak{p}\ , $$ say, for all $\ i,j\in\{1,2,\dots,12\}\ ,$ with $$ 20\mathfrak{h}+12\mathfrak{p}=1 $$ and $$ \mathfrak{h}=\frac{\mathfrak{h}}{2}+\frac{3\mathfrak{p}}{5}\ , $$ because the entry to a hexagon from each of its three adjacent hexagons occurs with probability $\ \frac{1}{6}\ $, and the entry to it from each of its three adjacent pentagons occurs with probability $\ \frac{1}{5}\ $. These solution to these equations is $\ \mathfrak{p}=\frac{1}{36}, \mathfrak{h}=\frac{1}{30}\ .$ It now follows from one of the fundamental theorems of ergodic Markov chains that the expected first passage time from a hexagon to itself is $\ \frac{1}{\mathfrak{h}}=30\ .$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .