MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
up vote 32 down vote accepted

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

share|cite|improve this answer
I'd like to add that we have another paper with a different proof of the same result. Also, regarding "Does it eventually look like a path graph?" in another paper (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. – Ori Gurel-Gurevich Sep 23 '10 at 3:36
The link is broken. – Bach Jul 7 '15 at 19:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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