# Self-intersecting walk in expander graphs

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

• 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 Nov 11 '11 at 14:32
• 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 Nov 11 '11 at 14:52
• 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 Nov 11 '11 at 17:14
• 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 Nov 11 '11 at 19:28

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