Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology | Markov Chains(Difference between revisions)
Jump to: navigation, search
m
Line 1: Line 1:
−
==分布間の距離==
+
==確率分布の距離==
  
 
二つの確率分布 <math>D_1</math> と <math>D_2</math> の距離を次のように定義する。
 
二つの確率分布 <math>D_1</math> と <math>D_2</math> の距離を次のように定義する。
  
−
変動距離: <math>\textstyle
+
; [定義] 変動距離 <math>\textstyle
 
||D_1 - D_2|| = \frac{1}{2} \sum_{x \in S} | D_1(x) - D_2(x) |
 
||D_1 - D_2|| = \frac{1}{2} \sum_{x \in S} | D_1(x) - D_2(x) |
 
</math>
 
</math>
  
−
右辺の係数 1/2 は <math> 0 \leq ||D_1 - D_2|| \leq 1</math> を満たすためについており、<math>||D_1 - D_2|| = 0</math> なら全要素について分布が等しいから <math>D_1 = D_2</math> である。また距離が 1 のときは確率が正となる状態の集合が独立であることを意味している。
+
右辺の係数 1/2 は <math> 0 <= ||D_1 - D_2|| <= 1</math> を満たすためについており、<math>||D_1 - D_2|| = 0</math> なら全要素について分布が等しいから <math>D_1 = D_2</math> である。また距離が 1 のときは確率が正となる状態の集合が独立であることを意味している。
−
 
+
 
変動距離は、特定の事象に対する確率の差を用いても定義できる。
 
変動距離は、特定の事象に対する確率の差を用いても定義できる。
 +
 +
; 定理
 
任意の <math>A \subset S</math> において <math>\textstyle D_i(A) = \sum_{x \in A} D_i (x)</math> とする。このとき
 
任意の <math>A \subset S</math> において <math>\textstyle D_i(A) = \sum_{x \in A} D_i (x)</math> とする。このとき
  
Line 50: Line 51:
  
 
<math>\textstyle
 
<math>\textstyle
−
||D_1 - D_2|| = \frac{1}{2}\sum_{x \in S} | D_1(x) - D_2(x) |
+
\begin{align}
−
= \frac{1}{2}( | D_1(S^+) - D_2(S^+) | + | D_2(S^-) - D_1(S^-) | )
+
||D_1 - D_2|| &= \frac{1}{2}\sum_{x \in S} | D_1(x) - D_2(x) | \\
−
= \max_{A \subset S} | D_1(A) - D_2(A) |
+
&= \frac{1}{2}( | D_1(S^+) - D_2(S^+) | + | D_2(S^-) - D_1(S^-) | ) \\
−
</math>(証明おわり)
+
&= \max_{A \subset S} | D_1(A) - D_2(A) |
 +
\end{align}
 +
</math>
  
 
==カップリング==
 
==カップリング==
Line 59: Line 62:
 
状態空間 ''S'' 上のマルコフ連鎖 <math>X_t</math>, <math>Y_t</math> がカップリング (coupling) するとは、時刻 ''t'' 以降に二つの確率過程が同じ状態を取ること、つまり <math> X_n = Y_n (n \geq t) </math> をいう。この時刻 ''t'' をカップリング時間という。
 
状態空間 ''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>\epsilon</math> に対して、ある数 ''T'' が存在し、 ''T'' ステップ後に定常分布との間の変動距離を <math>\epsilon</math> 以下にすることができる。
  
 
定常分布を表す <math>Y_n</math> と、任意の状態集合 <math>A \subset S</math> において
 
定常分布を表す <math>Y_n</math> と、任意の状態集合 <math>A \subset S</math> において
Line 83: Line 86:
  
 
選ばれて一度上に移動したカードの位置は、 ''X'' と ''Y'' の間で変わらない。
 
選ばれて一度上に移動したカードの位置は、 ''X'' と ''Y'' の間で変わらない。
−
そのため、カップリングするためには、全てのカードが少なくとも一度選ばれればよい。
+
そのため、全てのカードが少なくとも一度選ばれた時点でカップリングが起こり、その後の動作が全て同一になる。
−
これに必要な回数は <math>n \log n + cn</math> である。
+
全てのカードが少なくとも1回選ばれるのに必要な回数の期待値は <math>n \log n + cn</math> と書ける (''c''は定数)。
−
いずれか一枚のカードがまだ選ばれない確率は
+
いずれか一枚のカードがまだ選ばれていない確率は
  
 
<math>
 
<math>
Line 91: Line 94:
 
</math>
 
</math>
  
−
したがって ''n'' 毎のうちどれかが選ばれていない確率は高々 <math>e^{-c}</math>。
+
したがって ''n'' 枚のうちどれかが一つでも選ばれていない確率は高々 <math>e^{-c}</math>。
−
例えば、<math> n \log n + n \log (1/\epsilon) = n \log (n/\epsilon)</math> ステップたてば、カップリングしていない確率は高々 <math>\epsilon</math> になる。
+
例えば、<math> n \log n + n \log (1/\epsilon) = n \log (n/\epsilon)</math> 回シャッフルした後は、カップリングしていない確率は高々 <math>\epsilon</math> になる。

Revision as of 15:43, 7 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 <= ||D_1 - D_2|| <= 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 \begin{align} ||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) | \end{align}

カップリング

状態空間 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 の間で変わらない。 そのため、全てのカードが少なくとも一度選ばれた時点でカップリングが起こり、その後の動作が全て同一になる。 全てのカードが少なくとも1回選ばれるのに必要な回数の期待値は n \log n + cn と書ける (cは定数)。 いずれか一枚のカードがまだ選ばれていない確率は

(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 になる。

Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Markov_Chains/Coupling&oldid=255132"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox