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

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.

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.$$

• What is the $1$ in the expression $E(T) = 1 + \cdots$? – achille hui Oct 28 '14 at 12:13
• @achillehui Somehow I was counting the first time instant, but you are right it might be best not to. – Did Oct 28 '14 at 14:37
• I see. it is not clear whether we start with a configuration with no vertex or one vertex. I just want to make sure. – achille hui Oct 28 '14 at 14:45
• Can you provide a proof on this? I don't see how this limit gets us $Nlog(N)$ – EhBabay Oct 28 '14 at 16:23
• Now you are.  – Did Oct 30 '14 at 0:19

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?

• I think the probability of going to a new vertex is $\frac{N-n}{N-1}$ where n is the number of vertices you've been to. But I can't figure out the expected value. Is it an infinite series? – EhBabay Oct 28 '14 at 3:06
• Ok so I think I have an answer. – EhBabay Oct 28 '14 at 3:16

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

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?