糊涂蚂蚁 II

这是一个在 8 个顶点上的 3-正则图随机游走。

该链的平稳分布是均匀分布（正则图），即每个顶点平稳概率为 $1/8$。

马尔可夫链性质：从状态 $i$ 出发回到 $i$ 的期望回返时间等于 $1/\pi_i$。

因此期望回返步数为

$$\frac{1}{1/8}=8.$$

---

Original Explanation

This seems like a very complicated problem on the surface but you can actually use Markov Chains to solve this problem. There is a lot of symmetry in cubes to help us decrease the number of states involved in this question. Let’s let your starting state be $E_{00}$.

No matter which way the ant goes, by symmetry it’ll basically always be the same position. That position being 1 side length away from the starting vertex. Let's denote the expected number of moves to get back to the initial vertex as $E_{1}$. Thus $E_{00} = E_{1} + 1$.

Let $E_{2}$ be the expected number of moves from being in the state of 2 side lengths away from the starting vertex. Finally, let $E_{3}$ be the expected moves from being at the opposite vertex of the starting vertex. The equations for all these states are:

$$\begin{align*} E_{00} & = E_{1} + 1 \\ E_{1} & = \frac{2}{3}E_{2} + \frac{1}{3}E_{0} + 1 \\ E_{2} & = \frac{2}{3}E_{1} + \frac{1}{3}E_{3} + 1 \\ E_{3} & = E_{2} + 1 \\ \end{align*}$$

We know that $E_{0} = 0$. Solving all of these equations, we get $E_{00} = 8$. Thus it takes 8 steps for the ant to start at one vertex of the cube and return to it.