# Random walk inside a random walk inside…

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

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

-
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. – Ori Gurel-Gurevich Sep 23 '10 at 3:36
The link is broken. – Bach Jul 7 '15 at 19:46