チーガー行き

数学において、チーガー境界は、有限状態、離散時間、可逆定常マルコフ連鎖の遷移行列の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}}.}$

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