スペクトルギャップによる混合の評価

$P$ を、正の確率分布 $\pi$ について可逆で既約な $S$ 上の遷移行列とし、$\pi_{\min} = \min_x\pi(x)$ と置く。定義 2.7 の記号を使う。

1. すべての $x \in S$ と $t \ge 0$ について $$\|P^t(x, \cdot) - \pi\|_{\mathrm{TV}} \le \frac12\sqrt{\frac{1 - \pi(x)}{\pi(x)}}\,(1 - \gamma^*)^t.$$
2. $\gamma^* > 0$ ならば、$0 < \varepsilon < 1$ について $$t_{\mathrm{mix}}(\varepsilon) \le \max\Bigl\{0,\ \Bigl\lceil\frac{1}{\gamma^*}\ln\frac{1}{2\varepsilon\sqrt{\pi_{\min}}}\Bigr\rceil\Bigr\}.$$
3. すべての $t \ge 0$ で $\lambda_*^t \le 2d(t)$ である。したがって $0 < \gamma^* < 1$、$0 < \varepsilon < \frac12$ ならば $$t_{\mathrm{mix}}(\varepsilon) \ge \Bigl(\frac{1}{\gamma^*} - 1\Bigr)\ln\frac{1}{2\varepsilon}.$$