Cheeger con destino

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 considerarse un caso especial de desigualdades de Cheeger en grafos expansores .

Sea un conjunto finito y sea la probabilidad de transición para una cadena de Markov reversible en . Supongamos que esta cadena tiene una distribución estacionaria . ${\displaystyle X}$ ${\displaystyle K(x,y)}$ ${\displaystyle X}$ ${\displaystyle \pi }$

Definir

${\displaystyle Q(x,y)=\pi (x)K(x,y)}$

y para definir ${\displaystyle A,B\subset X}$

${\displaystyle Q(A\times B)=\sum _{x\in A,y\in B}Q(x,y).}$

Defina la constante como ${\displaystyle \Phi }$

${\displaystyle \Phi =\min _{S\subset X,\pi (S)\leq {\frac {1}{2}}}{\frac {Q(S\times S^{c})}{\pi (S)}}.}$

El operador que actúa sobre el espacio de funciones de a , definido por ${\displaystyle K,}$ ${\displaystyle |X|}$ ${\displaystyle \mathbb {R} }$

${\displaystyle (K\phi )(x)=\sum _{y}K(x,y)\phi (y)}$

tiene valores propios . Se sabe que . El límite de Cheeger es un límite en el segundo valor propio más grande . ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ ${\displaystyle \lambda _{1}=1}$ ${\displaystyle \lambda _{2}}$

Teorema (límite de Cheeger):

${\displaystyle 1-2\Phi \leq \lambda _{2}\leq 1-{\frac {\Phi ^{2}}{2}}.}$

Véase también

• Matriz estocástica
• Cheeger constante
• Conductancia

Referencias

• Cheeger, Jeff (1971). "Un límite inferior para el valor propio más pequeño del laplaciano". Problemas en análisis: un simposio en honor a Salomon Bochner (PMS-31) . Princeton University Press. págs. 195-200. doi :10.1515/9781400869312-013. ISBN . 978-1-4008-6931-2.
• Diaconis, Persi; Stroock, Daniel (1991). "Límites geométricos para valores propios de cadenas de Markov". Anales de probabilidad aplicada . 1 (1). Instituto de Estadística Matemática: 36–61. ISSN  1050-5164. JSTOR  2959624 . Consultado el 14 de abril de 2024 .