Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

up vote 27 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|improve this answer
10  
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
add comment

Your Answer

 
discard

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.