Ant on a Simplex problem, expected number

Question

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.

Answer 1

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*}

Answer 2

A brief note on simplification

This question is related to the harmonic numbers because it can be formulated as a version of the coupon collector problem.

Indeed, this is how it would work. The "graph" of the $n$-simplex, when you treat each of the corners as vertices and each of the edges joining the vertices as graph edges, is in fact an $n+1$-clique : a graph with $n+1$ vertices, in which every possible edge exists. For example, in a tetrahedron, every corner is connected to another one via an edge.

The advantage that this symmetry afford us is that, remarkably, it actually allows us to eliminate the "original" coordinate from your Markov chain.

Here's why. Let us phrase everything in terms of the Markov chain given just by the random walk part (so you forget whether you are at the "original" vertex or not). You start from a vertex, get to every other vertex, and then return to the original vertex.

We break this up into two key steps.

• Visiting every other vertex starting from the original.

• Once you are at the vertex that was visited last, then you need to return to the original vertex.

Now, let $\tau$ be the stopping time in question i.e. that you visit every vertex and then return to the original vertex. Let $\tau_c$ be the time taken only to visit every vertex, and not to return. Let $\tau_d$ be the time taken to return from the last vertex to the original vertex.

By the symmetry of the situation, we are afforded the following facts.

• The choice of original vertex does not matter because the graph is so symmetric!

• The time $\tau_c$ is actually equivalent to the coupon-collector problem on $n$ coupons, but you cannot pick the coupon you picked previously, so that is a small tweak that needs to be added.

• Once you complete $\tau_c$ and visit every vertex, the distribution of the "last" vertex is in fact uniform over all points other than the original point. So, $\tau_d$ becomes the answer to the following question : given a point uniformly picked from all the vertices, what is the expected time for this to return to the original vertex?

• Finally, $\tau_d$ is dependent only upon the Markov chain's values once $\tau_c$ occurs, and therefore by the strong Markov property, $\tau_d$ doesn't really depend on $\tau_c$.

---

Notation and geometric claim

Let's put all this into some notation now. Let $U$ be the uniform distribution on the vertices. It is clear that $U$ is a (the) stationary distribution for the Markov chain given purely by the random walk on the vertices of the $n$-simplex.

Let $X_n$ denote this random walk on the vertex set $V$ and for $f : V \to \mathbb R$ write $\mathbb E_U[f]$ for the expectation of $f$ under the uniform distribution.

Claim : Suppose that $X_0 \sim U$ (the original vertex is uniformly randomly chosen) , then $X_{\tau_c} \sim U$ (the "last visited vertex" is also uniformly distributed!).

The proof is quite easy, and is done using the idea of "transitivity" or using the symmetry of the geometric figure that is the $n$-simplex. Observe that $\mathbb P(X_{\tau_c} = y | X_0 = x) = \sum_{p \in P_{x,y}} \mathbb P(p | X_0 = x)$, where

• $P_{x,y}$ is the set of all paths from $x$ to $y$ which start at $x$ and visit every other vertex before visiting and ending at $y$, and

• $\mathbb P(p | X_0 = x)$ is the probability that the Markov chain follows exactly the path $p$ (at least) starting from $X_0 = x$. (Note that there are infinitely many such paths $p$ so the sum is infinite, but we can still work things out by truncating the sum to paths of length $\leq N$ and then letting $N \to \infty$, something that I'll leave a keen reader to fill in).

Here's an important thing to keep in mind : $\mathbb P(p | X_0 =x)$ depends only on the length of $p$ because every element of the transition matrix that isn't equal to $0$ is equal to $\frac 1n$, so that $\mathbb P(p | X_0 = x) = \frac 1{n^{|p|}}$ where $|p|$ is the number of edges in $p$.

Let $y' \neq y, y' \neq x$ be another possible last vertex. We will show that there is a bijection between $P_{x,y}$ and $P_{x,y'}$.

How? Well, we will show a hidden bijection within the simplex itself, and this will transfer onto a bijection between the paths.

Within an $n$-simplex, imagine any three vertices $a,b,c$. Suppose that you "hold" only the vertex $a$ in your hand, with the rest of the vertices jutting out. (You'll need to only imagine this for $2$ and $3$ dimensional simplices, the rest will be similar). Then, you can "rotate" the simplex in your hand, like a fan, and what this does is : it gives you a new orientation of the simplex, but $a$ remains $a$ while every other vertex goes to a different vertex.

For example, imagine keeping a triangle in your hand, holding a vertex and then flipping the triangle about that vertex. Or holding one vertex of a tetrahedron and then rotating about it, so that all other vertices change position except this one.

These "visual" depictions can , in fact, be translated into the following theorem, which I'm not going to prove, but I'm going to leave for those interested to verify.

Theorem : Given a simplex with three distinct vertices $a,b,c$, there is a bijection $\phi$ from the vertices of the map to itself such that $\phi(b) = c$ and the only vertex $x$ satisfying $\phi(x) = x$ is the point $a$.

Using this, one does as follows. Suppose that $p \in P_{x,y}$. Then, using the theorem we obtain a bijection $\phi_{x,y,y'}$ such that $\phi_{x,y,y'}(y) = y'$ and $\phi_{x,y,y'}(x) = x$ is the only fixed point. Create a new path $p'$ as follows : if $p = (x,p_1,p_2,\ldots, y)$ then $$ p' = (\phi_{x,y,y'}(x), \phi_{x,y,y'}(p_1),\phi_{x,y,y'}(p_2),\ldots, \phi_{x,y,y'}(y))$$

One sees that $p' \in P_{x,y'}$ by the properties of $\phi_{x,y,y'}$. Furthermore, the map $p \to p'$ created from $\phi_{x,y,y'}$ is invertible with inverse created similarly from $\phi_{x,y',y}$. Also observe that this map preserves the length of the path $p$!

All this put together , we get that there is a bijection from $P_{x,y}$ to $P_{x,y'}$, and because the map is length-preserving, it follows that $$ \sum_{P_{x,y}} \mathbb P(p|X_0 = x) = \sum_{n=1}^{\infty} \sum_{P_{x,y} : |p| = n} \mathbb (p|X_0 = x) \\ =_{bij'n} \sum_{n=1}^{\infty} \sum_{P_{x,y'} : |p'| = n} \mathbb (p'|X_0 = x) = \sum_{P_{x,y'}} \mathbb P(p'|X_0 = x) $$

Which shows the required equivalence. Hence, we are done!

---

$\tau_c$ and $\tau_d$

For $\tau_c$ now, we just need to note that we are performing the coupon-collector problem with the only condition being that we cannot pick the same coupon consecutively. However, this doesn't change things very much , because if you break $\tau_c$ into the stopping times $t_1 < t_2< \ldots < t_{n+1}$ where $t_i$ is the stopping time until you see $i$ unique vertices, then $t_0=t_1 = 0$ and $\mathbb E_U[\tau_c] = \sum_{i=0}^{n} \mathbb E_U[t_{i+1} - t_i]$.

The coupon-collector argument follows. If $t_i$ has occurred , then from the starting vertex, you can go to any non-visited vertex with probability $\frac{n-i}{n}$, otherwise you go to a visited vertex already. Considering the visit of a new vertex as a success, clearly $t_{i+1}-t_i$ is a geometric random variable with success probability $\frac{n-i}{n}$. In particular, we see that its expectation is $\frac{n}{n-i}$.

All in all, we have that $$ E_U[\tau_c] = \sum_{i=0}^{n} \mathbb E_U[t_{i+1} - t_i] = n \sum_{i=1}^n \frac{1}{i} = nH_n $$

What about $\tau_d$ now? Well, the claim that we have proven earlier is that , once $\tau_c$ has occurred, the resulting distribution over the rest of the vertices is uniform. Hence, we must find $\mathbb E_{U}[\tau_d]$.

However, it's easy to see that from any vertex $y \neq x$, you either visit $x$ with probability $\frac 1n$ or don't with probability $\frac{n-1}{n}$. That is, $\tau_d$ is also a geometric random variable but with success probability $\frac 1n$. This leads to $\mathbb E_U[\tau_D] = n$.

Finally, the answer is $$ \mathbb E_{U}[\tau] = \mathbb E_U[\tau_C] + \mathbb E_{U}[\tau_D] = n(H_n+1) $$

However, $E_{U}[\tau]$ actually equals $E[\tau|X_0 = x]$ for any value of $x$. To see why, if $x \neq y$ then one can use the same "rotation" argument (much more loosely) to obtain a bijection from paths starting at $x$ and ending at time $\tau$, to paths starting at $y$ and ending at time $\tau$, which is also length-preserving. Using the same "path-break" argument, one shows that $E[\tau|X_0 = x] = \mathbb E[\tau|X_0 = y]$ is independent of the start point, whence the equality follows from definition.

Therefore, we get $$ \mathbb E[\tau|X_0 = x] = n(H_n+1) $$

For example,

• $n=2$ : $2(1+\frac{1}{2}+1) = 7$.

• $n=3$ : $3(1+\frac{1}{2}+\frac 13 + 1) = 8.5$.

and so on.