Find the expected number of steps needed until every point has been visited at least once.

Question

The complete graph on {1,...,N} is the simple graph with these vertices such that any pair of distinct points is adjacent. Let $X_{n}$ denote the simple random walk on this graph and let T be the first time that the walk reaches the state 1.

The question is: Find the expected number of steps needed until every point has been visited at least once.

Answer 1

By a small modification of this answer, the mean time to visit every vertex at least once, counting the vertex one starts from, is $$E(S)=\frac{N-1}{N-1}+\frac{N-1}{N-2}+\frac{N-1}{N-3}+\cdots+\frac{N-1}{2}+\frac{N-1}{1}=(N-1)H_{N-1},$$ hence, when $N\to\infty$, $$E(S)\sim N\log N.$$

Answer 2

Hint: what is the expected number of steps from the first time $n$ different vertices have been visited to the first time $n+1$ different vertices have been visited?

Answer 3

Hint: This is almost the coupon collector's problem because the complete graph lets you visit the other vertices randomly. There is a slight change because the next coupon is never the same as the one you just got

Answer 4

Ok so I think I have an answer.

Expected amount of time to adding 1 node=$\sum_{k=1}^{\infty }k(\frac{n}{N-1})^(k-1)(\frac{N-n}{N-1})$. Where n= number of nodes visited.

Then using the properties of a geometric series we determine the expected value of steps to add a new node gets us this:

$\frac{N-n}{N-1}\frac{1}{(1-\frac{n}{N-1})^2}$

Then I should be multiplying this equation by N? Yes or no?