. . . . . . .. . . .
Lecture 11: PSRGs via Random Walks on Graphs
照山順一
国立情報学研究所
October 22, 2013
. . . .
どんなことすんの？
擬似乱数生成のお話
expander graph上のランダムウォークの利用[IZ89]：乱択アルゴリズ ムの確率増幅に使える
おおざっぱな解析をします．（厳密に解析すればよりよい擬似乱数の
保証ができる）
. . . .
Expander Graphs
Expander Graph (詳しくは次回以降) : 定数次数と定数のconductance 定式化のためには頂点数の増加に関してグラフの列を議論する必要が ある．
expander family : ∃(d, ϕ), s.t. 次数d, conductance が少なくともϕ, を満
たすグラフの列
(＊ランダムd-正則グラフは高い確率でexpanderとなる)
今回はexpanderのスペクトラルの性質を用いる．以下のようなexpander
のグラフ族を考える．
|λi− d| < ϵd ∀i ≥ 2 for constant ϵ
|µi| < ϵd ∀i ≥ 2 for constant ϵ
上のようなグラフの生成法は知られている．
. . . .
なんで擬似乱数？
擬似乱数生成器： 入力[シード：結構ランダムな短い列] ⇒ 出力[ほどほどにランダムな長い列] ..
. 1 ランダムビットは乏しい．ランダム性の維持にはそんなに多くは作 れない？しかし，乱択アルゴリズムの多くは乱数列をたくさん必要 とする． ..
. 2 デバッグ等でアルゴリズムを再度走らせるとき，同じシードによる 同じ乱数列を用いることができる：真の乱数では再現性はない．. . . .
応用
乱択アルゴリズムの複数試行による成功率増幅 (1回でrビットの乱数) 毎回同じだけのランダム列が必要そう(r× t, t:試行回数) → 新しいランダム列はそんなにいらない(示すこと：r + 9tくらい) t回生成すれば失敗確率はtに関して指数的に減少することを示す. . . .
応用
乱択アルゴリズムの複数試行による成功率増幅 (1回でrビットの乱数) 毎回同じだけのランダム列が必要そう(r× t, t:試行回数) → 新しいランダム列はそんなにいらない(示すこと：r + 9tくらい) t回生成すれば失敗確率はtに関して指数的に減少することを示す. . . .
応用
乱択アルゴリズムの複数試行による成功率増幅 (1回でrビットの乱数) 毎回同じだけのランダム列が必要そう(r× t, t:試行回数) → 新しいランダム列はそんなにいらない(示すこと：r + 9tくらい) t回生成すれば失敗確率はtに関して指数的に減少することを示す. . . .
Random Walk Generator
r : アルゴリズムの一回試行に必要なビット数 乱数の空間={0, 1}r アルゴリズムへの入力を一つに固定 X⊂ {0, 1}r : アルゴリズムが間違った答えを出力する乱数の集合 Y ⊂ {0, 1}r : アルゴリズムが正しい答えを出力する乱数の集合 V ={0, 1}rとしたexpander graph 上のランダムウォーク =乱数生成に対応 expander graph : d-正則 A : 隣接行列，d = µ1> µ2 ≥ · · · ≥ µn : 固有値 作りたいグラフの性質 |µi| d ≤ 1/10 for all i ≥ 2?. 構成方法は次回．
. . . .
Random Walk Generator
d = 400に設定． rビットの真の乱数を持つ：これをグラフに使ってみよう 初期値：グラフのスタート地点． ランダムに隣接点を選択．log2400∼ 9なので9ビットあれば十分． 注意点：グラフの簡潔な記述を必要とする． 頂点数が2rなのでかなり大きなグラフ．隣接行列ではグラフ全体を 保持することはできないかも． 代わりに頂点vと整数iからvのi番目の隣接点をすぐに出力する機 構を必要とする． {0, 1}r上のハイパーキューブを考える：d = rであり，i番目の隣接 点はiビット目をフリップしたものとする．
どうやらこんな感じのをできるらしい：I promise you that ...
. . . .
Random Walk Generator
d = 400に設定． rビットの真の乱数を持つ：これをグラフに使ってみよう 初期値：グラフのスタート地点． ランダムに隣接点を選択．log2400∼ 9なので9ビットあれば十分． 注意点：グラフの簡潔な記述を必要とする． 頂点数が2rなのでかなり大きなグラフ．隣接行列ではグラフ全体を 保持することはできないかも． 代わりに頂点vと整数iからvのi番目の隣接点をすぐに出力する機 構を必要とする． {0, 1}r上のハイパーキューブを考える：d = rであり，i番目の隣接 点はiビット目をフリップしたものとする．
どうやらこんな感じのをできるらしい：I promise you that ...
. . . .
Formalizing[
定式化
]
乱択アルゴリズムをt + 1回走らせたい 初期設定として真にランダムな頂点v∈ {0, 1}rにいる vからtステップランダムにウォーク X：間違う乱数：|X| ≤ 2r/100 (アルゴリズムは99％で成功) t + 1回の出力の多数決を考えるのならば，t + 1ステップでXの頂 点にいる回数が半分より少なければいい v0：初期頂点 v1, . . . , vt：各ステップでの頂点 S ={i | vi ∈ X}：t + 1回中での嫌な乱数を使ったステップの集合 .示したいこと (1：今日のメイン)
. . . .. . . . P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 ：失敗確率が指数的に減少！. . . .
Formalizing[
定式化
]
乱択アルゴリズムをt + 1回走らせたい 初期設定として真にランダムな頂点v∈ {0, 1}rにいる vからtステップランダムにウォーク X：間違う乱数：|X| ≤ 2r/100 (アルゴリズムは99％で成功) t + 1回の出力の多数決を考えるのならば，t + 1ステップでXの頂 点にいる回数が半分より少なければいい v0：初期頂点 v1, . . . , vt：各ステップでの頂点 S ={i | vi ∈ X}：t + 1回中での嫌な乱数を使ったステップの集合 .示したいこと (1：今日のメイン)
. . . .. . . . P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 ：失敗確率が指数的に減少！. . . .
Formalizing[
定式化
]
乱択アルゴリズムをt + 1回走らせたい 初期設定として真にランダムな頂点v∈ {0, 1}rにいる vからtステップランダムにウォーク X：間違う乱数：|X| ≤ 2r/100 (アルゴリズムは99％で成功) t + 1回の出力の多数決を考えるのならば，t + 1ステップでXの頂 点にいる回数が半分より少なければいい v0：初期頂点 v1, . . . , vt：各ステップでの頂点 S ={i | vi ∈ X}：t + 1回中での嫌な乱数を使ったステップの集合 .示したいこと (1：今日のメイン)
. . . .. . . . P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 ：失敗確率が指数的に減少！. . . .
Formalizing[
定式化
]
乱択アルゴリズムをt + 1回走らせたい 初期設定として真にランダムな頂点v∈ {0, 1}rにいる vからtステップランダムにウォーク X：間違う乱数：|X| ≤ 2r/100 (アルゴリズムは99％で成功) t + 1回の出力の多数決を考えるのならば，t + 1ステップでXの頂 点にいる回数が半分より少なければいい v0：初期頂点 v1, . . . , vt：各ステップでの頂点 S ={i | vi ∈ X}：t + 1回中での嫌な乱数を使ったステップの集合 .示したいこと (1：今日のメイン)
. . . .. . . . P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 ：失敗確率が指数的に減少！. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1) DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない) ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1)
DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない) ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1)
DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない)
ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1)
DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない)
ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1)
DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない)
ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
初期分布：p0= n11 = (n1, . . . ,n1)TχX, χY：X, Y の特性ベクトル(X,Y の要素のところだけ1)
DX = diag(χX), DY = diag(χY)
W = 1dA：G上のrandom walkの遷移行列(今回はlazyではない)
ω1, . . . , ωn：W の固有値，仮定から|ωi| ≤ 1/10 (∀i ≥ 2)． 確率分布pに対して，Xにいる確率は χTXp = 1TDXp DXp：pのXの要素でない部分を0にする． 集合R⊂ {0, . . . , t}を用いてi∈ R回目だけXにいる確率， 1TDZtW DZt−1W · · · DZ1W DZ0p0 Zi：i∈ RならX，そうでないならY． .
示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R|. . . .
証明のために解析していこう
.示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R| ここから，示したいこと(1)： P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 が証明できる． P r[|S| > t/2] ≤ ∑ |R|>t/2 P r[vi ∈ Xならばその時に限りi∈ R] ≤ 2t+1 ( 1 5 )t+1 2 ≤ ( 2 √ 5 )t+1. . . .
証明のために解析していこう
.示したいこと (2)
. . . .. . . . 1TDZtW DZt−1W· · · DZ1W DZ0p0≤ (1/5)|R| ここから，示したいこと(1)： P r[|S| > t/2] ≤ ( 2 √ 5 )t+1 が証明できる． P r[|S| > t/2] ≤ ∑ |R|>t/2 P r[vi ∈ Xならばその時に限りi∈ R] ≤ 2t+1 ( 1 5 )t+1 2 ≤ ( 2 √ 5 )t+1. . . .
行列ノルム
ノルム(2-norm) : ∥M∥ = maxv ∥Mv∥∥v∥ Mが対称 ⇒ ∥M∥ = maxα:固有値|α| (証明は自分で：対称行列なのでvは各固有値に対する固有空間の基 底の線形和) ∥M1M2∥ ≤ ∥M1∥ ∥M2∥ DX, DY, W は対称，かつノルムが1． .注意
. . . .. . . . 遷移行列の最大固有値が1であっても，非対称遷移行列のノルムは1よ り大きくなり得る． 例：3頂点パスでノルムは√2となる遷移行列がある．. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| .Lemma
. . . .. . . . ∥DXW∥ ≤ 15 証明は後で．これを適用してみよう． p0 = W p0であるから，(グラフは正則) 1TDZtW · · · DZ1W DZ0p0 = 1 T(D ZtW )· · · (DZ0W )p0． 補題より，∥DZiW∥ ≤ { 1/5 for i∈ R 1 for i /∈ R. よって，∥(DZtW )· · · (DZ0W )∥ ≤ 5|R|1 .. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| .Lemma
. . . .. . . . ∥DXW∥ ≤ 15 証明は後で．これを適用してみよう． p0 = W p0であるから，(グラフは正則) 1TDZtW · · · DZ1W DZ0p0 = 1 T(D ZtW )· · · (DZ0W )p0． 補題より，∥DZiW∥ ≤ { 1/5 for i∈ R 1 for i /∈ R. よって，∥(DZtW )· · · (DZ0W )∥ ≤ 5|R|1 .. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| .Lemma
. . . .. . . . ∥DXW∥ ≤ 15 証明は後で．これを適用してみよう． p0 = W p0であるから，(グラフは正則) 1TDZtW · · · DZ1W DZ0p0 = 1 T(D ZtW )· · · (DZ0W )p0． 補題より，∥DZiW∥ ≤ { 1/5 for i∈ R 1 for i /∈ R. よって，∥(DZtW )· · · (DZ0W )∥ ≤ 5|R|1 .. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| .Lemma
. . . .. . . . ∥DXW∥ ≤ 15 証明は後で．これを適用してみよう． p0 = W p0であるから，(グラフは正則) 1TDZtW · · · DZ1W DZ0p0 = 1 T(D ZtW )· · · (DZ0W )p0． 補題より，∥DZiW∥ ≤ { 1/5 for i∈ R 1 for i /∈ R. よって，∥(DZtW )· · · (DZ0W )∥ ≤ 1 5|R|.. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| ∥(DZtW )· · · (DZ0W )∥ ≤ 1 5|R| ∥p0∥ = 1/√n, ∥1∥ =√nなので， 1T(DZtW )· · · (DZ0W )p0 ≤ ∥1 T∥ ∥(D ZtW )· · · (DZ0W )∥∥p0∥ = (1/5)|R|. . . .
行列ノルム
.示したいこと (2)
. . . .. . . . 1TDZtW· · · DZ1W DZ0p0 ≤ (1/5)|R| ∥(DZtW )· · · (DZ0W )∥ ≤ 1 5|R| ∥p0∥ = 1/√n, ∥1∥ =√nなので， 1T(DZtW )· · · (DZ0W )p0 ≤ ∥1 T∥ ∥(D ZtW )· · · (DZ0W )∥∥p0∥ = (1/5)|R|. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] xを任意の非零ベクトルとし，x = c11 + y (1Ty = 0)と表す∥x∥ =√(c1√n)2+∥y∥2≥ max(c1√n,∥y∥)
DXW x = c1DXW 1 + DXW y
⇒ ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥
. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] xを任意の非零ベクトルとし，x = c11 + y (1Ty = 0)と表す∥x∥ =√(c1√n)2+∥y∥2≥ max(c1√n,∥y∥)
DXW x = c1DXW 1 + DXW y
⇒ ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥
. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] xを任意の非零ベクトルとし，x = c11 + y (1Ty = 0)と表す∥x∥ =√(c1√n)2+∥y∥2≥ max(c1√n,∥y∥)
DXW x = c1DXW 1 + DXW y
⇒ ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥
. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] xを任意の非零ベクトルとし，x = c11 + y (1Ty = 0)と表す∥x∥ =√(c1√n)2+∥y∥2≥ max(c1√n,∥y∥)
DXW x = c1DXW 1 + DXW y
⇒ ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥
. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] ∥x∥ ≥ max(c1√n,∥y∥)． ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥.. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] ∥x∥ ≥ max(c1√n,∥y∥)． ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥. W 1 = 1なので，DXW 1 = χX． ∥c1DXW 1∥= c1∥χX∥ = c1 √ |X| ≤ c1 √n 10 ≤ ∥x∥ 10．(|X| ≤ n/100). . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] ∥x∥ ≥ max(c1 √ n,∥y∥)． ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥. W：対称, ϕ1 = 1⇒ {ϕ2, . . . , ϕn}：他の固有ベクトル(固有値：ωi) y =∑i≥2ciϕi (ci = ϕTi y) ∥W y∥ = ∥∑i≥2ciωiϕi∥ =√∑i≥2(ciωi)2 ≤ 101√∑i≥2(ci)2 = ∥y∥10∥DXW y∥≤ ∥DX∥∥W y∥ ≤ (1/10)∥y∥ ≤ (1/10)∥x∥
. . . .
あとは補題の証明
.Lemma (書き換えました)
. . . .. . . . ∀x, ∥DXW x∥ ≤ (1/5)∥x∥ [証明] ∥x∥ ≥ max(c1√n,∥y∥)． ∥DXW x∥ ≤∥c1DXW 1∥+∥DXW y∥. まとめると， ∥c1DXW 1∥+∥DXW y∥≤ (1/10)∥x∥ + (1/10)∥x∥ ≤ (1/5)∥x∥. . . .
