En matemáticas , el límite de Cheeger es un límite del segundo valor propio más grande de la matriz de transición de una cadena de Markov estacionaria reversible, de tiempo discreto y de estado finito . Puede verse como un caso especial de desigualdades de Cheeger en gráficos expansores .
Dejar ser un conjunto finito y dejar ser la probabilidad de transición para una cadena de Markov reversible en . Suponga que esta cadena tiene una distribución estacionaria .
Definir
y para definir
Definir la constante como
El operador actuando sobre el espacio de funciones desde a , definido por
tiene valores propios . Se sabe que. El límite de Cheeger es un límite en el segundo valor propio más grande.
Teorema (límite de Cheeger):
Ver también
Referencias
- J. Cheeger, Un límite inferior para el valor propio más pequeño del Laplaciano, Problemas en el análisis, Artículos dedicados a Salomon Bochner, 1969, Princeton University Press, Princeton, 195-199.
- P. Diaconis, D. Stroock, Límites geométricos para valores propios de cadenas de Markov, Annals of Applied Probability, vol. 1, 36-61, 1991, que contiene la versión del encuadernado que se presenta aquí.