Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling - Revision history

Adm at 06:44, 7 July 2010

2010-07-07T06:44:30Z

Adm at 06:43, 7 July 2010

2010-07-07T06:43:14Z

Adm: Aritalab:Lecture/NetworkBiology/Markov Chain/Coupling moved to Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

2010-07-07T06:05:05Z

Aritalab:Lecture/NetworkBiology/Markov Chain/Coupling moved to Aritalab:Lecture/NetworkBiology/Markov Chains/Coupling

Adm: Aritalab:Lecture/NetworkBiology/Coupling moved to Aritalab:Lecture/NetworkBiology/Markov Chain/Coupling

2010-07-07T06:04:24Z

Aritalab:Lecture/NetworkBiology/Coupling moved to Aritalab:Lecture/NetworkBiology/Markov Chain/Coupling

Adm at 01:16, 1 July 2010

2010-07-01T01:16:42Z

Adm: /* カップリング */

2010-07-01T00:59:56Z

‎カップリング

Adm: New page: ==分布間の距離== 二つの確率分布 $D_1$ と $D_2$ の距離を次のように定義する。変動距離: $\textstyle ||D_1 - D_2|| = \frac{1}{2} \...$

2010-06-30T20:25:03Z

New page: ==分布間の距離== 二つの確率分布 <math>D_1</math> と <math>D_2</math> の距離を次のように定義する。変動距離: <math>\textstyle ||D_1 - D_2|| = \frac{1}{2} \...

New page

==分布間の距離==

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

変動距離: <math>\textstyle
||D_1 - D_2|| = \frac{1}{2} \sum_{x \in S} | D_1(x) - D_2(x) |
</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 のときは確率が正となる状態の集合が独立であることを意味している。

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

<math>
||D_1 - D_2|| = \max_{A \subset S} | D_1(A) - D_2(A) |
</math>

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

<math>
\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}
</math>

また

<math>
D_1(S^+) + D_1(S^-) = D_2(S^+) + D_2(S^-) = 1
</math>

より

<math>
D_1(S^+) - D_2(S^+) = D_2(S^-) - D_1(S^-)
</math>

したがって

<math>
\max_{A \subset S} | D_1(A) - D_2(A) | =
| D_1(S^+) - D_2(S^+) | = | D_2(S^-) - D_1(S^-) |
</math>

最後に

<math>\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) |
</math>(証明おわり)

==カップリング==

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

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

定常分布を表す <math>Y_t</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'' 以降に定常分布へ収束することがわかる。

← Older revision		Revision as of 06:44, 7 July 2010
Line 1:		Line 1:
		+	{{Lecture/Header}}
		+
	==確率分布の距離==		==確率分布の距離==

@@ Line 1: / Line 1: @@
-==分布間の距離==
+==確率分布の距離==
 二つの確率分布 <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) |
 </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> とする。このとき
@@ Line 50: / Line 51: @@
 <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) |
 ==カップリング==
@@ 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'' をカップリング時間という。
-規約でエルゴード的なマルコフ連鎖は、任意の初期分布と定数 <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> において
@@ Line 83: / Line 86: @@
 選ばれて一度上に移動したカードの位置は、 ''X'' と ''Y'' の間で変わらない。
-そのため、カップリングするためには、全てのカードが少なくとも一度選ばれればよい。
+そのため、全てのカードが少なくとも一度選ばれた時点でカップリングが起こり、その後の動作が全て同一になる。
-これに必要な回数は <math>n \log n + cn</math> である。
+全てのカードが少なくとも1回選ばれるのに必要な回数の期待値は <math>n \log n + cn</math> と書ける (''c''は定数)。
-いずれか一枚のカードがまだ選ばれない確率は
+いずれか一枚のカードがまだ選ばれていない確率は
 <math>
@@ Line 91: / Line 94: @@
 </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> になる。

← Older revision		Revision as of 01:16, 1 July 2010
Line 75:		Line 75:
	同じ議論を補集合 ''S-A'' に適用すると <math>\mbox{Pr}(X_T \not\in A) \geq \pi(S-A) - \epsilon</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> \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> になる。