1

I'm currently reading Lovasz's survey on random walks. He claims without proof in Proposition 2.3 that the expected time taken for a simple random walk starting at a vertex $u$ to return to $u$ is equal to $2m/d_u$, where $m$ is the number of edges in the underlying graph and $d_u$ is the degree of $u$.

Just wondering if anyone can provide a proof or some intuition behind it? Thanks.

Emil Sinclair
  • 769
  • 1
    The intuition isn't hard: imagine the random walk's been going for a long time and has mixed so it could be anywhere on the graph (assuming it's connected). At any given time there are $2m$ different steps it could be taking (two for every edge since they can be traversed in either direction) and of those $d_u$ steps take it to $u$. – Qiaochu Yuan Jul 19 '22 at 11:31
  • I'm sorry, but the way you're putting it makes it sound as though we're starting from the stationary distribution. Otherwise, to get close to being mixed the walk would have to go on for a long time, during which it might return to $u$ multiple times! – Emil Sinclair Jul 19 '22 at 12:27
  • That’s why I said it’s intuition and not a proof :P – Qiaochu Yuan Jul 19 '22 at 12:54
  • In the intuition that you mention, why shouldn't it be $2m/2d_u$? – Deep_S Dec 09 '22 at 00:43

0 Answers0