『確率と計算』 第7章 Marcov Chains & Random Walks
7.1 Marcov Chains: Definitions and Representations
定義 7.1 discrete time stochastic process $X_0,X_1,…$ が以下のとき、 マルコフ連鎖という。
\[ \mathrm{Pr}(X_t=a_t|X_{t-1}=a_{t-1},X_{t-2}=a_{t-2},X_0=a_0) = \mathrm{Pr}(X_t=a_t|X_{t-1}=a_{t-1}) = P_{a_{t-1},a_t} \]
ただし、$X_t$ が $X_0,…,X_{t-2}$ と必ずしも独立しているというわけではない。
ちょうど $m$ ステップで状態$i$から$j$に遷移確率する確率
\[ P^m_{i,j} = \mathrm{Pr}(X_{t+m}=j|X_t=i) \]
とあらわす。また、過程が時間 $t$ で状態 $i$ にある確率を $p_i(t)$ であらわすと
\[ p_i(t) = \sum_{j\ge0} p_j(t-1)P_{j,i} \]
例題 2-SATを解く乱択アルゴリズム
- $x_1 \cup x_2$ のように2つの論理変数を連言をclause
- 複数のclauseを選言でつなぎあわせたものを2-SAT
といい、論理変数について2-SATの論理式をtrueになるように各論理変数に真理値を割り当てたい。 単純にかんがえると $N$変数あれば$2^N$通りのパターンがあり、それをしらべていけばいい。
でも、Kromのアルゴリズムをつかえば、乱択アルゴリズムでなくても多項式時間で解くことができる。 see wikipedia 2-satisfiability
例題 3-SAT
この場合だと2-SATのような乱択アルゴリズムでも指数時間かかってしまうので、 アルゴリズムを修正する。
7.2 Classification of states
- accessible/communicate
- communicating classes
- irreducible
- recurrent or transient
- positive/null recurrent
\[ r^{t}_{i,j}=\mathrm{Pr}(X_t=j \cap \forall s 1 \le s \le t-1, X_s \ne j|X_0=i) \]
$r^{t}_{i,j}$ は状態 $i$ から開始して、時間 $t$ で状態 $j$ に初めて到達する確率
到達する時間の期待値 $h_{i,j}$
\[ h_{i,j}=\sum_{t \ge 1}{t \cdot r^{t}_{i,j}} \]
7.3 Stationary Distributions
「ある程度自由にうろうろする」マルコフ連鎖は、いずれどこの状態にとどまるかの確率分布が1つに定まる。
定理
finite, irreducible, ergodic なマルコフ連鎖は以下の性質をもつ:
- 1つの定常分布をもつ
- すべての $j,i$ について $\lim_{t \to \infty}P^t_{j,i}$ が存在し、$j$とは独立である。
- $\pi_i = \lim_{t \to \infty}P^t_{j,i} = \frac{1}{h_{i,i}}$
ここで $P^t_{j,i}$ は状態 $j$ から $i$ へ、時間$t$で到達する確率、 $h_{i,i}$は状態 $i$ から自分自身に戻る平均時間。
補題
再生理論からの定理。
finite, irreducible, ergodic なマルコフ連鎖で、 すべての $i$ について $\lim_{t \to \infty}P^t_{i,i}$ が存在し、
\[ \lim_{t \to \infty}P^t_{i,i} = \frac{1}{h_{i,i}} \]
定理
finite, irreducible, aperiodicなマルコフ連鎖において、 $S$を状態の集合としたとき、$S$から出ていく確率と$S$へ入る確率は等しい。
定理: 最終的に finite じゃなくてもよくなる
irreducible で aperiodicなマルコフ連鎖はいずれかのカテゴリーに属する
- そのマルコフ連鎖はergodicである
- positive recurrentな状態がない
例. 待ち行列
待ち行列の人数を$X_t$とするとマルコフ連鎖となる。 並ぶ人が増える確率 $\lambda$ 、列から1人抜ける $\mu$ とする
7.4 Random Walks on Undirected Graphs
定義
無向グラフでのランダムウォークについて $G=(V,E)$
- $d(i)$ 頂点$i$から出ている辺の数
- 頂点$i$から$j$に出ていく確率は $\frac{1}{d(i)}$
補題
無向グラフ$G$でのランダムウォークがaperiodicであるのは $G$がbipartiteでないときのみ
定理
無向グラフ$G=(V,E)$でのランダムウォークは $\bar\pi$ に収束し、
\[ \pi_v = \frac{d(v)}{2|E|} \]
hitting/commute/cover time
- $h_{u,v}$ $u$から$v$まで到達する平均時間 … hitting time
- commute time: $h_{u,v} + h_{v,u}$
- cover time: $v$ から出発してすべての頂点を巡るために必要な時間の期待値
see On the Cover Time of Random Walks on Graphs 1988 Jeff D. Khan,
ここからグラフ$G$におけるcover timeについての下限を求める
例. s-t connectivity
グラフ$G=(V,E)$の頂点$s$から$t$への経路を求める問題. 頂点の数を$n$, 辺の数を$m$とする
決定的なアルゴリズムだと $\Omega{n}$ の記憶空間が必要だが、 確率的なアルゴリズムだと $O(\log{n})$ の記憶空間で済む
- $s$からランダムウォークを始める
- $2n^3$ ステップ以内に$t$に到着しなければ、経路はないと判断する
7.5 Parrondo’s paradox
２つの負けるゲームを組み合わせて、1つの有利なゲームを作ることができる。
- ゲームA: $p_a < \frac{1}{2}$ で表が出るコインを1回投げて、表が出たら1ドル獲得。裏なら1ドル没収。
- ゲームB: 2枚のコインを使う。獲得した賞金が3で割り切れるなら、 確率 $p_b$ で表が出るコインを1回投げて、表なら1ドル獲得。裏なら1ドル没収。 3で割り切れない場合は、確率 $p_c$ で表が出るコインを1回投げて、表なら1ドル獲得。裏なら1ドル没収。
この2つのゲームを組み合わせて、ゲームCをつくる。 (ゲームBがまけるゲームだということは直感的にはわかりづらいが…)
- ゲームC: 公平なコインを1回投げて、表ならゲームA、裏ならゲームBを行うということを繰り返す
ゲームCは、期待値から見ると勝てるゲームである。