<p>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.</p>

<p>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.</p>

<p>$\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.</p>

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

CC BY-SA 3.0
2011-11-15T16:36:34.853Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-11-16T12:52:25.087Z
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.
jian
CC BY-SA 4.0
2019-09-11T15:02:58.363Z
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.
user2316602
CC BY-SA 3.0
2011-11-15T16:19:22.767Z
2011-11-15T16:19:22.767Z
Rong Ge
<p>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</p>

CC BY-SA 3.0
2011-11-11T14:32:48.533Z
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.
Chandra Chekuri
CC BY-SA 3.0
2011-11-11T14:52:37.127Z
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.
jian
CC BY-SA 3.0
2011-11-11T17:14:43.923Z
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).
Suresh Venkat
CC BY-SA 3.0
2011-11-11T19:28:06.570Z
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.
Chandra Chekuri
<reference-request><graph-theory><co.combinatorics><expanders><random-walks>
Self-intersecting walk in expander graphs
jian
# Self-intersecting walk in expander graphs

(Asked by: username_0 on 2011-11-11)

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

**Tags:** reference-request, graph-theory, co.combinatorics, expanders, random-walks
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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).  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-11-15. Score: 5

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.

> **Comments:**
> **username_2**: 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.  
> **username_0**: 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.  
> **username_4**: 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.  

---

