Sept. 24, 2015@ELC秋学校(岐阜)Exploring theLimits ofComputation

乱択の技法
Fukuoka(福岡)来嶋秀治
九州大学 大学院システム情報科学研究院

2

研究の興味
確率的アルゴリズム

敬称略 完璧サンプリング法 (MCMC法) (w/松井)
 ランダムウォークの脱乱択化 (w/牧野, 古賀, 梶野, 白髪, 山内, 山下) データストリーム中の頻出アイテム検知 (w/緒方, 山内, 山下) 置換多面体上の点の乱択丸め (w/畑埜, 瀧本, 安武, 末廣, 竹田, 永野) メディアン安定結婚問題 (w/根本)

グラフアルゴリズム
 区間グラフの部分グラフ同型性判定問題はP? NP-c? (w/斎藤, 大舘, 宇野) 区間グラフ上の支配集合数え上げ問題はP? #P-c? (w/岡本, 宇野) 最大次数4の剛性サーキットは，いつでも2つの互いに疎なハミルトン閉路に分解できるか？ (w/谷川)

分散アルゴリズム(w/ 溝口, 徐, 小野, 山内, 山下) ポピュレーションプロトコルのリーダー選挙問題の領域計算量
 円盤上の自律ロボットの脱出 (w/ Gasieniec, 山内, 山下)3「MCMCとか決定的酔歩の話をしてほしい．」
by上原先生確率的技法を使う人に増えてほしい．

4

確率、苦手
 使い所がわからない．
 簡単なの？難しいの？

実は、私の愚痴

 まるでサーカス．
 解析がマニアック．

 式が多い．
 難癖つける．
 不偏分散とか，t検定とか，細かい．

 そのくせ，「高い確率」とかやたら大雑把．
 結局，何をすれば論文になるの？

今日の趣旨
基礎技術を押さえる• 確率は定義的には「足し算，線形」の世界• ここに割り算(条件付き確率)や非線形関数(相関)を持ち込むと，途端にぐちゃぐちゃ(今日は避ける)．

確率、使って

 確率にはよくlogが出てくる
 計算量改善のチャンス！
 ２乗，平方根は確率の歴史

 Taylor展開の遺産（原理）， 一番簡単な強凸関数
 期待値は線形関数

 線形計画，多面体，線形代数etc. との相性抜群（だから皆使ってる．）
 全列挙とサンプリング Computer Scienceの多くの論文では，難しい確率は避けている．
 難しい技術を手に入れれば，論文チャンス(しかし、難しい) Martingale, 測度, 極値理論

56

乱択の技法: 今日の話題

基礎技術1.

1 𝑛11−≃𝑛e

基礎技術2. logの出てくる仕組み
基礎技術3. サンプリングのサイズはなぜ

1 2?
𝜀 レアイベント(起こりにくい事象)の確率～ 確率不等式の世界へようこそ ～基礎技術4. Median Trick
応用. 高度モンテカルロ法 サンプリングと積分
今後の課題. BPL=PSPACE?
私のよく使う技法

基礎技術 1.

1 𝑛11−≃𝑛e8Birthday paradox
問題 1.
40人の人が居ます．誕生日の同じ人の居る確率は？
401≃ ?
3659問題 2.(悪用)
ここに300人の人が居ます．各自，1～10000までの数字を一つ書いてください．もしこの中に同じ数字の人が居ると...
300
3=?
1000
100ヒント
余事象を考える．

例: それは悪魔の仕業です．この場に居る皆さんに不幸が訪れます．お祓いしましょう．
１万円です．

問題「 1, … , 𝑛 の中から一様ランダムに数字を選ぶ」操作を
𝑘 𝑛 回繰り返す．数字が重複しない確率は？
𝑛𝑛 −1 𝑛 −𝑘 𝑛⋯≃𝑛 𝑛𝑛9

10問題「 1, … , 𝑛 の中から一様ランダムに数字を選ぶ」操作を
𝑘 𝑛 回繰り返す．数字が重複しない確率は？
𝑛𝑛 −1 𝑛 −𝑘 𝑛𝑛− 𝑛𝑛⋯≤1 ⋅𝑛 𝑛𝑛𝑛(𝑘−1) 𝑛11

問題
「 1, … , 𝑛 の中から一様ランダムに数字を選ぶ」操作を
𝑘 𝑛 回繰り返す．数字が重複しない確率は？
𝑛𝑛 −1 𝑛 −𝑘 𝑛𝑛− 𝑛𝑛⋯≤1 ⋅𝑛 𝑛𝑛𝑛
1= 1−𝑛(𝑘−1) 𝑛(𝑘−1) 𝑛

12問題
「 1, … , 𝑛 の中から一様ランダムに数字を選ぶ」操作を
𝑘 𝑛 回繰り返す．数字が重複しない確率は？
𝑛𝑛 −1 𝑛 −𝑘 𝑛𝑛− 𝑛𝑛⋯≤1 ⋅𝑛 𝑛𝑛
𝑛1= 1−𝑛=1≃e(𝑘−1) 𝑛11−𝑛𝑘−1(𝑘−1) 𝑛𝑛𝑘−1

300 = 3 10000
𝑘 − 1 = 2



1 2≃ 0.135𝑒

基礎技術 2. logのでてくる仕組み

確率には log が良く出てくる．
問題 3.
人気クイズ番組「クイズ超難問！」では，２択の問題が20問出される．問題は超難問ばかりで，たとえば「強いのはどっち？ A. 赤鬼，B.青鬼」といった，勘で答えるより他にない問題ばかりである．20問連続正解すると豪華賞品（100万USD）がもらえるが，現在までに67人が挑戦して，全問正解者は居ない．全問正解が出るのは，いつごろ（何人目ごろ）か？
A. 約千人目ごろ
B. 約百万人目ごろ

149人目までの戦績
1. ○○×

2. ×
3. ○×
4. ×

5. ×
6. ○○○○○○○×
7. ○○×
8. ×
9. ×

15

9人目までの戦績
1. ○○×○○×○○×××○××○××○○×
2. ×××○○××××○○×○×○○×××○

3. ○×○○××○○×○××××○○×○××
4. ×○○×××○○××○×○×○×○××○
5. ××○××○○××○○×○××○××○○

6. ○○○○○○○×××○×○○○×○○×○
7. ○○×○○○×○×○××○×○×××○×
8. ×××○○×○○○××○○×××○×××
9. ×○×○○×○○××○××○×○×○○×

16

17

9人目までの戦績
1. 0.00100100111011011001

2. 0.11100111100101001110
3. 0.01001100101111001011

つまり4. 0.10011100110101010110

0.00000000000000000000から

5. 0.11011001100101101100

0.11111111111111111111

6. 0.00000001110100010010の数字が一様ランダム．

7. 0.00100010101101011101
8. 0.11100100011001110111
9. 0.10100100110110101001
実数乱数𝑟 ∈ [0,1)が0.000000000000000000001以下の確率 =1220

基礎技術 3. サンプリングのサイズはなぜレアイベント(起こりにくい事象)の確率～確率不等式の世界へようこそ～

1 2？
𝜀全然別の問題: tail boundの世界問題 4.
２択問題の専門家が101人居て，どの専門家も確率0.6以上で正解する．ある２択問題に対して，101人のうち過半数がAと答えた．Aが正しい確率は？
過半数が不正解する確率19

全然別の問題: tail boundの世界問題 4.
２択問題の専門家が101人居て，どの専門家も確率0.6以上で正解する．ある２択問題に対して，101人のうち過半数がAと答えた．Aが正しい確率は？
過半数が不正解する確率=正解者の数が50人以下の確率
50𝑘=0101
0.6𝑘 0.4𝑛−𝑘 =? ? ?
𝑘20

二項分布の裾21

定理[Chvatal](𝑝−𝑡)𝑚𝑗=0𝑚 𝑗𝑝 1 − 𝑝 𝑚−𝑗 ≤ exp −2𝑡 2 𝑚𝑗𝑚 = 101, 𝑝 = 0.6, 𝑡 = 0.1とすると，
50

𝑘=0101
0.6𝑘 0.4𝑛−𝑘 ≤ exp −2 × 0.12 × 101
𝑘1≤ 2 ≃ 0.135e

過半数が正解する確率 ≥ 0.865
V. Chvatal, The tail of the hypergeometric distribution, Discrete Mathematics,
25 (1979), 285–287.

一応ベイズも書いておく(省略)𝐴∗ :Aが正解, 𝐴:Aが過半数
Pr 𝐴 𝐴∗ ≥ 0.865
ベイズの定理より
Pr 𝐴∗

Pr 𝐴 ∣ 𝐴∗ Pr[𝐴∗ ]
𝐴 =
Pr[𝐴]
0.865 ∗ 0.5=
0.5 ∗ 0.865 + 0.5 ∗ 0.135
A (Aが過半数) B (Bが過半数)≥ 0.865≤ 0.135
A* (Aが正解)≤ 0.135≥ 0.865
B* (Bが正解)

事前情報が無い（Aが正解の確率が0.5）から．

22

23

超幾何分布

超幾何分布 (hypergeometric distribution)
Ωは有限集合とΞはその部分集合とする．
Ω = 𝑀, Ξ = 𝑁とする．
Ωから𝑚個の非復元抽出を行ったとき，そのサンプル𝑆に含まれるΞの要素の数が𝑛となる確率は
𝑁𝑛𝑀−𝑁𝑚−𝑛𝑀
𝑚=𝑚𝑛𝑀−𝑚𝑁−𝑛𝑀𝑁

例
トランプのカード52枚から10枚のカードを引いたとき，ハートが3枚出る確率．
1335210397

24

超幾何分布の裾定理[Chvatal]𝑁𝑀

𝑝 = , 𝑛 = 𝑝 + 𝑡 𝑚 としたとき，
𝑚𝑗=𝑘𝑁
𝑗𝑀−𝑁𝑚−𝑗𝑀𝑚≤𝑝𝑝+𝑡𝑝+𝑡1−𝑝1−𝑝−𝑡1−𝑝−𝑡𝑛V. Chvatal, The tail of the hypergeometric distribution, Discrete
Mathematics, 25 (1979), 285–287.

確率不等式

確率不等式
 Markovの不等式
 Chebyshevの不等式
 Chernoffの不等式({0,1}確率変数)
 Hoefdingの不等式(有限値)
参考: 二項分布，幾何分布の裾 Chvatal25

定理 (マルコフの不等式; Markov’s inequality)
定理: (マルコフの不等式; Markov’s inequality)
X は非負の確率変数とする. 任意の定数 𝑎 > 0 に対して,E[𝑋]
Pr 𝑋 ≥ 𝑎 ≤𝑎証明
𝐸𝑋𝑋
=𝐸𝑎𝑎∞𝑥=𝑓(𝑥)d𝑥 ≥0 𝑎∞𝑎𝑥𝑓(𝑥)d𝑥 ≥𝑎したがって
𝑋E𝑋
Pr 𝑋 ≥ 𝑎 ≤ E=𝑎𝑎∞𝑓(𝑥) d𝑥 = Pr[𝑋 ≥ 𝑎]
𝑎26

27

Chebyshev’s inequality
定理 [チェビシェフの不等式; Chebyshev’s inequality]
任意の a  0 に対して，
Var 𝑋
Pr 𝑋 − 𝐸 𝑋 ≥ 𝑎 ≤𝑎2証明

次の事実に注意する．
Pr 𝑋 − 𝐸 𝑋 ≥ 𝑎 = Pr 𝑋 − 𝐸 𝑋
マルコフの不等式より，
𝐸 𝑋−𝐸 𝑋
22Pr 𝑋 − 𝐸 𝑋≥𝑎 ≤𝑎22 ≥ 𝑎22

Var 𝑋=𝑎2

Chebyshev’s inequality
系 [チェビシェフの不等式; Chebyshev’s inequality]
任意の a  0 に対して，
Var 𝑋
Pr 𝑋 ≥ 1 + 𝑡 ⋅ E[𝑋] ≤𝑡⋅E 𝑋 2

証明
Pr 𝑋 ≥ 1 + 𝑡 ⋅ E[𝑋] = Pr 𝑋 − E[𝑋] ≥ 𝑡 ⋅ E[𝑋]
≤ Pr 𝑋 − E 𝑋 ≥ 𝑡 ⋅ E 𝑋
Var 𝑋≤𝑡⋅E 𝑋 228

Chernoff bound29

同一分布でなくて良い．

定理 [Chernoff]
𝑋1 , 𝑋2 , … , 𝑋𝑛 は相互に独立な {0,1}確率変数とし，𝑋 ≔ 𝑋1 + ⋯ + 𝑋𝑛 の期待値を𝜇とすると，𝜇e𝜀Pr 𝑋 ≥ 1 + 𝜀 𝜇 <Poisson試行
1 + 𝜀 1+𝜀と呼ばれる．
𝜇𝜀ePr 𝑋 ≤ 1 − 𝜀 𝜇 <1 − 𝜀 1−𝜀系
0 < 𝜀 ≤ 1 の場合，𝜀 2𝜇Pr 𝑋 ≥ 1 + 𝜀 𝜇 ≤ exp −3𝜀 2𝜇Pr 𝑋 ≤ 1 − 𝜀 𝜇 ≤ exp −2

30

証明のさわりPr 𝑋 ≥ 1 + 𝜀 𝜇= Pr e𝑡𝑋 ≥ e𝑡 1+𝜀 𝜇E[𝑒 𝑡𝑋 ]≤ 𝑡 1+𝜀 𝜇e(1)

各𝑋𝑖 は 0,1 確率変数より，𝑝𝑖 : = Pr 𝑋𝑖 = 1 とすると，E e𝑡𝑋𝑖 = 𝑝𝑖 e𝑡 + 1 − 𝑝𝑖Maclaurin展開𝑡= 1 + 𝑝𝑖 e − 1≤ exp(𝑝𝑖 e𝑡 − 1 )独立性より

𝑛E e𝑡𝑋 =𝑛E e𝑡𝑋𝑖 ≤𝑖=1= exp

exp 𝑝𝑖 e𝑡 − 1𝑖=1𝑛e𝑡−1𝑝𝑖= exp((𝑒 𝑡 − 1)𝜇)𝑖=1𝑡 = ln(1 + 𝜀)とすると，
exp 𝑒 𝑡 − 1 𝜇e𝜀𝜇1 ≤=
=
𝑡1+𝜀
𝜇1+𝜀
𝜇e
1+𝜀e𝜀
1 + 𝜀 1+𝜀𝜇

Hoeffding

almost surely bounded∃𝑎, 𝑏 ∈ ℝ, Pr 𝑋 ∈ 𝑎, 𝑏 = 1に拡張できる．

定理 [Hoeffding]𝑋1 , 𝑋2 , … , 𝑋𝑛 は相互に独立で0 ≤ 𝑋𝑛 ≤ 1をとる確率変数とする．
𝑋≔𝑋1 +⋯+𝑋𝑛とすると，0 < 𝑡 < 1 − E 𝑋 について，
𝑛Pr 𝑋 − 𝐸 𝑋 > 𝑡 < exp −2𝑛𝑡 2が成り立つ．

31

確率不等式

確率不等式
Markovの不等式
Chebyshevの不等式
Chernoffの不等式({0,1}確率変数)
Hoefdingの不等式(有限値)
参考: 二項分布，幾何分布の裾
Chvatal32

基礎技術 4. Median Trick全然別の問題: tail boundの世界
問題 5. (成功確率の増幅)
株価予測の専門家が101人居て，どの専門家も確率0.6以上で1年後の株価を誤差1%以内で的中させる．101人の意見からどう株価を予測する？
中央値 (median)を取る

34

35

全然別の問題: tail boundの世界
問題 5. (成功確率の増幅)
株価予測の専門家が101人居て，どの専門家も確率0.6以上で1年後の株価を誤差1%以内で的中させる．101人の意見からどう株価を予測する？
中央値 (median)を取る
中央値が誤差1%より小さい51人以上が小さめに外している1%区間

36

全然別の問題: tail boundの世界
問題 5. (成功確率の増幅)
株価予測の専門家が101人居て，どの専門家も確率0.6以上で1年後の株価を誤差1%以内で的中させる．101人の意見からどう株価を予測する？
中央値 (median)を取る
中央値が誤差1%より小さい51人以上が小さめに外している
中央値が誤差1%より大きい51人以上が大きめに外している
1%区間

全然別の問題: tail boundの世界
問題 5. (成功確率の増幅)
株価予測の専門家が101人居て，どの専門家も確率0.6以上で1年後の株価を誤差1%以内で的中させる．101人の意見からどう株価を予測する？
中央値 (median)を取る
中央値が誤差1%より小さい51人以上が小さめに外している
中央値が誤差1%より大きい51人以上が大きめに外している
いずれにせよ，過半数が外している．
1%区間
50𝑘=0

101
0.6𝑘 0.4𝑛−𝑘 =? ? ?
𝑘37

38Chernoff bound の演習
演習課題
Chernoff boundの系を使って，次の確率の上界を求めよ．
50𝑘=0101
0.6𝑘 0.4𝑛−𝑘 ≤? ? ?
𝑘Chernoff boundは配布資料 p.58 参照
系
0 < 𝜀 ≤ 1 の場合，𝜀 2𝜇Pr 𝑋 ≥ 1 + 𝜀 𝜇 ≤ exp −3𝜀 2𝜇Pr 𝑋 ≤ 1 − 𝜀 𝜇 ≤ exp −2

39

乱択の技法: 今日の話題

基礎技術1.

1 𝑛
11−
≃𝑛e

基礎技術2. logの出てくる仕組み
基礎技術3. サンプリングのサイズはなぜ1 2?
𝜀 レアイベント(起こりにくい事象)の確率～ 確率不等式の世界へようこそ ～基礎技術4. Median Trick
応用. 高度モンテカルロ法 サンプリングと積分
今後の課題. BPL=PSPACE?
私のよく使う技法

演習問題問題40
人気クイズ番組「クイズ超難問！」では，２択の問題が20問出される．問題は超難問ばかりで，たとえば「強いのはどっち？ A. 赤鬼，B.青鬼」
といった，勘で答えるより他にない問題ばかりである．20問連続正解すると豪華賞品（100万USD）がもらえるが，現在までに67人が挑戦して，全問正解者は居ない．全問正解が出るのは，いつごろ（何人目ごろ）か？
A. 約千人目ごろ
B. 約百万人目ごろ

練習課題 2224 ≃ 1.28 × 108 人を超えても達成者のいない確率は？

練習課題 3
達成者が100人になった．およそ何人チャレンジしたか？

Chernoff boundは 41
配布資料 p.58 参照

演習問題まとめ

演習課題
Chernoff boundの系を使って，次の確率の上界を求めよ．
50

𝑘=0101
0.6𝑘 0.4𝑛−𝑘 ≤? ? ?
𝑘

練習課題 2224 ≃ 1.28 × 108 人を超えても達成者のいない確率は？

練習課題 3
達成者が100人になった．およそ何人チャレンジしたか？

42何か問題ちょうだいThanks(たぶん)未解決問題
BPL=PSPACE?

平原さん，渡辺先生，山口さん
FactBPL ⊆ P

予想L = BPL方針
PSPACE完全な問題(例えば遷移問題)は乱択 log(𝑛) spaceで解ける、気がする（解けたらいいな）．

The endThank you for the attention.

演習問題 1Chernoff

𝜀2𝜇Pr 𝑋 ≤ 1 − 𝜀 𝜇 ≤ exp −2

𝑋 = 当たった人の数
𝜇 = 0.6 × 101,
𝜀 = 0.1749(50 < 1 − 0.1749 × 60.6)
50𝑘=0101
0.6𝑘 0.4𝑛−𝑘 ≤ Pr 𝑋 ≤ 1 − 0.1749 × 60.6
𝑘0.17492 × 60.6
≤ exp −21.8≤ exp −2
1= 0.9e44

演習 3

練習課題 345
達成者が100人になった．およそ何人チャレンジしたか？

 だいたい 100 × 220 = 108 人 (期待値) 挑戦者の数が3 × 108 を超えても達成者が100人に満たない確率

2 2× 300
213Pr 𝑋 < 100 ≤ Pr 𝑋 < 1 −× 300 ≤ exp −
≤ 200
32e
 挑戦者の数が0.6 × 108 未満で達成者が100人に超える確率
2 2× 60
213Pr 𝑋 > 100 = Pr 𝑋 > 1 +× 60 ≤ exp −≤ 2533e系
0 < 𝜀 ≤ 1 の場合，

𝜀2𝜇Pr 𝑋 ≥ 1 + 𝜀 𝜇 ≤ exp −3𝜀2𝜇Pr 𝑋 ≤ 1 − 𝜀 𝜇 ≤ exp −2