混合時間

同義語:mixing time

概要

混合時間(mixing time)とは、有限の状態空間の上の Markov 連鎖について、最悪の出発点からの分布と定常分布の全変動距離 $d(t)$ が $\varepsilon$ 以下になる最小の歩数 $t_{\mathrm{mix}}(\varepsilon)$ のことで、連鎖が出発点を忘れるまでの速さを測る。既約で周期がなければ有限である。上界は、同じ推移行列で動く 2 つの連鎖を一緒に走らせる結合をつくり、合流時刻 $\tau$ について $d(t)\le\max\Pr(\tau>t)$ とする方法で得られ、下界は 1 以外の固有値 $\lambda$ についての $\lvert\lambda\rvert^t\le2d(t)$ から得られる。トランプの切り方の回数や Markov 連鎖モンテカルロ法の精度の保証に使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Markov連鎖, 確率行列, Markovの不等式

52 枚のトランプを何回切れば十分に混ざるか。格子の上を酔歩する点の位置が、出発点を忘れて一様に散らばるまでに何歩かかるか。既約で周期のない有限 Markov 連鎖の分布が定常分布に近づくことは知られているが、応用で必要なのは「どれだけ速く近づくか」という量的な答えである。その答えを一つの数にまとめたものが 混合時間 である。
混合時間は 全変動距離 で測る。上界の主な道具は 結合(カップリング。カップリング(確率論))で、同じ推移行列で動く 2 つの連鎖を一緒に走らせ、出会うまでの時刻から距離を抑える。この記事では結合による上界(主定理)、劣乗法性、固有値による下界を証明し、例で数値まで計算する。

定義と使える条件

以下、$\mathcal X$ は有限集合、$P$ は $\mathcal X$ 上の推移行列(各行が確率ベクトルの非負行列)、$\pi$ は $P$ の定常分布($\pi P=\pi$ を満たす確率ベクトル)とする。$P^t(x,\cdot)$ は $x$ から出発した連鎖の時刻 $t$ の分布、$P^t(x,A)=\sum_{y\in A}P^t(x,y)$ である。

全変動距離

$\mathcal X$ 上の確率分布 $\mu,\nu$ の 全変動距離(total variation distance)を
$$ \|\mu-\nu\|_{\mathrm{TV}}:=\max_{A\subset\mathcal X}\lvert\mu(A)-\nu(A)\rvert $$
で定める。確率変数の組 $(X,Y)$ で、$X$ の分布が $\mu$、$Y$ の分布が $\nu$ であるものを、$\mu$ と $\nu$ の 結合(coupling)という。

全変動距離の 3 つの表し方

$\mathcal X$ 上の確率分布 $\mu,\nu$ について次が成り立つ。

  1. $\displaystyle\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_{x\in\mathcal X}\lvert\mu(x)-\nu(x)\rvert=1-\sum_{x\in\mathcal X}\min\{\mu(x),\nu(x)\}$。
  2. $\mu$ と $\nu$ のどの結合 $(X,Y)$ についても $\|\mu-\nu\|_{\mathrm{TV}}\le\Pr(X\ne Y)$。
  3. $\Pr(X\ne Y)=\|\mu-\nu\|_{\mathrm{TV}}$ となる結合が存在する。

1・2 は和をとる範囲を分けるだけの計算、3 は具体的な構成である。

証明を開く

1:$B=\{x:\mu(x)\ge\nu(x)\}$ とする。どの $A$ でも、$A\setminus B$ の点では $\mu(x)< \nu(x)$、$B\setminus A$ の点では $\mu(x)\ge\nu(x)$ なので $\mu(A)-\nu(A)\le\mu(A\cap B)-\nu(A\cap B)\le\mu(B)-\nu(B)$ である。同じく $\nu(A)-\mu(A)\le\nu(B^c)-\mu(B^c)$ で、$\mu,\nu$ の総和はともに $1$ なので右辺どうしは等しい。$A=B$ で等号が成り立つから $\|\mu-\nu\|_{\mathrm{TV}}=\mu(B)-\nu(B)$ である。これは $\sum_{x\in B}(\mu(x)-\nu(x))$ で、$B^c$ の上の $\sum(\nu-\mu)$ と等しいので、両者の平均 $\frac12\sum_x\lvert\mu(x)-\nu(x)\rvert$ に等しい。また $\min\{\mu(x),\nu(x)\}=\mu(x)-(\mu(x)-\nu(x))^+$ を足し合わせると $\sum_x\min\{\mu,\nu\}=1-(\mu(B)-\nu(B))$ である。

2:どの $A$ でも $\mu(A)-\nu(A)=\Pr(X\in A)-\Pr(Y\in A)\le\Pr(X\in A,\ Y\notin A)\le\Pr(X\ne Y)$ である。$\mu,\nu$ を入れかえても同じなので、$A$ について最大をとればよい。

3:$p:=\sum_x\min\{\mu(x),\nu(x)\}$ とおく。$p=1$ なら $\mu=\nu$ で、$X=Y$ を $\mu$ に従わせればよい。$p=0$ なら独立な結合で $\Pr(X\ne Y)=1=\|\mu-\nu\|_{\mathrm{TV}}$ である。$0< p< 1$ のとき、確率 $p$ で表が出る硬貨を投げ、表なら $Z$ を分布 $\min\{\mu,\nu\}/p$ からとって $X=Y=Z$ とし、裏なら $X$ を分布 $(\mu-\nu)^+/(1-p)$ から、$Y$ を分布 $(\nu-\mu)^+/(1-p)$ から独立にとる(1 により、どちらの分母も分子の総和 $1-p$ に等しい)。$X$ の分布は $\min\{\mu,\nu\}+(\mu-\nu)^+=\mu$、$Y$ の分布は $\nu$ である。裏のとき $X$ は $\mu>\nu$ の点、$Y$ は $\nu>\mu$ の点に値をとるので $X\ne Y$ で、表のとき $X=Y$ だから $\Pr(X\ne Y)=1-p=\|\mu-\nu\|_{\mathrm{TV}}$ である。$\square$

1 から $0\le\|\mu-\nu\|_{\mathrm{TV}}\le1$ で、全変動距離は確率分布の上の距離である。全変動距離を $\sum_x\lvert\mu(x)-\nu(x)\rvert$($1$ の $2$ 倍)で定める文献もあるので、数値を比べるときは規約を確かめる。

定常分布からの距離と混合時間

$t=0,1,2,\dots$ について
$$ d(t):=\max_{x\in\mathcal X}\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}},\qquad \bar d(t):=\max_{x,y\in\mathcal X}\|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}} $$
と置く。$0< \varepsilon< 1$ について
$$ t_{\mathrm{mix}}(\varepsilon):=\min\{t\ge0: d(t)\le\varepsilon\},\qquad t_{\mathrm{mix}}:=t_{\mathrm{mix}}(1/4) $$
を 混合時間(mixing time)という。そのような $t$ がなければ $t_{\mathrm{mix}}(\varepsilon)=\infty$ とする。

$d(t)$ は最悪の出発点での距離なので、混合時間は「どこから出発しても $t_{\mathrm{mix}}(\varepsilon)$ 歩の後には、どの事象の確率も定常分布での確率と $\varepsilon$ 以内で一致する」ことを保証する歩数である。$1/4$ は慣習の値で、$1/2$ 未満ならどれを選んでも定数倍しか変わらない(thm-mix-submult の 3)。
混合時間が有限になる条件は次のとおりである。

  • (i) $\mathcal X$ は有限集合である。
  • (ii) $P$ は 既約 である(どの $x,y$ にも $P^t(x,y)>0$ となる $t$ がある)。
  • (iii) $P$ は 非周期的 である(各 $x$ で $\{t\ge1:P^t(x,x)>0\}$ の最大公約数が $1$)。
    (i)〜(iii) のもとで定常分布 $\pi$ はただ 1 つで(Markov連鎖 の定理「既約な有限連鎖の定常分布」)、ある $r$ で $P^r$ の成分がすべて正になる(LPW17 Proposition 1.7、p. 7。この記事では証明しない)。この記事では (ii)(iii) の代わりに直接「$P^r$ の成分がすべて正になる $r$ がある」ことを仮定に使う。条件を一つ外すと混合時間が有限にならない例は、節「使える条件と反例」にまとめる。

公式の表

主張式使える条件根拠
全変動距離の和の形$\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_x\lvert\mu(x)-\nu(x)\rvert$有限集合上の確率分布prop-mix-tv
結合の不等式$\|\mu-\nu\|_{\mathrm{TV}}\le\Pr(X\ne Y)$$(X,Y)$ は $\mu,\nu$ の結合prop-mix-tv
$d$ と $\bar d$$d(t)\le\bar d(t)\le2d(t)$$\pi$ は定常分布thm-mix-coupling
結合による上界$d(t)\le\max_{x,y}\Pr_{x,y}(\tau>t)$各 $x,y$ に連鎖の結合があるthm-mix-coupling
劣乗法性$\bar d(s+t)\le\bar d(s)\,\bar d(t)$なしthm-mix-submult
精度を上げる費用$t_{\mathrm{mix}}(\varepsilon)\le\lceil\log_2(1/\varepsilon)\rceil\,t_{\mathrm{mix}}$$0< \varepsilon< 1$thm-mix-submult
固有値による下界$t_{\mathrm{mix}}(\varepsilon)\ge\bigl(\frac1{1-\lvert\lambda\rvert}-1\bigr)\log\frac1{2\varepsilon}$$\lambda\ne1$ は $P$ の固有値、$0< \varepsilon< 1/2$prop-mix-eigen
緩和時間による上界$t_{\mathrm{mix}}(\varepsilon)\le t_{\mathrm{rel}}\log\frac1{\varepsilon\,\pi_{\min}}$可逆・既約この記事では証明しない(thm-mix-relax)

主定理:結合による上界

2 つの連鎖を別々に走らせるのではなく、同じ乱数を使って一緒に走らせ、早く出会うように仕組むのが結合の方法である。

連鎖の結合と合流時刻

$x,y\in\mathcal X$ とする。同じ確率空間の上の確率過程の組 $(X_t,Y_t)_{t\ge0}$ で、$(X_t)$ が $X_0=x$ の推移行列 $P$ の Markov 連鎖、$(Y_t)$ が $Y_0=y$ の推移行列 $P$ の Markov 連鎖であるものを、$x$ と $y$ から出発する 連鎖の結合 という。
$$ \tau:=\min\{t\ge0: \text{すべての } s\ge t \text{ で } X_s=Y_s\}\quad(\text{なければ }\infty) $$
を 合流時刻 という。この確率空間の確率を $\Pr_{x,y}$ と書く。

$(X_t)$ と $(Y_t)$ のそれぞれが推移行列 $P$ の連鎖であればよく、両者の関係は自由に選べる。実際の構成では、出会うまでは何らかの規則で動かし、出会った後は同じ乱数で同じように動かす。こうすると合流時刻は最初に出会う時刻に等しい。

結合による混合時間の上界

$\pi$ を $P$ の定常分布とする。

  1. $d(t)\le\bar d(t)\le2d(t)$ である。
  2. $x$ と $y$ から出発する連鎖の結合と、その合流時刻 $\tau$ について $\|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}}\le\Pr_{x,y}(\tau>t)$ である。
  3. したがって、すべての $x,y$ について結合が与えられていれば
    $$ d(t)\le\max_{x,y\in\mathcal X}\Pr_{x,y}(\tau>t),\qquad t_{\mathrm{mix}}\le\Bigl\lceil4\max_{x,y\in\mathcal X}E_{x,y}[\tau]\Bigr\rceil $$
    である。
定常性で平均をとり、結合の不等式に持ち込む

1:$\bar d(t)\le2d(t)$ は全変動距離の三角不等式 $\|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}}\le\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}+\|\pi-P^t(y,\cdot)\|_{\mathrm{TV}}$ から出る。逆向きを示す。$\pi$ は定常なので $\pi=\pi P^t$、すなわち各 $A\subset\mathcal X$ で $\pi(A)=\sum_y\pi(y)P^t(y,A)$ である。$\sum_y\pi(y)=1$ を使うと
$$ \lvert P^t(x,A)-\pi(A)\rvert=\Bigl\lvert\sum_{y}\pi(y)\bigl(P^t(x,A)-P^t(y,A)\bigr)\Bigr\rvert\le\sum_y\pi(y)\,\|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}}\le\bar d(t) $$
である。左辺を $x$ と $A$ について最大にすれば $d(t)\le\bar d(t)$ を得る。
2:$(X_t)$ は $x$ から出発する推移行列 $P$ の連鎖なので $\Pr_{x,y}(X_t=z)=P^t(x,z)$、同じく $\Pr_{x,y}(Y_t=z)=P^t(y,z)$ である。よって $(X_t,Y_t)$ は $P^t(x,\cdot)$ と $P^t(y,\cdot)$ の結合で、prop-mix-tv の 2 により
$$ \|P^t(x,\cdot)-P^t(y,\cdot)\|_{\mathrm{TV}}\le\Pr_{x,y}(X_t\ne Y_t) $$
である。$X_t\ne Y_t$ なら合流時刻の定義から $\tau>t$ なので、右辺は $\Pr_{x,y}(\tau>t)$ 以下である。
3:1 と 2 から $d(t)\le\bar d(t)\le\max_{x,y}\Pr_{x,y}(\tau>t)$ である。$M:=\max_{x,y}E_{x,y}[\tau]$ が有限のとき、Markovの不等式 により $\Pr_{x,y}(\tau>t)\le E_{x,y}[\tau]/t\le M/t$ なので、$t=\lceil4M\rceil$ で $d(t)\le1/4$ となる($M=0$ なら $d(0)=0$)。$\square$

主定理の 2 は、全変動距離を「どう結合しても $X_t\ne Y_t$ の確率はこれより小さくできない量」として見たときの直接の帰結である。上界の良し悪しは結合の選び方で決まる。独立に走らせると出会いにくく、出会った後も離れてしまうので、良い上界は得られない(節「よくある誤り」)。

劣乗法性

距離の単調性と劣乗法性
  1. $d(t+1)\le d(t)$、$\bar d(t+1)\le\bar d(t)$ である。
  2. すべての $s,t\ge0$ で $\bar d(s+t)\le\bar d(s)\,\bar d(t)$ である。とくに正の整数 $\ell$ について $d(\ell t)\le\bar d(t)^\ell$。
  3. $0< \varepsilon< 1/2$ と正の整数 $\ell$ について $d(\ell\,t_{\mathrm{mix}}(\varepsilon))\le(2\varepsilon)^\ell$ であり、$0< \varepsilon< 1$ について $t_{\mathrm{mix}}(\varepsilon)\le\lceil\log_2(1/\varepsilon)\rceil\,t_{\mathrm{mix}}$ である。
符号の付いた測度を正と負に分ける

まず補題を示す。$\mu,\nu$ を確率分布、$g\colon\mathcal X\to\mathbb R$ とし、$\operatorname{osc}g:=\max g-\min g$ とする。$\eta:=\mu-\nu$ は $\sum_z\eta(z)=0$ を満たすので、$\eta^+$ と $\eta^-$ の総和はともに $\|\mu-\nu\|_{\mathrm{TV}}$ に等しい(prop-mix-tv の 1 の証明)。よって
$$ \sum_z\eta(z)g(z)=\sum_z\eta^+(z)g(z)-\sum_z\eta^-(z)g(z)\le\|\mu-\nu\|_{\mathrm{TV}}\max g-\|\mu-\nu\|_{\mathrm{TV}}\min g=\|\mu-\nu\|_{\mathrm{TV}}\operatorname{osc}g.\qquad(*) $$
2:$x,y$ と $A$ を固定し、$\mu=P^s(x,\cdot)$、$\nu=P^s(y,\cdot)$、$g(z)=P^t(z,A)$ と置く。$P^{s+t}=P^sP^t$ なので
$$ P^{s+t}(x,A)-P^{s+t}(y,A)=\sum_z\bigl(P^s(x,z)-P^s(y,z)\bigr)P^t(z,A)\le\bar d(s)\operatorname{osc}g $$
である。$\operatorname{osc}g=\max_{z,z'}(P^t(z,A)-P^t(z',A))\le\bar d(t)$ だから、$x,y,A$ について最大をとって $\bar d(s+t)\le\bar d(s)\bar d(t)$ を得る。これを繰り返し、thm-mix-coupling の 1 を使えば $d(\ell t)\le\bar d(\ell t)\le\bar d(t)^\ell$ である。
1:$\bar d(1)\le1$ なので 2 から $\bar d(t+1)\le\bar d(t)$ である。$d$ については、$P^{t+1}(x,\cdot)=\sum_yP(x,y)P^t(y,\cdot)$ と $\pi=\sum_yP(x,y)\pi$ から、各 $A$ で $\lvert P^{t+1}(x,A)-\pi(A)\rvert\le\sum_yP(x,y)\lvert P^t(y,A)-\pi(A)\rvert\le d(t)$ である。
3:$t=t_{\mathrm{mix}}(\varepsilon)$ では $\bar d(t)\le2d(t)\le2\varepsilon$ なので、2 から $d(\ell t)\le(2\varepsilon)^\ell$ である。$\varepsilon=1/4$ では $d(\ell\,t_{\mathrm{mix}})\le2^{-\ell}$ で、$\ell=\lceil\log_2(1/\varepsilon)\rceil$ と置けば $2^{-\ell}\le\varepsilon$ となる。$\square$

正の冪をもつ連鎖の混合時間は有限

ある $r\ge1$ と $\delta>0$ で、すべての $x,y$ について $P^r(x,y)\ge\delta$ とする。このとき $\pi$ は $P$ のただ 1 つの定常分布で、
$$ d(t)\le\bigl(1-\lvert\mathcal X\rvert\delta\bigr)^{\lfloor t/r\rfloor} $$
であり、すべての $0< \varepsilon< 1$ で $t_{\mathrm{mix}}(\varepsilon)< \infty$ である。

証明を開く

prop-mix-tv の 1 により $\|P^r(x,\cdot)-P^r(y,\cdot)\|_{\mathrm{TV}}=1-\sum_z\min\{P^r(x,z),P^r(y,z)\}\le1-\lvert\mathcal X\rvert\delta$ なので $\bar d(r)\le1-\lvert\mathcal X\rvert\delta$ である。thm-mix-coupling の 1 と thm-mix-submult の 1・2 から $d(t)\le\bar d(t)\le\bar d(r\lfloor t/r\rfloor)\le\bar d(r)^{\lfloor t/r\rfloor}$ で、右辺は $0$ に収束する。定常分布 $\pi'$ がほかにあれば、$\pi'$ についても同じ評価が成り立つので $\|\pi-\pi'\|_{\mathrm{TV}}\le\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}+\|P^t(x,\cdot)-\pi'\|_{\mathrm{TV}}\to0$ となり、$\pi=\pi'$ である。$\square$

固有値による評価

$P$ の固有値は絶対値が $1$ 以下で、$1$ は固有値である(定数関数が右固有ベクトル)。$1$ 以外の固有値の大きさが混合の速さの目安になる。

固有値による下界

$\lambda\ne1$ を $P$ の(複素数でもよい)固有値とする。すべての $t$ で $\lvert\lambda\rvert^t\le2d(t)$ であり、$0< \varepsilon< 1/2$ について
$$ t_{\mathrm{mix}}(\varepsilon)\ge\Bigl(\frac1{1-\lvert\lambda\rvert}-1\Bigr)\log\frac1{2\varepsilon} $$
である($\lvert\lambda\rvert=1$ なら右辺は $\infty$ と読み、$t_{\mathrm{mix}}(\varepsilon)=\infty$ を主張する)。

固有関数の平均は 0

$f\colon\mathcal X\to\mathbb C$ を $Pf=\lambda f$、$f\ne0$ とする($(Pf)(x)=\sum_yP(x,y)f(y)$)。$\pi P=\pi$ から $\sum_x\pi(x)f(x)=\sum_x(\pi P)(x)f(x)=\sum_x\pi(x)(Pf)(x)=\lambda\sum_x\pi(x)f(x)$ で、$\lambda\ne1$ なので $\sum_x\pi(x)f(x)=0$ である。よって
$$ \lvert\lambda^tf(x)\rvert=\lvert(P^tf)(x)\rvert=\Bigl\lvert\sum_y\bigl(P^t(x,y)-\pi(y)\bigr)f(y)\Bigr\rvert\le\max_y\lvert f(y)\rvert\sum_y\lvert P^t(x,y)-\pi(y)\rvert\le2d(t)\max_y\lvert f(y)\rvert $$
である(最後は prop-mix-tv の 1)。$\lvert f(x)\rvert$ が最大の $x$ を選べば $\lvert\lambda\rvert^t\le2d(t)$ を得る。
$t=t_{\mathrm{mix}}(\varepsilon)$ では $\lvert\lambda\rvert^t\le2\varepsilon< 1$ で、これを $t$ について解けば後半を得る。

後半の計算を開く

$\lvert\lambda\rvert=1$ ならこれは起こりえないので $t_{\mathrm{mix}}(\varepsilon)=\infty$ である。$\lambda=0$ なら主張の右辺は $0$ で自明である。$0< \lvert\lambda\rvert< 1$ なら $t\log(1/\lvert\lambda\rvert)\ge\log(1/(2\varepsilon))$ で、$0< u\le1$ で $\log(1/u)\le1/u-1$ が成り立つ($h(u)=1/u-1+\log u$ は $h(1)=0$、$h'(u)=(u-1)/u^2\le0$)ので、$\log(1/\lvert\lambda\rvert)\le(1-\lvert\lambda\rvert)/\lvert\lambda\rvert$ である。よって $t\ge\frac{\lvert\lambda\rvert}{1-\lvert\lambda\rvert}\log\frac1{2\varepsilon}=\bigl(\frac1{1-\lvert\lambda\rvert}-1\bigr)\log\frac1{2\varepsilon}$ を得る。$\square$

$\pi(x)P(x,y)=\pi(y)P(y,x)$ がすべての $x,y$ で成り立つとき、$P$ は 可逆 であるという(Markov連鎖モンテカルロ法 の詳細釣り合い)。可逆な $P$ の固有値は実数である。$\lambda_\star:=\max\{\lvert\lambda\rvert:\lambda\text{ は }1\text{ と異なる固有値}\}$ と置き、$t_{\mathrm{rel}}:=1/(1-\lambda_\star)$ を 緩和時間 という。可逆な連鎖では、下界と対になる上界が成り立つ。

緩和時間による上界

$P$ が可逆かつ既約で、$\lambda_\star< 1$ とし、$\pi_{\min}:=\min_x\pi(x)$ とする。$0< \varepsilon< 1$ について
$$ t_{\mathrm{mix}}(\varepsilon)\le\Bigl\lceil t_{\mathrm{rel}}\Bigl(\frac12\log\frac1{\pi_{\min}}+\log\frac1{2\varepsilon}\Bigr)\Bigr\rceil\le t_{\mathrm{rel}}\log\frac1{\varepsilon\,\pi_{\min}} $$
である。

この記事では証明しない。LPW17 Theorem 12.4(p. 163)。証明は $P$ を $\pi$ で重みを付けた内積に関する対称作用素として固有関数で展開し、Cauchy–Schwarz の不等式で $\lvert P^t(x,y)/\pi(y)-1\rvert$ を抑える。prop-mix-eigen とあわせると、可逆な連鎖の混合時間は $\log(1/\pi_{\min})$ 倍の範囲で緩和時間で決まる。

計算の手順

混合時間を評価するときは、次の順に進める。

  1. 連鎖を確かめる:状態空間・推移行列・定常分布 $\pi$ を書き、$P^r>0$ となる $r$ があるか(既約で非周期的か)を確かめる。周期的なら、確率 $1/2$ でその場に留まる 怠惰な連鎖 $\frac12(I+P)$ に替える(定常分布は変わらない)。
  2. 下界を出す:$1$ 以外の固有値 $\lambda$ を一つ見つけて prop-mix-eigen を使う。または、出発点から $t$ 歩では到達しにくい事象 $A$ を見つけて $d(t)\ge P^t(x,A^c)-\pi(A^c)$ と評価する。
  3. 上界を出す:同じ乱数で 2 つの連鎖を動かす結合を設計し、合流時刻 $\tau$ の裾 $\Pr(\tau>t)$ か期待値 $E[\tau]$ を評価して thm-mix-coupling を使う。可逆なら thm-mix-relax も使える。
  4. 精度を変える:$t_{\mathrm{mix}}$ から $t_{\mathrm{mix}}(\varepsilon)$ へは thm-mix-submult の 3 で移る。
  5. 小さな場合で照らす:$P^t$ を直接計算して $d(t)$ を求め、上界・下界と比べる。対称性があれば状態を縮約する(超立方体では Hamming 重み)。上界と下界の比が大きければ、結合か下界の事象を改良する。

例題

2 状態の連鎖

$\mathcal X=\{0,1\}$、$P=\begin{pmatrix}1-p&p\\q&1-q\end{pmatrix}$($0< p+q< 2$)とする。定常分布は $\pi=\bigl(\frac q{p+q},\frac p{p+q}\bigr)$、$\lambda:=1-p-q$ と置くと
$$ d(t)=\frac{\max\{p,q\}}{p+q}\lvert\lambda\rvert^t,\qquad \bar d(t)=\lvert\lambda\rvert^t $$
である。使う公式:def-mix-time、prop-mix-tv の 1。
答え:$p=0.3$、$q=0.1$ では $d(t)=0.75\times0.6^t$ で、$d(2)=0.27$、$d(3)=0.162$ なので $t_{\mathrm{mix}}=3$ である。$t_{\mathrm{mix}}(0.01)=9$($d(9)\approx0.00756$)で、thm-mix-submult の上界 $\lceil\log_2100\rceil\cdot3=21$ と prop-mix-eigen の下界 $1.5\log50\approx5.868$ の間にある。

途中の計算を開く

行ベクトル $v=(1,-1)$ は $vP=(1-p-q,\,-(1-p-q))=\lambda v$ を満たす。$\delta_0-\pi=\frac p{p+q}v$、$\delta_1-\pi=-\frac q{p+q}v$ なので、$P^t(0,\cdot)-\pi=\frac p{p+q}\lambda^tv$、$P^t(1,\cdot)-\pi=-\frac q{p+q}\lambda^tv$ である。$v$ の成分の絶対値の和は $2$ なので、prop-mix-tv の 1 から $\|P^t(0,\cdot)-\pi\|_{\mathrm{TV}}=\frac12\cdot\frac p{p+q}\lvert\lambda\rvert^t\cdot2=\frac p{p+q}\lvert\lambda\rvert^t$ などを得る。差 $P^t(0,\cdot)-P^t(1,\cdot)=\lambda^tv$ から $\bar d(t)=\lvert\lambda\rvert^t$。数値では $0.75\times0.6^2=0.27>0.25\ge0.75\times0.6^3=0.162$。$\varepsilon=0.01$ では $0.75\times0.6^8\approx0.0126>0.01\ge0.75\times0.6^9\approx0.00756$。下界は固有値 $\lambda=0.6$ で $\bigl(\frac1{0.4}-1\bigr)\log\frac1{0.02}=1.5\log50$。

超立方体 $\{0,1\}^n$ の上の 怠惰なランダムウォーク は、確率 $1/2$ でその場に留まり、確率 $1/2$ で $n$ 個の隣(座標を 1 つだけ反転した点)から一様に選んで移る連鎖である。定常分布は一様分布 $2^{-n}$ である。

超立方体の怠惰なランダムウォーク

$c>0$ について $d(\lceil n\log n+cn\rceil)\le e^{-c}$ である。したがって $0< \varepsilon< 1$ について $t_{\mathrm{mix}}(\varepsilon)\le\lceil n\log n+n\log(1/\varepsilon)\rceil$ である。

同じ座標に同じビットを書き込む

怠惰なランダムウォークの 1 歩は「座標 $i$ を一様に選び、公平な硬貨で決めたビット $b$ を座標 $i$ に書き込む」と同じ分布をもつ。実際、$b$ が現在の値と同じ確率は $1/2$ でその場に留まり、座標 $i$ だけが反転する確率は $\frac1n\cdot\frac12$ である。
$x$ と $y$ から出発する 2 つの連鎖を、各時刻に 同じ $i$ と 同じ $b$ で動かす。各連鎖は単独では怠惰なランダムウォークである。座標 $i$ が一度選ばれると、その後は両者の座標 $i$ が一致し続ける。$\sigma$ をすべての座標が少なくとも一度選ばれる最初の時刻とすると、時刻 $\sigma$ 以降の 2 つの連鎖は同じ点にあり、同じ規則で動くので離れない。よって合流時刻 $\tau$ は $\tau\le\sigma$ を満たす。
$t=\lceil n\log n+cn\rceil$ とし、$A_i$ を「最初の $t$ 歩で座標 $i$ が一度も選ばれない」事象とする。各歩で $i$ が選ばれない確率は $1-1/n$ で、歩ごとに独立だから、$1-u\le e^{-u}$ を使って
$$ \Pr(\sigma>t)=\Pr\Bigl(\bigcup_{i=1}^nA_i\Bigr)\le\sum_{i=1}^n\Bigl(1-\frac1n\Bigr)^t\le ne^{-t/n}\le ne^{-\log n-c}=e^{-c} $$
である。thm-mix-coupling の 3 から $d(t)\le\max_{x,y}\Pr_{x,y}(\tau>t)\le e^{-c}$。$c=\log(1/\varepsilon)$ と置けば後半を得る。$\square$

超立方体での数値

$n=10$ とする。使う公式:prop-mix-hypercube、prop-mix-tv の 1。
答え:上界は $t_{\mathrm{mix}}\le\lceil10\log10+10\log4\rceil=\lceil36.889\rceil=37$ である。$d(t)$ を厳密に計算すると $t_{\mathrm{mix}}=16$、$d(37)\approx0.0251$ で、上界はおよそ 2 倍の余裕がある。$n=20$ では上界 $88$、厳密な値 $39$ である。

厳密な計算の方法を開く

出発点を $0=(0,\dots,0)$ とする(推移行列は座標の並べ替えと各座標の反転で不変なので、どの出発点でも距離は同じ)。$P^t(0,\cdot)$ と一様分布はともに Hamming 重み $w(x)=\sum_ix_i$ が同じ点で等しい値をとるので、全変動距離は重みの分布の全変動距離 $\frac12\sum_{k=0}^n\bigl\lvert\Pr(W_t=k)-\binom nk2^{-n}\bigr\rvert$ に等しい。重み $W_t$ は $\{0,\dots,n\}$ 上の連鎖で、$k\to k-1$ の確率 $\frac k{2n}$、$k\to k+1$ の確率 $\frac{n-k}{2n}$、残りは留まる。この $n+1$ 状態の推移を $t$ 回繰り返して $d(t)$ を求めた。

図: 超立方体 {0,1}^n の怠惰なランダムウォークの d(t) を、横軸 t/(n log n) で n=10(点線)、n=50(破線)、n=250(実線)について描いた。n が大きくなるほど、d(t) は t/(n log n)=1/2(灰色の実線)の付近で 1 から 0 へ急に落ちる。灰色の破線は結合の上界の主要項 n log n、点線の横線は 1/4。 図: 超立方体 {0,1}^n の怠惰なランダムウォークの d(t) を、横軸 t/(n log n) で n=10(点線)、n=50(破線)、n=250(実線)について描いた。n が大きくなるほど、d(t) は t/(n log n)=1/2(灰色の実線)の付近で 1 から 0 へ急に落ちる。灰色の破線は結合の上界の主要項 n log n、点線の横線は 1/4。
図のように、$n$ が大きくなると $d(t)$ は $t\approx\frac12n\log n$ の付近で急に $1$ から $0$ へ落ちる。結合の上界 $n\log n$ は主要項で 2 倍の余裕がある。

円周の上の怠惰なランダムウォーク

$\mathcal X=\mathbb Z/n\mathbb Z$($n\ge3$)で、確率 $1/2$ で留まり、確率 $1/4$ ずつ $\pm1$ に動く連鎖を考える。定常分布は一様である。使う公式:thm-mix-coupling、prop-mix-eigen、thm-mix-relax。
答え:結合で $t_{\mathrm{mix}}\le n^2$、固有値 $\lambda_2=\frac12(1+\cos\frac{2\pi}n)$ で $t_{\mathrm{mix}}\ge(t_{\mathrm{rel}}-1)\log2$ が成り立つ。$n=10$ では $\lambda_2\approx0.904508$、$t_{\mathrm{rel}}\approx10.4721$ で、下界 $6.5656$、thm-mix-relax の上界 $10.4721\log40\approx38.630$、結合の上界 $100$ に対し、厳密な値は $t_{\mathrm{mix}}=10$ である。$n=20$ では厳密な値 $38$ である。

途中の計算を開く

結合:$x,y$ から出発し、出会うまでは各時刻に公平な硬貨で 2 つのうち一方だけを選び、選んだ方を確率 $1/2$ ずつ $\pm1$ に動かす。出会った後は同じ乱数で同じように動かす。各連鎖は単独で確率 $1/2$ で留まり $1/4$ ずつ $\pm1$ に動くので、元の連鎖である。$X_t$ から $Y_t$ へ正の向きに測った距離 $D_t\in\{0,\dots,n\}$ は、出会うまで $1/2$ ずつ $\pm1$ に動き、$0$ か $n$ に達すると合流する。一度に一方しか動かないので、すれ違うことはない。

合流時刻の期待値:$f(k)=k(n-k)$ は $f(0)=f(n)=0$、$\frac12\bigl(f(k-1)+f(k+1)\bigr)=f(k)-1$ を満たす。よって $E[f(D_{(t+1)\wedge\tau})]=E[f(D_{t\wedge\tau})]-\Pr(\tau>t)$ で、足し合わせると $E[f(D_{t\wedge\tau})]=f(D_0)-E[t\wedge\tau]$。左辺は $0$ 以上なので $E[t\wedge\tau]\le f(D_0)\le n^2/4$ で、$t\to\infty$ として(単調収束定理)$E[\tau]\le n^2/4$。thm-mix-coupling の 3 の証明と同じく $\Pr(\tau>t)\le n^2/(4t)$ なので、$t=n^2$ で $d(t)\le1/4$。

固有値:$\omega=e^{2\pi i/n}$、$\varphi_j(k)=\omega^{jk}$ と置くと $(P\varphi_j)(k)=\frac12\omega^{jk}+\frac14(\omega^{j(k+1)}+\omega^{j(k-1)})=\frac12(1+\cos\frac{2\pi j}n)\varphi_j(k)$ なので、固有値は $\frac12(1+\cos\frac{2\pi j}n)$($j=0,\dots,n-1$)で、どれも $0$ 以上である。$1$ 以外で最大のものが $\lambda_2$ で $\lambda_\star=\lambda_2$。$n=10$ では $\pi_{\min}=0.1$、$\varepsilon=1/4$ で $\log\frac1{\varepsilon\pi_{\min}}=\log40$。

結合の上界 $n^2$ は粗いが、次数 $n^2$ は正しい。逆向きに $t_{\mathrm{mix}}\ge n^2/32$ が Chebyshev の不等式で示せる(LPW17 §5.3.2、pp. 63–64。この記事では証明しない)。

トランプの riffle shuffle

52 枚のトランプを 2 つの山に分けて交互に落とし込む切り方(Gilbert–Shannon–Reeds の模型)を繰り返す Markov 連鎖は、状態が $52!$ 個の置換で、定常分布は一様分布である。Bayer と Diaconis(1992)は、7 回切った後の一様分布からの全変動距離を約 $0.3341$ と計算した(LPW17 Chapter 8 の Notes、p. 114。この記事では証明しない)。7 回では「どの事象の確率も一様な場合と $0.334$ 以内で一致する」ことしか保証されない。

使える条件と反例

cor-mix-finite の結論(すべての $\varepsilon$ で $t_{\mathrm{mix}}(\varepsilon)< \infty$)は、節「定義と使える条件」の (i)〜(iii) のもとで成り立つ。各行は (i)〜(iii) のちょうど 1 つを外す。

外す条件反例成り立たなくなること
(iii) 非周期性$\mathcal X=\{0,1\}$、$P=\begin{pmatrix}0&1\\1&0\end{pmatrix}$(既約、定常分布 $(\frac12,\frac12)$)$d(t)=\frac12$ がすべての $t$ で成り立ち、$\varepsilon< 1/2$ で $t_{\mathrm{mix}}(\varepsilon)=\infty$
(ii) 既約性$\mathcal X=\{0,1\}$、$P=I$(各状態が吸収状態で非周期的)定常分布が一つに決まらない。$\pi=(\frac12,\frac12)$ では $d(t)=\frac12$、$\bar d(t)=1$ のまま
(i) 有限性$\mathcal X=\{0,1,2,\dots\}$、$P(x,x-1)=\frac23$、$P(x,x+1)=\frac13$($x\ge1$)、$P(0,0)=\frac23$、$P(0,1)=\frac13$(既約・非周期的、定常分布 $\pi(x)=2^{-x-1}$)出発点 $0$ からは距離が速く小さくなるが、$d(t)=\sup_x\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}=1$ がすべての $t$ で成り立つ
反例の確かめを開く

1 行目:$P^t(0,\cdot)$ は $t$ が偶数なら $\delta_0$、奇数なら $\delta_1$ で、どちらも $\pi$ との距離は $\frac12$。固有値 $-1$ があるので prop-mix-eigen からも $t_{\mathrm{mix}}(\varepsilon)=\infty$ が出る。2 行目:$P^t=I$ なので $P^t(0,\cdot)=\delta_0$、どの確率ベクトルも定常分布である。3 行目:$\pi(x)P(x,x+1)=2^{-x-1}\cdot\frac13=2^{-x-2}\cdot\frac23=\pi(x+1)P(x+1,x)$ なので $\pi$ は可逆な定常分布である。$x>t$ から出発すると $t$ 歩後の位置は $[x-t,x+t]$ にあるので、$A=[x-t,x+t]$ について $P^t(x,A)-\pi(A)\ge1-\pi([x-t,\infty))=1-2^{-(x-t)}$。$x\to\infty$ として上限は $1$ である。数値では $t=10$ で出発点 $0$ なら距離 $\approx0.0354$、出発点 $30$ なら $\approx0.999999$。

よくある誤り

誤り正しくはなぜ
$d$ も劣乗法的とみなして $d(s+t)\le d(s)d(t)$ を使う劣乗法的なのは $\bar d$ で、$d(\ell t)\le\bar d(t)^\ell\le(2d(t))^\ell$2 状態の連鎖で $p=q=\frac14$ とすると $d(1)=\frac14$、$d(2)=\frac18>d(1)^2=\frac1{16}$
2 つの連鎖を独立に走らせて合流時刻を測る出会った後は同じ乱数で動かし、出会いやすい結合を設計する独立だと出会っても離れ、周期的な部分があると出会わないこともある(怠惰でない円周の歩みで $n$ が偶数、距離が奇数)
1 つの出発点の $\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}$ で混合時間を決める出発点について最大をとる反例の表の 3 行目では出発点 $0$ からの距離は $t=10$ で約 $0.0354$ だが $d(t)=1$
全変動距離を $\sum_x\lvert\mu(x)-\nu(x)\rvert$ と $\frac12\sum_x\lvert\mu(x)-\nu(x)\rvert$ で混同する規約を確かめて換算する2 倍違い、$t_{\mathrm{mix}}(\varepsilon)$ の $\varepsilon$ の意味が変わる
第 2 固有値だけで上界を出す可逆な連鎖で $\lambda_\star$(絶対値の最大)と $\log(1/\pi_{\min})$ を使う固有値 $-1$ に近いものがあると遅い。怠惰な連鎖に替えれば固有値は $0$ 以上

補足

cutoff 現象:連鎖の列について、すべての $0< \varepsilon< 1$ で $t^{(n)}_{\mathrm{mix}}(\varepsilon)/t^{(n)}_{\mathrm{mix}}(1-\varepsilon)\to1$ となるとき、列は cutoff をもつという(LPW17 §18.1、p. 261)。超立方体の怠惰なランダムウォークは $\frac12n\log n$ に cutoff をもつ(LPW17 Theorem 18.3、p. 265。この記事では証明しない)。図の曲線はこの現象を示している。
強定常時刻:その時刻の位置が定常分布に従い時刻と独立になる停止時刻 $\tau$ からも $d(t)$ の上界が得られる。トランプの一番上の 1 枚を無作為な位置に差し込む切り方の上界はこの方法による(LPW17 §6.5.3、p. 82。この記事では証明しない)。Markov連鎖モンテカルロ法 で何歩捨ててから標本を使えばよいかの保証も混合時間で与えられる。

関連項目

参考文献

[1]
David A. Levin, Yuval Peres (with contributions by Elizabeth L. Wilmer), Markov Chains and Mixing Times, American Mathematical Society, 2017, Proposition 1.7(p. 7)、§5.3.2(pp. 63–64)、§6.5.3(p. 82)、Chapter 8 の Notes(p. 114)、Theorem 12.4(p. 163)、§18.1(p. 261)、Theorem 18.3(p. 265)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する