单纯形上的蚂蚁

设这是一个 $n$-单纯形，并把起点记作原点。除了原点外，还有 $n$ 个其他顶点。

把过程按“已经访问过多少个非原点顶点”来分阶段。若目前已经访问过 $i$ 个非原点顶点，那么下一步走到一个尚未访问的新顶点的概率是 $$\frac{n-i}{n},$$ 因为每次都等概率走向其余 $n$ 个顶点中的任意一个。

因此，从访问了 $i$ 个非原点顶点推进到访问 $i+1$ 个非原点顶点，所需步数的期望是 $$\frac{n}{n-i}.$$

把这些阶段全部加起来：

• 从 0 个推进到 1 个，期望是 $\frac{n}{n}=1$；
• 从 1 个推进到 2 个，期望是 $\frac{n}{n-1}$；
• ……
• 从 $n-1$ 个推进到 $n$ 个，期望是 $\frac{n}{1}=n$。

当所有非原点顶点都访问过之后，还需要回到原点。此时下一步回到原点的概率是 $\frac1n$，所以额外期望步数也是 $n$。

总期望为 $$\frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} + n = n\left(\frac1n + \frac1{n-1} + \cdots + 1 + 1\right) = \boxed{n(H_n+1)}.$$

---

Original Explanation

Suppose the ant is moving on an n-simplex. Then the crucial observation is that we can come up with a Markov chain which moves in a single direction: $$0 \overset{\frac{n}{n}}{\longrightarrow} 1 \overset{\frac{n-1}{n}}{\longrightarrow} 2 \overset{\frac{n-2}{n}}{\longrightarrow} 3 \overset{\frac{n-3}{n}}{\longrightarrow} \quad\cdots\quad \overset{\frac{1}{n}}{\longrightarrow} n \overset{\frac{1}{n}}{\longrightarrow} \texttt{origin}$$

Here are some explanations:

• Each $i=0,1,\ldots,n$ represents the state at which the ant has visited $i$ vertices, not counting the origin.
• The state $\texttt{origin}$ represents the state at which the ant has visited all the stated and is located at the origin. We are interested in the expected hitting time of this state.
• The arrow $i \overset{p}{\longrightarrow} j$ means that the chain jumps from $i$ to $j$ with probability $p$
• Just at the moment the ant has visited all the $n$ vertices (not counting the origin), the location of the ant cannot be the origin. This explains the last transition $n \overset{\frac{1}{n}}{\longrightarrow} \texttt{origin}$

From this, we find that:

• The transition $0 \to 1$ takes $T_{0\to1} = 1$ unit of time
• The transition $1 \to 2$ takes $T_{1\to2} \sim \operatorname{Geometric}\!\left(\frac{n-1}{n}\right)$ unit of time
• The transition $2 \to 3$ takes $T_{2\to3} \sim \operatorname{Geometric}\!\left(\frac{n-2}{n}\right)$ unit of time

and likewise for all the other transitions. So, the expected time from the state $0\text{ to }\texttt{origin}$ is: $$\mathbb{E}[T_{0\to1} + T_{1\to2} + T_{2\to3} + \cdots + T_{(n-1)\to n} + T_{n\to\texttt{origin}}] = \frac{n}{n} + \frac{n}{n-1} + \frac{n}{n-2} + \cdots + \frac{n}{1} + \frac{n}{1},\\ = n\left(\frac{1}{n} + \frac{1}{n-1} + \frac{1}{n-2} + \cdots + 1 + 1\right) = \boxed{n(H_n + 1)}$$