Explicación intuitiva de la brecha espectral en el contexto de Markov Chain Monte Carlo (MCMC)

Question

Estoy aprendiendo sobre los métodos Markov Chains Monte Carlo y los tiempos de mezcla, y me vendría bien un poco de ayuda para entender el concepto de Spectral Gap y por qué / cómo se relaciona con los tiempos de mezcla.

Hasta ahora lo que he aprendido es lo siguiente: dado un fenómeno ergódico (irreducible, aperiódico) y reversible (p. ej. $\pi(x)P(x,y) = \pi(y)P(y,x)$ para todos $x,y \in \Omega=$ espacio de estados) cadena de Markov finita y su matriz de transición $P$ la brecha espectral se define como

$$\xi = 1 - \lambda_\max$$

donde $\lambda_\max = \max\{|\lambda_2|, |\lambda_n|\}$ . Alternativamente, la brecha espectral puede entenderse como el menor valor propio positivo distinto de cero (¿creo?)

Vagamente entiendo que esto está relacionado de alguna manera con el tiempo de mezcla de la cadena de Markov (que cuanto mayor sea la brecha espectral, más rápido será el tiempo de mezcla), pero me falta una comprensión fundamental intuitiva de por qué esto es así. Mis conocimientos de álgebra lineal son escasos en el mejor de los casos, así que agradecería mucho una explicación como si tuviera 5 años de por qué los valores propios están acotados de la forma en que lo están (entre 1 y -1), por qué los valores propios negativos no nos preocupan realmente a efectos de MCMC, por qué nos preocupamos por $\lambda_\max$ y cómo es que la brecha espectral es indicativa del tiempo de mezcla.

Answer 1

En sentido estricto, MCMC significa construir una cadena de Markov que tenga alguna propiedad deseada (por lo general, una distribución de equilibrio o una expectativa preestablecidas) y, a continuación, extraer numéricamente muestras de ella. Si se le da una cadena de Markov, en realidad se denomina simulación de Montecarlo.

De todos modos, a cada hora fija $t$ el valor de la cadena tendrá una determinada distribución, dada por $p_0 P^t$ donde $p_0$ es la distribución inicial (escrita como un vector de filas) y $P$ es la matriz de probabilidad de transición (en la convención fila-estocástica, es decir. $\sum_{j=1}^n P_{ij}=1$ ).

Así que el comportamiento a largo plazo de las distribuciones en cada fijo $t$ viene determinado por el comportamiento de $P^t$ como $t \to \infty$ . Cualquier matriz estocástica tiene todos los valores propios de módulo como máximo $1$ . También dispone de $1$ como valor propio. El supuesto de ergodicidad nos dice además que el valor propio $1$ tiene multiplicidad $1$ y que todos sus demás valores propios tendrán módulo estrictamente inferior a $1$ . (Sin irreducibilidad es posible que el valor propio $1$ tiene una multiplicidad mayor; sin aperiodicidad es posible tener un valor propio como $-1$ o $e^{2\pi i/3}$ .) La hipótesis de reversibilidad nos dice (entre otras cosas) que $P$ es diagonalizable con valores propios reales (porque la reversibilidad proporciona una transformación de similitud que convierte a $P$ en una matriz simétrica).

Como resultado de estos tres hechos se puede escribir

$$p_0 P^t = \pi + \sum_{i=2}^n c_i \lambda_i^t q_i$$

donde $\lambda_i$ son valores propios menores que $1$ en valor absoluto, $q_i$ son los vectores propios izquierdos, y $c_i$ son coeficientes que dependen de $p_0$ . Esto es justo lo que se obtiene al diagonalizar $P^t$ (sin repasar y calcular el $c_i$ ya que realmente no importan para esta presentación).

Puede ver que como $t \to \infty$ los valores propios restantes decaerán debido a la potencia de $t$ . Suponiendo que el $c_i$ son todas significativas (la situación típica para una distribución inicial "aleatoria"), la el más lento decaimiento es por $\lambda_{\max}$ ya que está más cerca de $1$ en valor absoluto. Por tanto, cuanto mayor sea la brecha espectral $\xi$ más rápida será la convergencia. Obsérvese que los valores propios negativos do asunto, por lo que lo escribió como $\lambda_{\max}=\max \{ |\lambda_2|,|\lambda_n| \}$ .

La relación precisa entre la brecha espectral y las propiedades dinámicas de la cadena es más sutil que el resto de lo que he dicho aquí. En términos generales, cuando la brecha espectral es pequeña, el vector propio correspondiente a $\lambda_{\max}$ que podría denominar "eigenvector metaestable", será significativo y positivo para un conjunto de estados y significativo y negativo para otro conjunto de estados. También podría ser menor en un tercer conjunto de estados.

El "eigenvector metaestable" corresponde entonces al lento intercambio de probabilidad entre los dos primeros conjuntos de estados (porque el decaimiento de su contribución a la distribución da lugar a un flujo de un conjunto al otro, dependiendo el conjunto de cuál sea el signo del correspondiente $c_i$ ). Para más información, consulte metaestabilidad en cadenas de Markov. Para hacerse una idea, considere una matriz como

$$P=\begin{bmatrix} 1/3 & 2/3 & 0 & 0 \\ 1/4-\epsilon/2 & 3/4-\epsilon/2 & \epsilon & 0 \\ 0 & \epsilon & 1/5-\epsilon/2 & 4/5-\epsilon/2 \\ 0 & 0 & 1/6 & 5/6 \end{bmatrix}$$

donde $0<\epsilon \ll 1$ es un parámetro pequeño. Para $\epsilon=10^{-6}$ por ejemplo, esto tiene un equilibrio relativamente rápido dentro de los conjuntos $\{ 1,2 \}$ y $\{ 3,4 \}$ (impulsado por valores propios de $1/12$ y $1/30$ respectivamente) y un lento equilibrio entre ambos (impulsado por un valor propio de aproximadamente $1-10^{-6}$ ).