カップリング(確率論)

同義語:coupling (probability theory)

概要

カップリング(確率論)(coupling)とは、2 つの確率分布 $\mu,\nu$ に対し、同じ確率空間の上で $X$ の分布が $\mu$、$Y$ の分布が $\nu$ となるように作った確率変数の組 $(X,Y)$、またはその同時分布のことで、結合ともいう。どのカップリングでも全変動距離は $\Pr(X\ne Y)$ 以下で、等号を実現する最大カップリングがある。実数直線の上では、$X\le Y$ となるカップリングがあることと確率順序 $\mu\preceq\nu$ は同値である。既約で非周期的な可算状態の Markov 連鎖が定常分布をもつとき、2 つの連鎖を独立に走らせて出会う時刻を使うと、推移確率が定常分布に収束することが証明できる。

$$\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連鎖

2 つの確率分布 $\mu,\nu$ を比べたいとき、それぞれに従う確率変数 $X,Y$ を別々に考える必要はない。同じ確率空間の上に $X$ と $Y$ を、互いにうまく関係づけて作ってよい。たとえば、表の確率が $p$ と $r$($p\le r$)の硬貨を 1 回ずつ投げる代わりに、$[0,1)$ の一様乱数 $U$ を 1 つだけ引いて $X=\mathbf 1\{U< p\}$、$Y=\mathbf 1\{U< r\}$ とすれば、$X\le Y$ がいつも成り立ち、$X\ne Y$ となる確率は $r-p$ である。このように分布を保ったまま 2 つの確率変数を同じ空間に載せたものを カップリング(coupling)という。日本語では 結合 ともいう。
カップリングは比べ方の道具である。$\Pr(X\ne Y)$ が小さければ、どの事象の確率も $\mu$ と $\nu$ でほとんど変わらない(全変動距離の評価)。$X\le Y$ がいつも成り立てば、増加関数の期待値は $\nu$ のほうが大きい(確率順序)。同じ推移確率で動く 2 つの Markov 連鎖を同じ空間で走らせ、出会った後は区別できないことを使えば、分布が定常分布に近づくことが分かる。この記事では、カップリングの定義、全変動距離とカップリングの関係(最大カップリング)、実数直線の上の確率順序とカップリングの同値性を証明し、主定理として、可算状態の Markov 連鎖の収束定理をカップリングで証明する。

定義

カップリング

$(E,\mathcal E)$、$(F,\mathcal F)$ を可測空間とし、$\mu$ を $E$ の上の、$\nu$ を $F$ の上の確率測度とする。

  1. 積空間 $(E\times F,\mathcal E\otimes\mathcal F)$ の上の確率測度 $\gamma$ で、すべての $A\in\mathcal E$、$B\in\mathcal F$ について $\gamma(A\times F)=\mu(A)$、$\gamma(E\times B)=\nu(B)$ を満たすものを、$\mu$ と $\nu$ の カップリング という。その全体を $\Pi(\mu,\nu)$ と書く。
  2. ある確率空間 $(\Omega,\mathcal A,\Pr)$ の上の確率変数の組 $(X,Y)$ で、$X$ の分布が $\mu$、$Y$ の分布が $\nu$ であるものも、$\mu$ と $\nu$ のカップリングという。
  3. 確率過程の組 $(X_t,Y_t)_{t\ge0}$ が同じ確率空間の上にあり、$(X_t)$ と $(Y_t)$ がそれぞれ指定された法則をもつとき、これを 2 つの法則のカップリングという。

2 の組 $(X,Y)$ の同時分布は 1 の意味のカップリングである。逆に 1 の $\gamma$ があれば、$\Omega=E\times F$、$\Pr=\gamma$ とし、$X,Y$ を 2 つの座標への射影とすれば 2 の意味のカップリングになる。$\Pi(\mu,\nu)$ は空でない。積測度 $\mu\otimes\nu$($X$ と $Y$ を独立にとるもの)がつねに属するからである。同じ対象は Wasserstein距離 と 最適輸送 でも「結合」「輸送計画」の名で使われ、そこでは費用の期待値を最小にするカップリングを探す。

基本的なカップリング
  1. 独立カップリング:$\gamma=\mu\otimes\nu$。最も単純だが、$X$ と $Y$ を近づける働きはない。
  2. 対角カップリング:$\mu=\nu$ のとき、$X\sim\mu$ をとって $Y:=X$ とする。
  3. 分位点カップリング:$\mu,\nu$ を実数直線の上の分布とし、分布関数を $F_\mu,F_\nu$ とする。$(0,1)$ の一様分布に従う $U$ を 1 つとり、$X:=Q_\mu(U)$、$Y:=Q_\nu(U)$ とおく。ここで $Q_\mu(u):=\sup\{y\mid F_\mu(y)< u\}$ である。確率変数の収束 の補題「分位点関数による実現」により $X\sim\mu$、$Y\sim\nu$ である。
  4. 冒頭の硬貨の例は、3 で $U$ を $1-U$(これも一様分布に従う)に替えたもので、Bernoulli分布 の命題「同じ一様変数から作る」にあたる。

公式の表

内容式条件根拠
カップリングの不等式$\Vert\mu-\nu\Vert_{\mathrm{TV}}\le\Pr(X\ne Y)$$(X,Y)$ はカップリング、対角が可測thm-cp-maximal
最大カップリング$\Pr(X\ne Y)=\Vert\mu-\nu\Vert_{\mathrm{TV}}$ となる $(X,Y)$ がある対角が可測thm-cp-maximal
密度による表示$\Vert\mu-\nu\Vert_{\mathrm{TV}}=1-\int\min(f,g)\,d\lambda$$f,g$ は $\lambda=\mu+\nu$ に関する密度thm-cp-maximal
確率順序$\mu\preceq\nu$ ⇔ $X\le Y$ となるカップリングがある$\mathbb R$ の上の分布thm-cp-order
収束定理$\sup_A\lvert p^{(n)}_i(A)-\pi(A)\rvert\le\Pr(T>n)\to0$可算状態、既約、非周期、定常分布 $\pi$thm-cp-convergence

全変動距離と最大カップリング

可測空間 $(E,\mathcal E)$ の上の確率測度 $\mu,\nu$ の 全変動距離 を
$$ \Vert\mu-\nu\Vert_{\mathrm{TV}}:=\sup_{A\in\mathcal E}\lvert\mu(A)-\nu(A)\rvert $$
で定める。状態が有限個の場合は 混合時間 の命題「全変動距離の 3 つの表し方」に証明がある。次の定理はこれを一般の可測空間に広げる。

カップリングの不等式と最大カップリング

$\mu,\nu$ を $(E,\mathcal E)$ の上の確率測度とし、$\lambda:=\mu+\nu$ とする。Radon–Nikodymの定理 により $\mu=f\lambda$、$\nu=g\lambda$ となる可測関数 $f,g\ge0$ をとり、$D:=\{f>g\}$ とおく。

  1. $\Vert\mu-\nu\Vert_{\mathrm{TV}}=\mu(D)-\nu(D)=1-\int_E\min(f,g)\,d\lambda=\frac12\int_E\lvert f-g\rvert\,d\lambda$ である。
  2. 対角集合 $\Delta:=\{(x,x)\mid x\in E\}$ が $\mathcal E\otimes\mathcal E$ に属するとする。このとき、$\mu$ と $\nu$ のどのカップリング $(X,Y)$ についても $\Vert\mu-\nu\Vert_{\mathrm{TV}}\le\Pr(X\ne Y)$ である。
  3. 2 の仮定のもとで、$\Pr(X\ne Y)=\Vert\mu-\nu\Vert_{\mathrm{TV}}$ となるカップリングが存在する。これを 最大カップリング という。
密度の小さいほうを共有させる

要点:1 は $D$ で上限に達すること、2 は $\{X=Y\}$ の上で $X\in A$ と $Y\in A$ が一致すること、3 は密度の共通部分 $\min(f,g)$ の上で $X=Y$ とし、残りを別々にとる構成による。

詳しい証明を開く

1:任意の $A\in\mathcal E$ について $\mu(A)-\nu(A)=\int_A(f-g)\,d\lambda\le\int_{A\cap D}(f-g)\,d\lambda\le\int_D(f-g)\,d\lambda=\mu(D)-\nu(D)$ である。$\mu,\nu$ の全質量はともに $1$ なので、同じく $\nu(A)-\mu(A)\le\nu(D^c)-\mu(D^c)=\mu(D)-\nu(D)$ である。$A=D$ で等号が成り立つから $\Vert\mu-\nu\Vert_{\mathrm{TV}}=\mu(D)-\nu(D)$ である。$\int\min(f,g)\,d\lambda=\nu(D)+\mu(D^c)=1-(\mu(D)-\nu(D))$ であり、$\frac12\int\lvert f-g\rvert\,d\lambda=\frac12\bigl((\mu(D)-\nu(D))+(\nu(D^c)-\mu(D^c))\bigr)=\mu(D)-\nu(D)$ である。

2:$\{X\ne Y\}=\{(X,Y)\notin\Delta\}$ は事象である。どの $A\in\mathcal E$ についても $\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)$ で、$X$ と $Y$ を入れ替えても同じである。

3:$p:=\int\min(f,g)\,d\lambda$ とおく。$p=1$ なら 1 により $\mu=\nu$ で、対角カップリングをとればよい。$p=0$ なら $\Vert\mu-\nu\Vert_{\mathrm{TV}}=1$ で、2 により独立カップリングでも $\Pr(X\ne Y)=1$ である。$0< p< 1$ とする。1 により $(f-g)^+\lambda$ と $(g-f)^+\lambda$ の全質量はともに $1-p$ である。互いに独立な $\xi,V,X',Y'$ を、$\Pr(\xi=1)=p=1-\Pr(\xi=0)$、$V\sim\min(f,g)\lambda/p$、$X'\sim(f-g)^+\lambda/(1-p)$、$Y'\sim(g-f)^+\lambda/(1-p)$ となるようにとる(積測度の空間で座標をとればよい)。$\xi=1$ なら $(X,Y):=(V,V)$、$\xi=0$ なら $(X,Y):=(X',Y')$ とおく。$X$ の分布は $\min(f,g)\lambda+(f-g)^+\lambda=f\lambda=\mu$、$Y$ の分布は同じく $\nu$ である。$X'$ は確率 $1$ で $D$ に、$Y'$ は確率 $1$ で $\{g>f\}\subset D^c$ に値をとるので、$\xi=0$ なら $X\ne Y$ である。よって $\Pr(X\ne Y)=1-p=\Vert\mu-\nu\Vert_{\mathrm{TV}}$ である。$\square$

$E$ が可分な距離空間で $\mathcal E$ がその Borel 集合族なら、$\Delta$ は $E\times E$ の閉集合で、$E\times E$ の Borel 集合族は $\mathcal E\otimes\mathcal E$ に等しいので、2 の仮定は満たされる。定理の 2 と 3 を合わせると
$$ \Vert\mu-\nu\Vert_{\mathrm{TV}}=\min\{\Pr(X\ne Y)\mid(X,Y)\text{ は }\mu,\nu\text{ のカップリング}\} $$
である。これは、距離 $d(x,y)=\mathbf 1\{x\ne y\}$ について費用の期待値 $\mathrm E[d(X,Y)]$ を最小にする輸送問題の値が全変動距離であることを言っている(Wasserstein距離 の $p=1$ の場合にあたる)。全変動距離の上界がほしいときは、$\Pr(X\ne Y)$ が小さいカップリングを 1 つ作ればよい。下界がほしいときは、$\mu(A)-\nu(A)$ が大きい事象 $A$ を 1 つ見つければよい。

確率順序と単調なカップリング

実数直線の上の確率分布 $\mu,\nu$ について、すべての $t\in\mathbb R$ で $\mu((t,\infty))\le\nu((t,\infty))$ が成り立つとき、$\nu$ は $\mu$ を 確率的に優越する といい、$\mu\preceq\nu$ と書く。分布関数でいえば $F_\mu\ge F_\nu$ である。

実数直線の上の確率順序

$\mu,\nu$ を $\mathbb R$ の上の確率分布とする。次の 3 条件は同値である。

  1. $\mu\preceq\nu$。
  2. $\mu$ と $\nu$ のカップリング $(X,Y)$ で、確率 $1$ で $X\le Y$ となるものがある。
  3. 有界で単調非減少な可測関数 $h\colon\mathbb R\to\mathbb R$ のすべてについて $\int h\,d\mu\le\int h\,d\nu$。
同じ一様乱数の分位点をとる

1 ⇒ 2。 ex-cp-basic の 3 の分位点カップリング $X=Q_\mu(U)$、$Y=Q_\nu(U)$ をとる。$u\in(0,1)$ を固定し、$x:=Q_\nu(u)$ とおく。確率変数の収束 の補題「分位点関数による実現」の同値「$Q(u)\le x$ ⇔ $u\le F(x)$」を $\nu$ に使うと $u\le F_\nu(x)$ で、仮定 $F_\nu\le F_\mu$ から $u\le F_\mu(x)$ である。同じ同値を $\mu$ に使うと $Q_\mu(u)\le x=Q_\nu(u)$ である。よってすべての $u$ で $Q_\mu(u)\le Q_\nu(u)$ であり、$X\le Y$ がいつも成り立つ。
2 ⇒ 3。 $h$ は単調非減少なので、確率 $1$ で $h(X)\le h(Y)$ である。有界なので期待値をとって $\int h\,d\mu=\mathrm E[h(X)]\le\mathrm E[h(Y)]=\int h\,d\nu$ である。
3 ⇒ 1。 $h:=\mathbf 1_{(t,\infty)}$ は有界で単調非減少なので、$\mu((t,\infty))\le\nu((t,\infty))$ である。$\square$

条件 3 は、LPW17 Lemma 22.5(p. 307)では連続な単調非減少関数で述べられている。半順序集合の上の分布では条件 3 を確率順序の定義にとる。状態が有限個の半順序集合でも 1 と 2 の同値(Strassen の定理)が成り立つ(LPW17 Theorem 22.6(p. 307)。証明は §22.8(p. 320)。この記事では証明しない)。同書 §22.10(p. 322)によれば、Strassen は半順序をもつ Polish 空間でこの同値を示した。

二項分布の単調性と距離

$0\le p\le r\le1$ とし、$U_1,\dots,U_n$ を独立な $(0,1)$ の一様乱数として $X:=\sum_k\mathbf 1\{U_k< p\}$、$Y:=\sum_k\mathbf 1\{U_k< r\}$ とおく。$X\sim\mathrm{Bin}(n,p)$、$Y\sim\mathrm{Bin}(n,r)$ で、いつも $X\le Y$ である。
確率順序。 thm-cp-order により $\mathrm{Bin}(n,p)\preceq\mathrm{Bin}(n,r)$ で、$\Pr(\mathrm{Bin}(n,p)\ge k)$ はどの $k$ でも $p$ について単調非減少である。$n=10$、$k=5$ では $p=0.3$ で $0.150268$、$p=0.5$ で $0.623047$ である。
距離。 $X\ne Y$ ならある $k$ で $p\le U_k< r$ なので、thm-cp-maximal の 2 により
$$ \Vert\mathrm{Bin}(n,p)-\mathrm{Bin}(n,r)\Vert_{\mathrm{TV}}\le\Pr(X\ne Y)=1-(1-(r-p))^n\le n(r-p) $$
である。$n=10$、$p=0.30$、$r=0.31$ では右辺の中央の値は $0.095618$ で、実際の距離は $0.026854$ である。このカップリングは最大カップリングではない。

主定理:Markov 連鎖の収束定理

状態空間 $S$ を可算集合、$P=(p_{ij})_{i,j\in S}$ を推移行列とし、$n$ 歩の推移確率を $p^{(n)}_{ij}$ と書く。既約性、周期、定常分布は Markov連鎖 の定義「到達可能性・既約性・吸収状態・周期」と「定常分布」の意味で使う。既約な連鎖ではすべての状態の周期が等しい(同記事の命題「互いに到達可能な状態の周期は等しい」)ので、その値が $1$ のとき 非周期的 という。$A\subset S$ について $p^{(n)}_i(A):=\sum_{j\in A}p^{(n)}_{ij}$、$\pi(A):=\sum_{j\in A}\pi_j$ と書き、出発点 $i$ の連鎖の確率を $\Pr_i$ と書く。

非周期な連鎖の推移確率はやがて正

$P$ が既約で非周期的なら、各 $i,j\in S$ に $N$ があって、$n\ge N$ のすべてで $p^{(n)}_{ij}>0$ である。

戻る時刻の集合は加法で閉じている

要点:$I:=\{n\ge1\mid p^{(n)}_{ii}>0\}$ は和について閉じ、最大公約数が $1$ なので、十分大きい整数をすべて含む。

詳しい証明を開く

$p^{(m+n)}_{ii}\ge p^{(m)}_{ii}p^{(n)}_{ii}$ なので $I$ は和で閉じている。$I$ の元を小さい順に並べ、先頭から $k$ 個の最大公約数を $d_k$ とすると $d_k$ は単調非増加な正の整数の列なので、ある $k$ で $d_k=\gcd I=1$ になる。Bézout の等式により整数 $c_1,\dots,c_k$ で $\sum_lc_la_l=1$($a_l\in I$)となるものがある。正の係数の部分を $A:=\sum_{c_l>0}c_la_l$、負の係数の部分を $B:=\sum_{c_l< 0}(-c_l)a_l$ とおくと $A=B+1$ である。$B=0$ なら $1=A\in I$ で、$I$ はすべての正の整数を含む。$B\ge1$ なら $B,B+1\in I$ である。$m\ge B^2$ を $m=qB+r$($0\le r< B$)と書くと $q\ge B>r$ なので $m=(q-r)B+r(B+1)\in I$ である。よって $m\ge B^2$ のすべてで $p^{(m)}_{ii}>0$ である。既約なので $p^{(K)}_{ij}>0$ となる $K$ があり、$p^{(m+K)}_{ij}\ge p^{(m)}_{ii}p^{(K)}_{ij}>0$ である。$\square$

定常分布をもつ既約な連鎖はどの状態にも到達する

$P$ が既約で定常分布 $\pi$ をもつなら、すべての $w,z\in S$ について $\Pr_w(\text{ある }n\ge0\text{ で }X_n=z)=1$ である。

定常な連鎖を時間でずらしても確率は変わらない

既約なので $\pi_x>0$ となる $x$ と $p^{(n)}_{xz}>0$ となる $n$ があり、$\pi_z=\sum_y\pi_yp^{(n)}_{yz}\ge\pi_xp^{(n)}_{xz}>0$ である。
初期分布 $\pi$ の連鎖を考え、$k\ge0$ について $G_k:=\{m\ge k\text{ のすべてで }X_m\ne z\}$ とおく。有限の時間区間の事象については、経路の確率の式(Markov連鎖 の命題「経路の確率による特徴づけ」)と $\pi P^k=\pi$ から $\Pr_\pi(k\le m\le k+N\text{ で }X_m\ne z)=\Pr_\pi(0\le m\le N\text{ で }X_m\ne z)$ である。$N\to\infty$ として確率の連続性から $\Pr_\pi(G_k)=\Pr_\pi(G_0)$ を得る。$k\ge1$ なら $\{X_0=z\}\cap G_k\subset G_k\setminus G_0$ で、$G_0\subset G_k$ なので右辺の確率は $\Pr_\pi(G_k)-\Pr_\pi(G_0)=0$ である。$\pi_z>0$ で割って、すべての $k\ge1$ について
$$ \Pr_z(m\ge k\text{ のすべてで }X_m\ne z)=0 $$
である。$w=z$ なら主張は明らかなので $w\ne z$ とし、既約性から $p^{(k)}_{zw}>0$ となる $k\ge1$ をとる。時刻 $k$ での Markov 性(経路の確率の式を有限の区間で使い、区間を伸ばして極限をとる)により
$$ 0=\Pr_z(X_k=w,\ m\ge k\text{ のすべてで }X_m\ne z)=p^{(k)}_{zw}\,\Pr_w(m\ge0\text{ のすべてで }X_m\ne z) $$
である。よって $\Pr_w(z\text{ に到達しない})=0$ である。$\square$

カップリングによる収束定理

$S$ を可算集合、$P$ を既約で非周期的な推移行列とし、定常分布 $\pi$ をもつとする。$i\in S$ とし、$X_0=i$ の連鎖 $(X_n)$ と初期分布 $\pi$ の連鎖 $(Y_n)$ を独立に走らせ、$T:=\inf\{n\ge0\mid X_n=Y_n\}$ とおく。このとき $\Pr(T< \infty)=1$ であり、すべての $n$ で
$$ \sup_{A\subset S}\bigl\lvert p^{(n)}_i(A)-\pi(A)\bigr\rvert\le\Pr(T>n)\xrightarrow[n\to\infty]{}0 $$
が成り立つ。とくにすべての $j$ で $p^{(n)}_{ij}\to\pi_j$ であり、定常分布は $\pi$ だけである。

出会った後の 2 つの連鎖は区別できない

組の連鎖。 $S\times S$ の上の推移行列 $q_{(a,b),(a',b')}:=p_{aa'}p_{bb'}$ を考える。$(X_n,Y_n)$ は初期分布 $\delta_i\otimes\pi$、推移行列 $q$ の Markov 連鎖である(経路の確率が独立な 2 つの連鎖の経路の確率の積になる)。$\pi\otimes\pi$ は $q$ の定常分布である:$\sum_{a,b}\pi_a\pi_bp_{aa'}p_{bb'}=\pi_{a'}\pi_{b'}$。
組の連鎖は既約。 $(a,b),(a',b')\in S\times S$ を任意にとる。lem-cp-aperiodic により、十分大きい $n$ で $p^{(n)}_{aa'}>0$ と $p^{(n)}_{bb'}>0$ が同時に成り立つので、$q^{(n)}_{(a,b),(a',b')}=p^{(n)}_{aa'}p^{(n)}_{bb'}>0$ である。非周期性を使うのはここだけである。
出会う。 $z\in S$ を 1 つ固定する。lem-cp-hit を $q$ と $\pi\otimes\pi$ に使うと、どの $(i,b)$ から出発しても組の連鎖は確率 $1$ で $(z,z)$ に到達する。$\Pr(T< \infty)\ge\sum_b\pi_b\Pr_{(i,b)}((z,z)\text{ に到達})=1$ である。
出会った後。 $m\le n$、$a\in S$、$B\subset S$ とする。事象 $\{T=m,\ X_m=Y_m=a\}$ は時刻 $m$ までの組の連鎖で決まるので、Markov 性により、その上で $X_n$ と $Y_n$ の条件付き分布はどちらも $p^{(n-m)}_{a\cdot}$ である:
$$ \Pr(T=m,\ X_m=a,\ X_n\in B)=\Pr(T=m,\ X_m=a)\,p^{(n-m)}_a(B)=\Pr(T=m,\ Y_m=a,\ Y_n\in B). $$
$m\le n$ と $a$ について和をとると $\Pr(X_n\in B,\ T\le n)=\Pr(Y_n\in B,\ T\le n)$ である。
結論。 $Y_n$ の分布は $\pi P^n=\pi$ なので、
$$ p^{(n)}_i(B)-\pi(B)=\Pr(X_n\in B)-\Pr(Y_n\in B)=\Pr(X_n\in B,\ T>n)-\Pr(Y_n\in B,\ T>n) $$
で、右辺の絶対値は $\Pr(T>n)$ 以下である。$T< \infty$ が確率 $1$ なので $\Pr(T>n)\to0$ である。$B=\{j\}$ とすれば $p^{(n)}_{ij}\to\pi_j$ を得る。$\pi'$ が別の定常分布なら、$\pi'_j=\sum_i\pi'_ip^{(n)}_{ij}$ で $n\to\infty$ とすると、優収束定理により $\pi'_j=\pi_j$ である。$\square$

この証明は Dur19 Theorem 5.6.6(pp. 313–314)と同じ筋で、そこで引かれている再帰性の定理の代わりに lem-cp-hit を証明した。$S$ が有限なら、組の連鎖はどこから出発しても $N$ 歩以内に確率 $\delta>0$ 以上で対角に入るような $N,\delta$ がとれるので、Markov 性を $N$ 歩ごとに使って $\Pr(T>kN)\le(1-\delta)^k$ となり、収束は指数的である。独立に走らせるのは最も素朴な選び方で、出会うまでの時間を短くする工夫は 混合時間 の定理「結合による混合時間の上界」で使われる。

例

2 状態の連鎖の独立カップリング

$S=\{0,1\}$、$p_{01}=a$、$p_{10}=b$($0< a,b\le1$、$a+b< 2$)とする。定常分布は $\pi=(\frac b{a+b},\frac a{a+b})$ で、厳密に $\sup_A\lvert p^{(n)}_0(A)-\pi(A)\rvert=\frac a{a+b}\lvert1-a-b\rvert^n$ である。$X_0=0$ とし、$Y_0\sim\pi$ を独立にとる。$Y_0=0$ なら $T=0$ である。$X_m\ne Y_m$ のとき、次の 1 歩で 2 つが一致しない確率は、どちらの並びでも $\rho:=(1-a)(1-b)+ab$ である。よって $\Pr(T>n)=\frac a{a+b}\rho^n$ である。$a=0.3$、$b=0.2$、$n=10$ では、厳密な距離は $0.6\cdot0.5^{10}\approx5.86\times10^{-4}$、カップリングの上界は $0.6\cdot0.62^{10}\approx5.04\times10^{-3}$ である。

途中の計算を開く

$P$ の固有値は $1$ と $1-a-b$ で、$p^{(n)}_{00}-\pi_0=\frac a{a+b}(1-a-b)^n$ である。2 状態では $\sup_A$ は $A=\{0\}$ でとれる。$X_m=0,\ Y_m=1$ から一致するのは、ともに $0$ へ行く確率 $(1-a)b$ か、ともに $1$ へ行く確率 $a(1-b)$ で、一致しないのは $1-(1-a)b-a(1-b)=\rho$ である。$X_m=1,\ Y_m=0$ でも同じ値になる。$\rho-\lvert1-a-b\rvert$ は、$a+b\le1$ なら $2ab$、$a+b>1$ なら $2(1-a)(1-b)$ で、どちらも $0$ 以上である。したがって独立カップリングの上界は正しい速さより遅い。$a=b=\frac12$ では厳密な距離は $1$ 歩で $0$ になるが、$\rho=\frac12$ である。

カップリングが使われる場面

場面カップリング得られること記事
Poisson 近似各 Bernoulli 変数を平均の等しい Poisson 変数と結ぶLe Cam の不等式Poisson分布
ランダムグラフの単調性$G(n,p)$ に独立なランダムグラフを重ねて $G(n,r)$($r\ge p$)を作る単調増加な性質の確率は $p$ について単調Erdős–Rényiのランダムグラフ
交換可能列戻さない抽出と戻す抽出を同じ番号で作るde Finetti の定理の有限版の誤差評価de Finettiの定理
Markov 連鎖の混合同じ乱数で 2 つの連鎖を動かし、出会ったら一緒に動かす混合時間の上界混合時間
収束定理2 つの連鎖を独立に走らせるthm-cp-convergenceこの記事

使える条件と反例

各行は thm-cp-convergence か thm-cp-order の仮定を 1 つだけ外す。

外す条件反例成り立たなくなること
非周期性$S=\{0,1\}$、$p_{01}=p_{10}=1$、$\pi=(\frac12,\frac12)$$p^{(n)}_{00}$ は $1,0,1,0,\dots$ と振動し収束しない。$(0,1)$ から出発した独立な 2 つの連鎖は入れ替わり続けて出会わない
既約性$S=\{0,1\}$、$p_{00}=p_{11}=1$、$\pi=(\frac12,\frac12)$非周期で $\pi$ は定常分布だが、$p^{(n)}_{00}=1$ で $\pi_0=\frac12$ に収束しない
定常分布の存在$S=\mathbb Z$、確率 $\frac12$ で留まり $\frac14$ ずつ $\pm1$ に動く連鎖既約で非周期だが、どの有限集合 $A$ でも $p^{(n)}_0(A)\to0$ で、$p^{(n)}_{0\cdot}$ は確率分布に収束しない
全ての $t$ での裾の比較(確率順序)$\mu=\delta_0$、$\nu=\frac12(\delta_{-1}+\delta_3)$平均は $0\le1$ だが $\nu((-1,\infty))=\frac12< 1=\mu((-1,\infty))$ で、$X\le Y$ となるカップリングはない
反例の確かめ
確かめを開く

1 行目:$P^2=I$ なので $p^{(n)}_{00}$ は $n$ の偶奇で $1$ と $0$ になる。$(X_0,Y_0)=(0,1)$ なら $(X_n,Y_n)$ は $(0,1)$ と $(1,0)$ を交互にとる。2 行目:$\pi P=\pi$ は明らか。3 行目:位置は独立な歩みの和で、各歩みは平均 $0$、分散 $\frac12$ なので、中心極限定理 により $X_n/\sqrt n$ は $N(0,\frac12)$ に分布収束する。有限集合 $A\subset[-K,K]$ なら、任意の $\varepsilon>0$ について十分大きい $n$ で $\Pr_0(X_n\in A)\le\Pr_0(\lvert X_n\rvert/\sqrt n\le\varepsilon)$ で、右辺は $\Pr(\lvert N(0,\frac12)\rvert\le\varepsilon)$ に近づき、$\varepsilon\to0$ で $0$ に近づく。定常分布 $\pi$ があれば $\pi(A)=\sum_i\pi_ip^{(n)}_i(A)\to0$($p^{(n)}_i(A)=p^{(n)}_0(A-i)$ なので各 $i$ で $0$ に近づき、優収束定理による)となり、$A$ が任意の有限集合なので $\pi=0$ となって矛盾する。4 行目:$X=0$ なら $X\le Y$ には $Y\ge0$ が確率 $1$ で要るが、$\nu(\{-1\})=\frac12$ である。

よくある誤り

誤り正しくはなぜ
カップリングとは 2 つの確率変数を独立にとることだと思う周辺分布さえ正しければ同時分布は自由に選べる。独立はその 1 つにすぎないdef-cp-coupling
$\Pr(X\ne Y)$ を全変動距離そのものとして使うどのカップリングでも上界にすぎず、等号は最大カップリングで成り立つthm-cp-maximal、ex-cp-binomial
最大カップリングは 1 つに決まると思う$X\ne Y$ となる部分の同時分布は自由に選べ、一般には一意でないprf-cp-maximal の 3
2 つの連鎖を独立に走らせればいつか出会う周期的な連鎖では出会わないことがある反例の表の 1 行目
平均の大小から確率順序を結論する確率順序はすべての $t$ で裾の確率を比べる反例の表の 4 行目

補足

関連する話題

単調な連鎖。 状態に半順序があり、順序を保つカップリングで動かせる連鎖では、最大と最小の状態から出発した 2 つの連鎖が出会えば、途中から出発した連鎖もすべて出会う。このとき 1 組の合流時刻で全体の混合が評価できる(LPW17 §22.1、pp. 305–306)。全変動距離の定義の違い。 文献によっては $\sum_x\lvert\mu(x)-\nu(x)\rvert$ を全変動距離と呼び、この記事の値の 2 倍になる。最大カップリングの離散版。 状態が有限個の場合の構成と $\Vert\mu-\nu\Vert_{\mathrm{TV}}=\min\Pr(X\ne Y)$ は LPW17 Proposition 4.7・Remark 4.8(p. 50)にある。

関連項目

参考文献

[1]
David A. Levin, Yuval Peres (with contributions by Elizabeth L. Wilmer), Markov Chains and Mixing Times, American Mathematical Society, 2017, Proposition 4.7・Remark 4.8(p. 50)、§22.1(pp. 305–306)、Lemma 22.5・Theorem 22.6(p. 307)、§22.8(p. 320)、§22.10(p. 322)

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