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 .${\estilo de visualización X}$${\displaystyle K(x,y)}$${\estilo de visualización X}$ ${\estilo de visualización \pi}$

Definir

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

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

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

Defina la constante como${\estilo de visualización \Phi}$

${\displaystyle \Phi =\min _{S\subconjunto 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${\estilo de visualización K,}$${\estilo de visualización |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}}.}$

• Matriz estocástica
• Cheeger constante
• Conductancia

Este artículo relacionado con las estadísticas es un esbozo . Puedes ayudar a Wikipedia expandiéndolo.

• en
• a
• mi