Cheeger bunden

I matematik är Cheeger -gränsen en gräns för det näst största egenvärdet för övergångsmatrisen för en ändlig, tidsdiskret, reversibel stationär Markov-kedja . Det kan ses som ett specialfall av Cheeger-ojämlikheter i expandergrafer .

Låt $X$ vara en finit mängd och låt $K(x,y)$ vara övergångssannolikheten för en reversibel Markov-kedja på $X$ . Antag att denna kedja har stationär fördelning $\pi$ .

Definiera

$Q(x,y)=\pi (x)K(x,y)$

och för $A,B\subset X$ definiera

$Q(A\ gånger B)=\summa _{x\in A,y\in B}Q(x,y).$

Definiera konstanten $\Phi$ som

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

Operatören $K,$ som verkar på utrymmet för funktioner från $|X|$ till $|X|$ , definierad av

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

har egenvärden $\lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}$ . Det är känt att $\lambda _{1}=1$ . Cheeger-gränsen är en gräns för det näst största egenvärdet $\lambda _{2}$ .

Sats (Cheeger bundet):

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

Se även

• Stokastisk matris
• Cheeger konstant

• J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis, Papers dedikerade till Salomon Bochner, 1969, Princeton University Press, Princeton, 195-199.
• P. Diaconis, D. Stroock, Geometriska gränser för egenvärden för Markov-kedjor, Annals of Applied Probability, vol. 1, 36-61, 1991, innehållande versionen av bunden som presenteras här.