チーガー行き

数学において、チーガー境界（チーガーばんい）とは、有限状態、離散時間、可逆な定常マルコフ連鎖の遷移行列の2番目に大きい固有値の境界である。これは、エクスパンダーグラフにおけるチーガー不等式の特殊なケースとみなすことができる。

を有限集合とし、上の可逆マルコフ連鎖の遷移確率を とする。この連鎖は定常分布に従うと仮定する。 ${\displaystyle X}$ ${\displaystyle K(x,y)}$ ${\displaystyle X}$ ${\displaystyle \pi }$

定義する

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

そして定義 する ${\displaystyle A,B\subset X}$

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

定数を次のように 定義する ${\displaystyle \Phi }$

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

からまでの関数の空間に作用する演算子は、次のように定義される。 ${\displaystyle K,}$ ${\displaystyle |X|}$ ${\displaystyle \mathbb {R} }$

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

は固有値 を 持ちます。 であることが知られています 。Cheeger境界は、2番目に大きい固有値 に関する境界です。 ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}}$ ${\displaystyle \lambda _{1}=1}$ ${\displaystyle \lambda _{2}}$

定理（チーガー境界）:

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

参照

• 確率行列
• チーガー定数
• コンダクタンス

参考文献

• チーガー、ジェフ (1971). 「ラプラシアンの最小固有値の下限値」.解析学の問題：サロモン・ボクナー記念シンポジウム (PMS-31) . プリンストン大学出版局. pp.  195– 200. doi :10.1515/9781400869312-013. ISBN 978-1-4008-6931-2。
• Diaconis, Persi; Stroock, Daniel (1991). 「マルコフ連鎖の固有値の幾何学的境界」.応用確率年報. 1 (1). 数理統計研究所: 36–61 . doi :10.1214/aoap/1177005980. ISSN  1050-5164. JSTOR  2959624. 2024年4月14日閲覧.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Cheeger_bound&oldid=1272555911"