Tasa de convergencia de cadena de Markov absorbente

Question

Sea $G$ un grafo biconectado y no bipartito. Puedo simular un paseo aleatorio en este grafo con una cadena de Markov. La matriz estocástica es $M = AD^{-1}$, donde $A$ es la matriz de adyacencia de $G$ y $D$ es una matriz diagonal con $D_{ii} = grado(i)$.

Porque $G$ está conectado y no es bipartito, hay una distribución estacionaria única $\pi$ tal que

$$\|\pi - M^i p\|_2 \le c (1-\lambda)^i $$

donde $\lambda$ es la diferencia entre el primer y segundo autovalor de $A$, llamado brecha espectral. Así que hay un límite inferior para la tasa de convergencia hacia la distribución estacionaria, dependiendo de la brecha espectral.

Puedo modificar el grafo para que haya un solo nodo sumidero, que una vez ingresado nunca pueda ser abandonado. Este grafo $G'$ ya no es no dirigido. Obtengo una cadena de Markov absorbente donde un estado es absorbente y todos los demás estados son transitorios. Aún hay una distribución estacionaria única $\pi'$, donde la probabilidad de estar en un nodo sumidero es 1.

Entonces mi pregunta es, ¿puedo obtener un límite similar para la tasa de convergencia del proceso de Markov absorbente, basado en la brecha espectral de $G$?

Answer 1

Por cierto, la expresión que tienes con $1-\lambda$, que involucra el espacio espectral, es simplemente el segundo mayor autovalor de la matriz de transición.

En el caso en que cada nodo tiene una arista al nodo absorbente, la tasa de deterioro cambiará a $N/(N+1)$ donde N es el número total de nodos en el grafo original. Puedes ver esto observando que los eigenvectores originales de la matriz de transición original seguirán funcionando si los aumentamos con un cero en la última posición. Sin embargo, dado que la submatriz correspondiente a permanecer dentro de los nodos originales del grafo debe reducirse en tamaño por el factor que involucra el grado, también lo harán los autovalores, por lo que el antiguo eigenvector de estado estacionario que tenía como autovalor 1, ahora tiene el autovalor que escribí anteriormente.

En el caso en que el número de aristas hacia el estado absorbente es mucho menor que el tamaño del grafo, creo que podrías hacer una aproximación de estado estacionario cuasi. Supongamos que dentro del grafo original las cosas están distribuidas de acuerdo a la antigua distribución estacionaria. Digamos que hay un solo nodo, digamos etiquetado como $i$, con una arista al nodo absorbente. Entonces, en promedio, si comienzas en el grafo original, tu probabilidad de moverte al estado absorbente en un turno dado será $\pi_i/(D_i + 1)$ donde $D_i $ es el grado original del nodo i. Por lo tanto, la probabilidad de permanecer en el subgrafo es 1 menos lo anterior, y eso debería, en el límite de que el subgrafo sea grande, aproximar tu tasa de deterioro.