paseos aleatorios simples en grafos no dirigidos

Question

Consideremos un simple paseo aleatorio sobre un grafo no dirigido y conectado. Este es el paseo aleatorio que, en cada paso de tiempo, se desplaza a un vecino aleatorio, siendo todos los vecinos igualmente probables. Supongamos que cada nodo tiene un bucle propio para evitar los problemas asociados a la periodicidad. Entonces, el siguiente hecho (sorprendente para mí) es cierto: bajo la distribución estacionaria, cada arista se recorre con la misma probabilidad .

Estoy tratando de intuir por qué ocurre esto, y me pregunto si alguien puede dar una explicación a este fenómeno.

Naturalmente, conozco la prueba estándar que observa que $\pi_i = d_{i}/\sum_k d_k$ satisface las ecuaciones de la distribución estacionaria, por lo que $\pi_i p_{ij} = 1/\sum_k d_k$ siempre que el borde $(i,j)$ está presente en el gráfico. Esta prueba, sin embargo, me parece más un cálculo afortunado que una explicación.

Nótese que el hecho en negrita es falso para los grafos dirigidos. También es falso para la cadena de dos pasos correspondiente, es decir, la cadena de Markov con matriz de transición de probabilidad $P^2$ , donde $P$ es la matriz de transición del paseo aleatorio simple.

Answer 1

En primer lugar, piensa en cada arista como un camino de longitud unitaria que conecta dos vértices.

Ahora, imaginemos que en lugar de un paseo aleatorio por los vértices, consideramos un paseo aleatorio continuo que se mueve por las aristas a velocidad unitaria. Cada vez que llegamos a un vértice, decidimos aleatoriamente qué arista que sale del vértice vamos a atravesar a continuación. Nótese que la secuencia de vértices y aristas que atravesamos será la misma que en el paseo aleatorio en tiempo discreto.

Ahora imaginemos que llenamos el gráfico con un número muy grande de partículas, cada una de las cuales realiza un paseo continuo. Iniciamos las partículas en tiempos aleatorios en el intervalo $[0,1]$ para que cada vértice tenga continuamente partículas pasando por él, y luego esperar hasta que estemos en el estado estacionario.

Al menos para mí, parece obvio en este punto que el gráfico se llenará uniformemente de partículas, teniendo cada arista la misma densidad. A cada vértice le llegarán partículas desde todas sus aristas a la misma velocidad, y estas partículas se distribuirán aleatoriamente entre las aristas salientes. Esta situación es claramente estable, por lo que debe ser el estado estacionario.