¿Por qué una caminata al azar en un grafo G converge a una distribución uniforme?

Question

De La Wikipedia:

la conductancia de un grafo G=(V,E) las medidas de cómo "tejer" el gráfico es: controla la velocidad de un paseo aleatorio en G converge a un uniforme de distribución.

Me preguntaba por qué una caminata al azar en un grafo G converge a un uniforme distribución? Cualquier referencia en este?

Gracias!

Answer 1

No, en general. Que el artículo necesita corrección.

Un paseo aleatorio de partida en cualquier vértice se (suponiendo que G está conectado y [como Nate señaló] da una aperiódica pie) converge a la distribución estacionaria, la cual está dada por los valores de la izquierda vector propio asociado con el primer autovalor de la matriz de transición. Esto depende de las conexiones de ambos en el gráfico y en las probabilidades, en cualquier vértice, con el que se va a mover a cada uno de sus vecinos.

La distribución estacionaria será uniforme si, por ejemplo, el grafo es regular (todos los vértices tienen el mismo grado) y en cada paso se elige uno de los nodos vecinos, con igual probabilidad, desde entonces, la izquierda autovector es proporcional a $\mathbf{1} = (1,1,\dotsc,1)$.

Answer 2

Una caminata al azar en un gráfico de $G$ con vértices $\{1,2,\ldots,n\}$ tiene la matriz de transición $P(i,j)=\frac{n_{ij}}{d_i}$ donde $n_{ij}$ 1 $i,j$ siendo vecinos y 0 en caso contrario y $d_i$ es el grado de $i$. Esta matriz de transición es reversible con respecto a la medida $\pi(i)=\frac{d_i}{\sum_i d_i}=\frac{d_i}{2m}$ donde $m$ es el número de aristas:

$\pi(i)P(i,j)=\pi(j)P(j,i)$.

Esto implica $\pi$ es estacionaria medida de la cadena de Markov: $\pi P= \pi$, en ese $\sum_i \pi(i)P(i,j)=\sum_i\pi(j)P(j,i)=\pi(j)$. Suponiendo que la cadena de Markov es tanto irreducible y aperiódica, esto implica que hemos de convergencia a la distribución estacionaria. Tenga en cuenta que no es "uniforme" en el que no todos los puntos son igualmente probables, sino que cada punto es tan probable como del grado.