27
$\begingroup$

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

$\endgroup$
34
$\begingroup$

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

$\endgroup$
  • 12
    $\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$ – Ori Gurel-Gurevich Sep 23 '10 at 3:36
  • $\begingroup$ The link is broken. $\endgroup$ – Bach Jul 7 '15 at 19:46
  • $\begingroup$ The link has been fixed. $\endgroup$ – Ori Gurel-Gurevich May 16 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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