糊涂蚂蚁 I

按与终点的“层级距离”分组，设：

• $E_0$：从起点（距离 0 层）到终点的期望步数；
• $E_1$：从与起点相邻的顶点（3 个，距离 1 层）的期望步数；
• $E_2$：从与终点相邻的顶点（3 个，距离 2 层）的期望步数；
• $E_3=0$：终点。

转移：

• 起点必到第 1 层：$E_0=1+E_1$。
• 第 1 层：以 $1/3$ 回到起点，以 $2/3$ 去第 2 层：

$$E_1=1+\frac13 E_0+\frac23 E_2.$$

• 第 2 层：以 $1/3$ 到终点，以 $2/3$ 回到第 1 层：

$$E_2=1+\frac23 E_1+\frac13 E_3=1+\frac23 E_1.$$

联立解得 $E_1=9$，因此

$$E_0=1+E_1=10.$$

---

Original Explanation

There are a total of eight vertices: one is the starting vertex denoted $v_0$, three are the vertices adjacent to the starting vertex denoted $v_1$, three are the vertices adjacent to the ending vertex denoted $v_2$, and one is the ending vertex denoted $v_3$. Let $E[v_i]$ be the expected number of edges travelled to arrive at $v_3$ from $v_i$. This problem has now been set up as calculating the expecting hitting time of a state within a Markov chain:

$$E[V_0] = 1 + \frac{1}{3}\times E[V_1] + \frac{1}{3}\times E[V_1] + \frac{1}{3}\times E[V_1]$$ $$E[V_1] = 1 + \frac{1}{3}\times E[V_0] + \frac{1}{3}\times E[V_2] + \frac{1}{3}\times E[V_2]$$