3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

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

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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – EhBabay Oct 28 '14 at 3:06
  • $\begingroup$ Ok so I think I have an answer. $\endgroup$ – EhBabay Oct 28 '14 at 3:16
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.