Probability an ant returns to its starting vertex on an octahedron after $6$ moves

Question

I've seen several problems of the form:

An ant is on a vertex of a $n$-sided regular polyhedron. The probability that the ant returns back to their original position after $m$ moves can be expressed in the form $ \frac {p}{q}$, find the value of $p + q$. (A move from one vertex to an adjacent vertex.)

The only way I've thought of is manually evaluated all of the cases, but I'm sure there's a more efficient method. So for example, let's take a case where we have an octahedron and $6$ moves available for the ant, how would you be able to solve that?

Answer 1

For this problem there are just three states: In state $S_1$ the ant sits at the starting position, in state $S_2$ the ant sits on one of the four adjacent positions, and in state $S_3$ the ant sits at the vertex opposite to the starting vertex. Denote by $${\bf p}(n)=\left[\matrix{p_1(n)\cr p_2(n)\cr p_3(n)\cr}\right]\qquad(n\geq0)$$ the probabilities that after $n\geq0$ steps the ant is in state $S_i$ $\>(1\leq i\leq3)$. Then ${\bf p}(0)=(1,0,0)$. The rules of the game then say that $${\bf p}(n+1)=A\>{\bf p}(n)\qquad(n\geq0)$$ with $$A:=\left[\matrix{0&{1\over4}&0\cr 1&{1\over2}&1\cr0&{1\over4}&0\cr}\right]\ .$$ This is the essential step. E.g., the second column of $A$: When the ant is in state $S_2$ then it will move to state $S_1$ with probability ${1\over4}$, remain in state $S_2$ with probability ${1\over2}$, and move to state $S_3$ with probability ${1\over4}$. We now have to compute $p_1(6)$, which is the first component of $$A^{6}\left[\matrix{1\cr0\cr0\cr}\right]=\left[\matrix{{11\over64}\cr{21\over32}\cr{11\over64}\cr}\right]\ .$$

Answer 2

There is a simple standard method to mechanically ensure you consider all cases. This is the transition matrix $T$: $T_{i,j}$ is the probability of moving from state $i$ to state $j$. A bit of thought should show that $T^2$ describe probabilities of moving from one state to another after 2 steps. The matrix product rule sums up all paths that can lead from one state to another through all intermediate steps, according to the combined probability.

In symbols: \begin{equation} T^2_{i,j} = \sum_{k} T_{i,k} T_{k,j} \end{equation} which is exactly what we want.

This immediately extends to the powers of $T$, $T^n$ giving the probabilities after $n$ steps.

You can make this process more efficient by consolidating equivalent cases. On an octahedron, there are six vertices, but only three cases: the starting vertex (call this the north pole), any of the four vertices that are one hop away (call this the equator), and the vertex directly opposite the starting vertex. It doesn't matter exactly where you are, only how far away from the starting point you are.

You can then construct the transition matrix:

\begin{equation} T = \begin{pmatrix} 0 & 1 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1 & 0 \end{pmatrix} \end{equation} and the sixth power is: \begin{equation} T^6 = \begin{pmatrix} 704 & 2688 & 704 \\ 672 & 2752 & 672 \\ 704 & 2688 & 704 \end{pmatrix} / 4^6 = \begin{pmatrix} 22 & 84 & 22 \\ 211 & 86 & 211 \\ 22 & 84 & 22 \end{pmatrix} / 2^7 \end{equation}

22 / 2^7 = 11 / 2^6 = 11 / 64. (Note that this is just barely over the naive "well mixed" answer of 1/6, which is a good check that no mistakes were made).

Answer 3

This is a solution closely related to that from @ChristianBlatter.

Here's an octahedron:

Here is its graph (edges connect vertices on the octahedron):

Here's its adjacency matrix:

$${\bf M} = \left( \begin{array}{cccccc} 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ \end{array} \right)$$

Here is ${\bf M}^6$

$$\left( \begin{array}{cccccc} 704 & 672 & 672 & 672 & 672 & 704 \\ 672 & 704 & 672 & 704 & 672 & 672 \\ 672 & 672 & 704 & 672 & 704 & 672 \\ 672 & 704 & 672 & 704 & 672 & 672 \\ 672 & 672 & 704 & 672 & 704 & 672 \\ 704 & 672 & 672 & 672 & 672 & 704 \\ \end{array} \right)$$

Here is ${\bf M}^6 (1,0,0,0,0,0)^t$:

$$\left( \begin{array}{c} 704 \\ 672 \\ 672 \\ 672 \\ 672 \\ 704 \\ \end{array} \right)$$

So the probability the ant is at his starting point is $\frac{704}{2 \cdot 704 + 4 \cdot 672} = \frac{11}{64}$.

It is a nice confirmation to see that the probability the ant is on the opposite vertex is the same... as a consideration of symmetry shows.

---

In case anyone wants the components of the Mathematica code:

Graphics3D[{Opacity[.5], LightBlue, EdgeForm[Gray], 
  PolyhedronData["Octahedron", "Faces", "Polygon"]}]

rr=(Graph[UndirectedEdge @@@ 
      PolyhedronData[#, "AdjacentFaceIndices"]] & /@ 
   PolyhedronData["Platonic"])[[1]]

MatrixForm[ppp = AdjacencyMatrix[rr]]

MatrixForm[MatrixPower[ppp,6]]

MatrixForm[MatrixPower[ppp,6].{1,0,0,0,0,0}]

This approach generalizes trivially to arbitrarily complex polyhedra and arbitrary number of steps (where one step is along an edge of any length). Thus one can easily find the probability the ant is on any given vertex after 15947 steps on this Great Rhombic Triacontahedron:

Of course now it depends which vertex the ant starts on.