Cheeger se dirige

En matemáticas , la cota de Cheeger es una cota del segundo autovalor más grande de la matriz de transición de una cadena de Markov estacionaria, reversible, de tiempo discreto y con un número finito de estados . Puede considerarse un caso especial de las desigualdades de Cheeger en grafos expansores .

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

Definir

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

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

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

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

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

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

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

tiene valores propios${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$Se sabe que ${\displaystyle \lambda _ {1}=1}$La cota de Cheeger es una cota para el segundo valor propio más grande.${\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