6
$\begingroup$

Consider a random walk in an expander graph. How much time it typically takes to visit the same vertex twice. It seems to me that it should be something between $\sqrt{n}$ to $\sqrt{n}\log n$. Is there any reference on this or similar things

$\endgroup$
  • 1
    $\begingroup$ That seems incorrect to me. The walk mixes fast and in $O(n \log n)$ time should visit all nodes. If a node is visited roughly every $\sqrt{n}$ steps then it would be too slow it seems. $\endgroup$ – Chandra Chekuri Nov 11 '11 at 14:32
  • 2
    $\begingroup$ My intuition is that it should behave like birthday paradox where each time you can pick a random node. The extra \log n factor may be needed since it takes \log n steps to pick a random node. $\endgroup$ – jian Nov 11 '11 at 14:52
  • $\begingroup$ There's something to Jian's intuition though: a heuristic argument is that after log n steps you're "mixed" and can access any node with equal probability (modulo a log n factor to get there). So then you are in 'balls and bins' land, and so the birthday paradox argument might kick in. This doesn't contradict the visiting time of n log n (that's analogous to the coupon collector event in the same system). $\endgroup$ – Suresh Venkat Nov 11 '11 at 17:14
  • $\begingroup$ I misunderstood the question. I thought it was asking how frequently a typical vertex gets revisited but it is how frequently does some vertex gets revisited. $\endgroup$ – Chandra Chekuri Nov 11 '11 at 19:28
5
$\begingroup$

I think only knowing the graph is an expander does not fix the value you are asking. If you are doing random walk naively then when the graph has bounded degree there is constant probability that the walk will reach the same vertex after just 2 steps, and therefore the expected number of steps is constant.

I guess you want to exclude that case by saying the random walk cannot take the same edge in two consecutive steps. But still there are different cases here: if we take the union of a degree 4 expander graph and a grid, it will still be an expander (with worse parameters), but there is constant probability that the walk return to the same position in 4 steps, and therefore the expected number of steps is again constant. On the other hand, if we take a random graph, since the girth is high the expected number (or in fact the minimum) of steps for any vertex to be revisited will be super-constant.

$\sqrt{n}\log n$ is definitely a safe upperbound because of the birthday paradox argument. I guess the answer for random graphs might be $\sqrt{n}$, because if you take a random walk of length significantly smaller than $\sqrt{n}$, with good probability the induced subgraph will be just the path and do not have more edges. In general if the induced graph on the set of visited vertices has a lot of edges outside the path, it means the walk "had many chances" to visit some vertex twice.

I understand this may not answer your question completely but I couldn't figure out how to leave a comment like Suresh Venkat did.

$\endgroup$
  • $\begingroup$ you need enough reputation to leave a comment. However, I think this is worth leaving as an answer because of length and level of detail. $\endgroup$ – Suresh Venkat Nov 15 '11 at 16:36
  • $\begingroup$ Thanks, Rong. I also realized that the source should be revisited with constant prob in a constant degree expander. I hope to get a high prob result. $\endgroup$ – jian Nov 16 '11 at 12:52
  • $\begingroup$ I think this is wrong. Just because there is a constant probability of returning in two steps, the expectation does not have to be constant. $\endgroup$ – user2316602 Sep 11 '19 at 15:02

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.