GhaSShee


Rand Algo


数学ガール「乱択アルゴリズム」 I read "Mathematic Girl-Randomized Algorithm" by Hiroshi Yuki,
reconstructed the contents with some optimizations and supplement.

# Probability Space ## Definition of Pribability Space - $ \Phi $ : 母集団（標本集合） - $ {\cal X} $ : 確率変数 - $ {\cal X(\Phi)} $ : $ \Phi \rightarrow R _ + $ - $ {\cal Pr} $ : $ \Phi \rightarrow R_+ $ - $ Pr( \Phi ) = 1 $ - $ Pr(A)+Pr(B) = Pr(A + B) $ given by $ A \cup B = \phi $

## コインをn回投げ、表が出た回数の期待値はいくらか？ How many times will you see the head of coin in throwing the coin n times? Solution. - $ Pr(表) := p $ - $ Pr(裏) := q $ $ \quad \quad $ where $ \quad p + q = 1 $ - $ {\cal X}(表) := 1 $ - $ {\cal X}(裏) := 0 $ $ \quad \quad $ where $ \quad \Phi = $ { $ 表 , 裏 $ } k回目における確率変数は - $ {\cal X _ k} (表) = 1 $ - $ E( \cal X _ k ) = p $ 表が出た回数は - $ {\cal X} = \sum _ {k=1} ^n \cal{X} _ k $ 表が出た回数の期待値は、 $$ E({\cal X}) = E( \sum _ { k=1 } ^ n {\cal{X}} _ k ) = \sum _ {k=1} ^ n E( {\cal X _ k} ) = np $$

# サイコロの確率空間 Probability Space of Dice * $ {\cal X} $ : 確率変数　{1,2,3,4,5,6} * $ \Phi $ : 母集団　{ ⚀ , ⚁ , ⚂ , ⚃ , ⚄ , ⚅ } * $ {\cal Pr} $ : $ \Phi \rightarrow R _ + $　{ $ \frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6} $ }

# サイコロの目が全て出るまでにかかる回数の期待値はいくらか？ How many times will you throw a dice until all pips on the dice is out ? Solution. - コインの問題に帰着させる - 新しい目がでると階段を一段上る、とする - $ k $ 段目で新しい目がでるのにかかる回数を $ a _ k $ とすると答えは　$ a = \sum _ {k=1} ^6 {a _ k} $ - $ k $ 段目で新しい目がでる(表)　　$ \cal{X} _ {ki} = 1 $ 　とする 　$ Pr (\cal{X} _ {ki} = 1) = \frac{6-k}{6} $ - $ k $ 段目で新しい目が出ない(裏)　$ \cal{X} _ {ki} = 0 $ 　とする 　$ Pr (\cal{X} _ {ki} = 0) = \frac{k}{6} $
インディケータ確率変数 $ \cal{X} _ {ki} $ - ある事象が起きる　$ \rightarrow 1 $ - 　　　　起きない　$ \rightarrow 0 $
インディケータ変数の期待値は、 $$ E( {\cal {X} _ {ki}}) = Pr ( {\cal X _ {ki}}) $$
k段目で表が出た回数は、 $ a _ k $ 回目の一回だけ表なので、 - $ \sum _ {k=1} ^ {a _ k} \cal X _ {ki}　= 1 $ その期待値も　1　となるので、 $$ E( \sum _ {k=1} ^ {a _ k} {\cal{X} _ {ki} } ) = \sum _ {k=1} ^ {a _ k} E( {\cal X _ {ki}} ) = a _ k \frac{6-k}{6} = 1 $$ $$ a _ k = \frac{6}{6-k} $$ Answer. $$ a = \sum _ {k=1} ^6 {a _ k} = 14.7 $$

# 問題提起　 強正美優問題 |-|強|正|美|優|意味|記号| |:---|---:|---:|---:|---:|---|:---:|:---:| |P1|1|1|1|-|強いか正しいか美しいか| $ x_1 \lor x_2 \lor x_3 $ | |P2|-|1|0|1|正しいか美しくないか優しいか| $ x_2 \lor \lnot x_3 \lor x_4 $ | |P3|0|-|1|1|正しくないか美しいか優しいか| $ \lnot x_1 \lor x_3 \lor x_4 $ | |P4|0|1|-|0|...|...| |P5|-|0|1|0|...|...| |P6|0|0|0|-|...|...| |P7|1|-|0|0|...|...| |P8|1|0|-|1|...|...|
Qestion. P1 ~ P8 をどうじにみたすものはあるか？ Solution. 論理図を描いて確かめる ![](/image/sat3.png width="200") Answer. 同時に満たすものはない

# SAT 強正美優問題は 3-SAT である
## Syntax - `literal` $ \equiv $ $ x_1 , x_2 , x_3, \lnot x_1 , \lnot x_2 , \lnot x_3 \in \\{ True, False \\} $ - `clause` $ \equiv $ `lit` $ \lor $ `lit` , `lit` $ \lor $ `cla` - `CNF` $ \equiv $ (`cla`) $ \land $ (`cla`) , (`cla`) $ \land $ (`CNF`) - `CNF` : `Conjunctive Normal form` : `乗法標準型`
## Evaluation - `CNF` -----------> { $ True , False $ }
`CNF` -----------> $ True $ We say in this evaluation `CNF is satisfied`
# SAT2 * Satisfiability Problem * `P問題` である * CNF が充足しているかを判定する問題


# P問題 P : polynomial time NP : non-deterministic polynomial time

# NTM & DTM DTM : Deterministic Turing Machine NTM : Non-Deterministic Turing Machine

# Definition of NTM
$$ M = ( {\cal Q} ,\Sigma , t, \sqcup , A , \delta ) $$ * $ {\cal Q} $ : 状態群の有限集合 * $ \Sigma $ : 記号群の集合 * $ t \in {\cal Q} $ : 初期状態 * $ \sqcup \in {\cal Q} $ : 空状態 * $ A \subset {\cal Q} $ : 受理済みの状態の集合 * $ \delta $ : $ {\cal Q} $ \ $ A \times \Sigma \rightarrow ( {\cal Q} \times \Sigma \times $ { $ L,R $ } $ ) $ * `未受理の状態`と`記号群`の直積　→　`状態`と`記号群`の直積 の右シフトまたは左シフト
これは状態遷移マシン（多変数関数)である。 ~~~ DTMは一変数関数であり、純粋関数型である。 ~~~

# 3 - SAT Problem Question. ~~~ 3 - CNF ------> True となるものはあるか？ ~~~
(`lit` $\lor$ `lit` $\lor$ `lit`) $\land$ ( `lit` $\lor$ `lit` $\lor$ `lit` ) を `3 - CNF` とよぶ

# RANDOM WALK 3 SAT Algorithm
~~~ procedure RANDOM-WALK-3-SAT(f,n,R) r ← 1 while r ≤ R do a ← [n変数の割り当てを乱択する] w ← 1 while w ← 3n if f(a) then return 充足する endif c ← aの中で充足しない clause x ← cの literal からひとつを乱択 a ← x を反転した値 w ← w + 1 end-while r ← r + 1 end-while return おそらく充足しない end-procedure ~~~









　← c = `lit` $\lor$ `lit` $\lor$ `lit`
　　c is `False` $\Rightarrow$ 内部の全てのlitはFalse
　← At least, $\frac{1}{3}$ の確率で誤りを訂正している








プログラムの誤り訂正に、一次元のランダムウォークが隠れている
この誤り度合いを表す数直線上の距離を`ハミング距離`という このアルゴリズムは`片側誤りのモンテカルロアルゴリズム`という


# ハミング距離 3-dimentional (n = 3) 4-dimentional　(n = 4)

# 片側誤りのモンテカルロアルゴリズム Definition ~~~ Proposition --------> {True, おそらくFalse} 一方の出力は100％正しく 他方はある確率で正しい 乱択アルゴリズム ~~~
このアルゴリズムの`見逃し確率`を求める $ 1 $ より大きい整数 $ M $ を用いて、ラウンド $ R $ の成功確率を $ \frac{1}{M^n} $ とおくと、 $$\begin{eqnarray} 見逃し確率 &=& (ラウンドの失敗確率)^R \\\ &=& ( 1 - \frac{1}{M^n})^R \\\ (ここで&R&=K*M^n とおく ) \\\ &=& ( 1 - \frac{1}{M^n})^{K*M^n} \\\ &≤& e^{- \frac{1}{M^n} * K * M ^ n} \\\ &=& e^{-K} \\\ &=& \frac{1}{e^K} \end{eqnarray}$$


# 3-SAT-RANDOM-WALK $ \quad \left( \begin{array}{c} 2i + h \\\ i \end{array} \right) \frac{h}{2i + h} \quad = \quad \left( \begin{array}{c} 2i + h - 1 \\\ i \end{array} \right) \quad - \quad \left( \begin{array}{c} 2i + h - 1 \\\ i - 1 \end{array} \right) $


ハミング距離の初期値が $ h $ のとき、 $ 3n $ 回以内に成功する確率 $ P(h) $ は、 $$\begin{eqnarray} P(h) &=& \sum ^ { \frac{3n-h}{2} } _ {i=0} \left( \begin{array}{c} 2i + h \\ i \end{array} \right) \left( \frac{2}{3} \right) ^ i \left( \frac{1}{3} \right) ^ {h+i} \\ &>& \sum ^ { h } _ {i=0} \left( \begin{array}{c} 2i + h \\ i \end{array} \right) \left( \frac{2}{3} \right) ^ i \left( \frac{1}{3} \right) ^ {h+i} \\ & & \begin{cases} \left(\frac{2}{3}\right) ^ i ≥ \left(\frac{2}{3}\right) ^ h \\ \left(\frac{1}{3}\right) ^ {h+i} ≥ \left(\frac{1}{3}\right) ^ 2h \\ \frac{h}{2i+h} ≥ \frac{1}{3} \\ \sum ^ { h } _ {i=0} \left( \begin{array}{c} 2i + h \\ i \end{array} \right) ≥ \left( \begin{array}{c} 3h \\ h \end{array} \right) \end{cases} \\ &≥& \left(\frac{1}{3}\right) \left(\frac{2}{27}\right) ^ h \left( \begin{array}{c} 3h \\ h \end{array} \right) \\ ここで、スターリングの近似式より& &　C = \frac{1}{3} \frac{\sqrt{3}}{2 \sqrt{\pi}} e ^ { - \frac{1}{8}}\\ &≥& \frac{C}{\sqrt{h}} \left(\frac{1}{2}\right) ^ h \end{eqnarray}$$

$$\begin{eqnarray} ラウンドの成功確率\frac{1}{M^n} &=& \sum ^n _ {h=0} (初期値がhになる確率) P(h) \\\ &≥& \sum ^n _ {h=0} \left(\frac{1}{2}\right) ^ n \left( \begin{array}{c} n \\ h \end{array} \right) \frac{C}{\sqrt{h}} \left(\frac{1}{2}\right) ^ h \\ &≥& \frac{C}{\sqrt{n}} \frac{1}{2^n} \sum ^n _ {h=0} \left( \begin{array}{c} n \\ h \end{array} \right) \left(\frac{1}{2}\right) ^ h \left( 1 \right) ^ {n-h} \\ &=& \frac{C}{\sqrt{n}} \frac{1}{2^n} \left(\frac{1}{2} + 1 \right) ^ n\\ &=& \frac{C}{\sqrt{n}} \left( \frac{3}{4} \right) ^ n \end{eqnarray}$$

$$ \begin{eqnarray} 成功確率の逆数　M ^ n ≤ \frac{\sqrt{n}}{C} \left( \frac{4}{3} \right) ^ n \\ \\ 1に持っていくことで成功する値であり、\\ 上から押さえてやる必要がある。\\ 上から抑えられれば、ラウンド数で割ることができ、\\ 成功確率の期待値を1以上にすることができる。\\ つまり、この逆数がたかだかいくらである必要がある。\\ \\ たかだか、\left(\frac{4}{3}\right) ^n ≤ (1.334) ^n である \end{eqnarray} $$


# Quick Sort
`INPUT` 数列 : $ A = A[1],A[2],A[3],...,A[n] $ ソート範囲 : $ L , R $
`OUTPUT` sorted ($ A = A[L],A[L+1],...,A[R] $)
~~~ procedure QUICKSORT (A,L,R) if L < R then p ← L k ← L + 1 while k ≤ R do if A[L] > A[k] then A[p+1] ↔ A[k] p ← p + 1 endif k ← k + 1 end-while A[L] ↔ A[p] A ← QUICKSORT (A,L,p-1) A ← QUICKSORT (A,p,R) end-if return A end-procedure ~~~
~~~ 1 1 1 R-L R-L R-L/2 R-L/2 R-L R-L 1 X' X' 1 1 . ~~~

$ N = R-L = 2^c * 2^n $とおくと $$\begin{eqnarray} X _ k &=& 6+5\frac{R-L}{2^{k-1}} + 2X _ {k+1} \\\ X &=& 6(1+2+..+2^n) + 5(R-L)n\\\ &=& 6(2^n - 1) + 5(R-L)n\\\ &=& 6(\frac{N}{2^c} - 1) + 5N(\log _ 2 N - c) \\\ &=& C _ 1 N + C _ 2 N \log N \end{eqnarray}$$ At most $ N\log N $ 's order


おわり