1
$\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

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.