Let $G=(V,E)$ be a graph and consider a random walk on it. Let $G'=(V',E')$ be a subgraph consisting of the vertices and edges that are visited by the random walk.

Question 0: Is there a standard name for $G'$?

Intuitively $G'$ is a thin subgraph, so for instance, even when $G$ is transient, $G'$ can be recurrent.

Question 1: Is there a counterexample? So, Is there a transient graph $G$ so that $G'$ is transient with positive probability?

I'm also curious to know what happens when one iterates this procedure, $G,G',G'',\dots$. Does it eventually look like a path graph?

Question 2: What can one say about $G^{(n)}$ as $n\to \infty$?


1 Answer 1


Question 0: $G'$ is known as the trace of the random walk.

Question 1: $G'$ is always recurrent with probability one. This is a result of Benjamini, Gurel-Gurevich, and Lyons from 2007.

Question 2: Since $G'$ is recurrent, with probability one we have $G^{(n)}=G'$ for all $n \geq 1$.

  • 13
    $\begingroup$ I'd like to add that we have another paper arxiv.org/abs/math/0508270 with a different proof of the same result. Also, regarding "Does it eventually look like a path graph?" in another paper arxiv.org/abs/0902.0115 (with Benjamini and Schramm) we prove that there are transient graphs for which the trace of a simple random walk does not look like path in the sense that it does not have infinitely many cutpoints. $\endgroup$ Sep 23, 2010 at 3:36
  • $\begingroup$ The link is broken. $\endgroup$
    – Bach
    Jul 7, 2015 at 19:46
  • $\begingroup$ The link has been fixed. $\endgroup$ May 16, 2017 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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