View source for Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

==カップリング==

状態空間 ''S'' 上のマルコフ連鎖 <math>X_t</math>, <math>Y_t</math> がカップリング (coupling) するとは、時刻 ''t'' 以降に二つの確率過程が同じ状態を取ること、つまり <math> X_n = Y_n (n \geq t) </math> をいう。この時刻 ''t'' をカップリング時間という。

ただひとつの定常分布を持つ規約でエルゴード的なマルコフ連鎖の場合、任意の初期分布と定数 <math>\epsilon</math> に対して、ある数 ''T'' が存在し、 ''T'' ステップ後に定常分布との間の変動距離を <math>\epsilon</math> 以下にすることができる。

定常分布を表す <math>Y_n</math> と、任意の状態集合 <math>A \subset S</math> において

<math>
\begin{align}
\mbox{Pr}(X_T \in A) &\geq \mbox{Pr}((X_T = Y_T) \cap (Y_T \in A)) \\
&= 1 - \mbox{Pr}((X_T \not= Y_T) \cup (Y_T \not\in A)) \\
&\geq (1 - \mbox{Pr}(Y_T \not\in A)) - \mbox{Pr}(X_T \not= Y_T) \\
&\geq (1 - \mbox{Pr}(Y_T \not\in A)) - \epsilon \\
&= \pi(A) - \epsilon
\end{align}
</math>

同じ議論を補集合 ''S-A'' に適用すると <math>\mbox{Pr}(X_T \not\in A) \geq \pi(S-A) - \epsilon</math>。
すなわち <math> \mbox{Pr}(X_T \in A) \leq \pi(A) + \epsilon </math> であるため、時刻 ''T'' 以降に定常分布へ収束することがわかる。

===具体例===

;トランプのシャッフル
二組のトランプを用意し、一組目 <math>X_t</math> は52枚のカードから等確率で一枚選び、一番上におく。
もう一組 <math> Y_t </math> のほうは、''X'' で選んだ値を同様に一番上におく。

選ばれて一度上に移動したカードの位置は、 ''X'' と ''Y'' の間で変わらない。
そのため、全てのカードが少なくとも一度選ばれた時点でカップリングが起こり、その後の動作が全て同一になる。
全てのカードが少なくとも1回選ばれるのに必要な回数の期待値は <math>n \log n + cn</math> と書ける (''c''は定数)。
いずれか一枚のカードがまだ選ばれていない確率は

<math>
(1 - 1/n)^{n \log n + cn} \leq e^{-(\log n + c)} = \frac{e^{-c}}{n}
</math>

したがって ''n'' 枚のうちどれかが一つでも選ばれていない確率は高々 <math>e^{-c}</math>。
例えば、<math> n \log n + n \log (1/\epsilon) = n \log (n/\epsilon)</math> 回シャッフルした後は、カップリングしていない確率は高々 <math>\epsilon</math> になる。