Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

Revision as of 10:16, 1 July 2010

分布間の距離

二つの確率分布 $D_1$ と $D_2$ の距離を次のように定義する。

変動距離: $\textstyle ||D_1 - D_2|| = \frac{1}{2} \sum_{x \in S} | D_1(x) - D_2(x) |$

右辺の係数 1/2 は $0 \leq ||D_1 - D_2|| \leq 1$ を満たすためについており、 $||D_1 - D_2|| = 0$ なら全要素について分布が等しいから $D_1 = D_2$ である。また距離が 1 のときは確率が正となる状態の集合が独立であることを意味している。

変動距離は、特定の事象に対する確率の差を用いても定義できる。任意の $A \subset S$ において $\textstyle D_i(A) = \sum_{x \in A} D_i (x)$ とする。このとき

$||D_1 - D_2|| = \max_{A \subset S} | D_1(A) - D_2(A) |$

証明

$D_1(x) \geq D_2(x)$ を満たす状態の集合を $S^+ \subset S$ 、 $D_1(x) < D_2(x)$ を満たす状態の集合を $S^- \subset S$ と書く。このとき

$\begin{align} \max_{A \subset S} D_1(A) - D_2(A) &= D_1(S^+) - D_2(S^+)\\ \max_{A \subset S} D_2(A) - D_1(A) &= D_1(S^-) - D_2(S^-)\\ \end{align}$

また

$D_1(S^+) + D_1(S^-) = D_2(S^+) + D_2(S^-) = 1$

より

$D_1(S^+) - D_2(S^+) = D_2(S^-) - D_1(S^-)$

したがって

$\max_{A \subset S} | D_1(A) - D_2(A) | = | D_1(S^+) - D_2(S^+) | = | D_2(S^-) - D_1(S^-) |$

最後に

$\textstyle ||D_1 - D_2|| = \frac{1}{2}\sum_{x \in S} | D_1(x) - D_2(x) | = \frac{1}{2}( | D_1(S^+) - D_2(S^+) | + | D_2(S^-) - D_1(S^-) | ) = \max_{A \subset S} | D_1(A) - D_2(A) |$ (証明おわり)

カップリング

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

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

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

$\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}$

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

具体例

トランプのシャッフル

二組のトランプを用意し、一組目 $X_t$ は52枚のカードから等確率で一枚選び、一番上におく。もう一組 $Y_t$ のほうは、X で選んだ値を同様に一番上におく。

選ばれて一度上に移動したカードの位置は、 X と Y の間で変わらない。そのため、カップリングするためには、全てのカードが少なくとも一度選ばれればよい。これに必要な回数は $n \log n + cn$ である。いずれか一枚のカードがまだ選ばれない確率は

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

したがって n 毎のうちどれかが選ばれていない確率は高々 $e^{-c}$ 。例えば、 $n \log n + n \log (1/\epsilon) = n \log (n/\epsilon)$ ステップたてば、カップリングしていない確率は高々 $\epsilon$ になる。

@@ Line 75: / Line 75: @@
 同じ議論を補集合 ''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'' の間で変わらない。
+そのため、カップリングするためには、全てのカードが少なくとも一度選ばれればよい。
+これに必要な回数は <math>n \log n + cn</math> である。
+いずれか一枚のカードがまだ選ばれない確率は
+<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> になる。

Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

Revision as of 10:16, 1 July 2010

分布間の距離

カップリング

具体例

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox