Random walk on complete graph

Question

An ant is doing a random walk on the complete graph of n vertices (1,...,n) starting at vertex 1. What is the expectation of the number of moves until it gets to every vertice?

Answer 1

Let $E$ be the expected number of moves, and $E_x$ be the expected number of moves the ant takes when it has already visited $x$ vertices to visit a new vertex.

Using linearity of expectation,

$$E = \sum^{n-1}_{i=1} E_i$$

$E_i$ is, as you have suggested, the expected value of a geometric distribution with $p=\frac{n-i}{n-1}$.

$$\implies E = \sum^{n-1}_{i=1} \frac{n-1}{n-i}$$

$$= (n-1)\sum^{n-1}_{i=1} \frac{1}{n-i}$$

$$= (n-1)\sum^{n-1}_{i=1} \frac{1}{i}$$

$$= (n-1)H_{n-1}$$

where $H_n$ is the nth harmonic number