I recently encountered a quant interview question, which I think is not super hard, but still I am not very sure about my results.
Could you guys give me some hints on it?
The question goes as follows:
An ant is put on a vertex of a simplex, and at each vertex, it has equal probability to move to any other one. Once it goes back to the original start point and also it has visited all the vertices, it stops.
What is the expected number of steps for its move?
The way I did is to consider a 'state', $(n,x)$, where $n$ represents the number of vertices it has visited, and $x$ is a binary represents whether it is at the original or not. It should be a regular Markov Chain.
Therefore, the ant starts at $(1,\text{True})$ state and move to $(2,\text{False})$ state with probability $1$ $\ldots$ $(4,\text{True})$ state is the only absorbing state.
After some calculations, my result is $\mathbf{7}$. I am wondering whether it is correct or not and do you guys have other insights?
Appreciate the community!!!
Edit. I'm sorry. I messed up with the matrix. The correct answer should be $8.5$ from my side.
Best Answer
Sketch of Proof. 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$.
Each loop from $i$ to $i$ itself is omitted from the above diagram, since drawing them is super painful with vanilla MathJax. However, it is easy to recover them from the other arrows.
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}(\frac{n-1}{n})$ unit of time.
The transition $2 \to 3$ takes $T_{2\to3} \sim \operatorname{Geometric}(\frac{n-2}{n})$ unit of time.
and likewise for all the other transitions. So, the expected time from the state $0$ to $\texttt{origin}$ is
\begin{align*} &\mathbf{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) \\ &= n(H_n + 1). \end{align*}