Los paseos aleatorios cubren el tiempo en grafos regulares aleatorios

Question

Dejemos que $G=(V,E)$ sea un azaroso $r$ -grafo regular en $n$ nodos. Realiza un paseo aleatorio por $G$ partiendo de un nodo elegido según la distribución estacionaria del paseo (es decir, elegido uar de $V$ ).

Reclamación. Si $U \subset V$ y el paseo es en el vértice $u \in U$ en un momento determinado, entonces la posibilidad de que el paseo siga estando dentro $U$ en el siguiente paso es $|U|/|V|$ .

La afirmación es errónea (porque de lo contrario el tiempo de cobertura esperado para grafos cúbicos aleatorios sería $|V| \times \log|V|$ y sé que es un poco más grande que eso) ... pero ¿por qué? ¿Qué suposición errónea estoy haciendo? ¿Cuál es la probabilidad exacta de permanecer en un determinado conjunto de nodos?

Answer 1

[no hay derecho a comentar, así que publico esto como respuesta]

Por la propiedad de Markov fuerte, lo que parece implicar es equivalente a lo siguiente: partiendo en el tiempo 0 de la distribución estacionaria (uniforme) restringida en $U$ , $\pi(\cdot \cap U)/\pi(U)$ la cadena se distribuye según $\pi$ en el momento 1. Esto es un error en general (ver el comentario anterior de Liviu): se necesita más tiempo para alcanzar $\pi$ .

Ejemplo (aperiódico): para el gráfico 2 regular $\mathbb Z/n\mathbb Z$ , $n$ incluso, si se toma $U$ sea el conjunto de números Impares, entonces la probabilidad de permanecer en U el siguiente paso después de entrar en él es 0. Por otro lado, si se elige $U=\{n/2,...,n-1\}$ entonces la probabilidad de permanecer en $U$ el siguiente paso después de introducirlo en un tiempo estrictamente positivo es $1/2$ y esto coincide con $\pi(U)$ . Esto significa que el límite de U importa.