most recent 30 from http://mathoverflow.net 2013-06-20T12:14:07Z http://mathoverflow.net/feeds/question/39664 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39664/random-walk-inside-a-random-walk-inside Gjergji Zaimi 2010-09-22T22:38:47Z 2010-09-22T23:07:18Z

<p>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.</p> <blockquote> <p>Question 0: Is there a standard name for $G'$?</p> </blockquote> <p>Intuitively $G'$ is a thin subgraph, so for instance, even when $G$ is transient, $G'$ can be recurrent.</p> <blockquote> <p>Question 1: Is there a counterexample? So, Is there a transient graph $G$ so that $G'$ is transient with positive probability?</p> </blockquote> <p>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?</p> <blockquote> <p>Question 2: What can one say about $G^{(n)}$ as $n\to \infty$?</p> </blockquote>

http://mathoverflow.net/questions/39664/random-walk-inside-a-random-walk-inside/39667#39667 Louigi Addario-Berry 2010-09-22T23:07:18Z 2010-09-22T23:07:18Z

<p>Question 0: $G'$ is known as the <em>trace</em> of the random walk. </p> <p>Question 1: $G'$ is always recurrent with probability one. This is <a href="http://www.math.ubc.ca/~origurel/papers/BGGL07.pdf" rel="nofollow">a result of Benjamini, Gurel-Gurevich, and Lyons</a> from 2007.</p> <p>Question 2: Since $G'$ is recurrent, with probability one we have $G^{(n)}=G'$ for all $n \geq 1$. </p>