Paseo aleatorio dentro de un paseo aleatorio dentro ...

Question

Deje $G=(V,E)$ un gráfico y considerar la posibilidad de un paseo aleatorio en él. Deje $G'=(V',E')$ ser un subgrafo que consta de los vértices y aristas que son visitados por el paseo aleatorio.

Pregunta 0: hay un nombre estándar para $G'$?

Intuitivamente $G'$ es una delgada subgrafo, así, por ejemplo, incluso cuando se $G$ es transitorio, $G'$ puede ser recurrente.

Pregunta 1: ¿hay un contraejemplo? Así, hay un transitorio gráfico de $G$, de modo que $G'$ es transitorio con probabilidad positiva?

También tengo curiosidad por saber qué sucede cuando uno recorre en este procedimiento, $G,G',G'',\dots$. ¿Finalmente se verá como una ruta gráfica?

Pregunta 2: ¿Qué se puede decir acerca de la $G^{(n)}$ as $n\to \infty$?

Answer 1

Pregunta 0:$G'$ se conoce como el rastro de la caminata aleatoria.

Pregunta 1:$G'$ siempre es recurrente con probabilidad uno. Este es el resultado de Benjamini, Gurel-Gurevich y Lyons de 2007.

Pregunta 2: Dado que$G'$ es recurrente, con una probabilidad tenemos$G^{(n)}=G'$ para todos los$n \geq 1$.