Document

Mathematics that the professor loved
徳山 豪
東北大学
Probability that professors love
博士たちの愛する確率
内容
• 数学の定理の面白さと証明アイデアの紹介
• 組み合わせ数学と確率
• カードのシャッフル
–
–
何回カードを『切れば』ランダムに混ざるか?
いろいろな確率の考え方
•
•
–
–
順列とその上の確率空間
確率状態の「距離」
挿入シャッフルの解析
リッフルシャッフルの解析
• ランダムネスの利用と、その難しさ
確率論と組合せ
日本シリーズ(7回戦、先に4勝した方が勝ち)
で、第7戦を仙台に誘致するとしよう。 誘致
コスト(たとえゲームがなくても)が5百万円、
開催したときの利益が二千万円だとする。
あなたは誘致しますか?
(いろいろな落とし穴がある問題)
注意: 統計と確率は違う
組合せ数学 (Combinatorics):
データの分割と組み立ての数学
1
1,
1,
1,
1,
1,
1
2,
3,
4,
Pascal’s triangle
1
3,
6,
6C2
1
4,
1
= 15 = (6×5)÷2
6人の生徒から2人を選ぶ組
合せ数は15通り
5, 10, 10, 5, 1
6枚のカードを2枚と4枚に分
1, 6, 15, 20, 15, 6, 1 ける方法は15通り
ゲームやギャンブル(ブリッジ、マージャン,
バカラ、クラップスなど)、 情報処理に必須
1
1,
1,
1,
1,
1,
•パスカルとフェルマのギャンブ
ルに関する文通
1
2,
3,
4,
• 綺麗だと思いません?
1
3,
6,
•算法統宗(16世紀の中国の
本)
1
4,
1
5, 10, 10, 5, 1
• どこでも見出せる恋人
• 数学、化学、物理、哲学、情報、
経済学、建築学…
1, 6, 15, 20, 15, 6, 1
高校で習う確率 = 場合の数 = 組合せ数
でも、ちょっと数が大きいと、組合せ数は莫大になる。
だから、もう少し賢い確率論を考えよう
バースデートリック
• クラスにn人の生徒が居る。 全員が違う誕
生日である確率はどのくらいだろうか?
• 30人のクラスだと、同じ誕生日が居る確率は
どのくらい?
確率と期待値の両方でアタック
してみよう
2つの有名な確率論の道具
クーポンコレクタ定理
n枚のポケモンカードがある。 チョコレートを買
うとどれか1枚のカードが(等確率で)はいって
いる。 全部のカードを揃えるのに、何個の
チョコレートを買えばいいだろうか?
カードのシャッフル
• トランプゲームでは52枚のカードを使います。
• 「シャッフル」するので、いつでもカードは十分
良く混ざっていると仮定しています
• 本当でしょうか?
• 何回シャッフルすれば十分にランダムに混ざ
るでしょうか?
「定式化」:現実問題を数学にする道
• カードの並び全体を数学的に捉えよう
• シャッフルとは数学的に何か
– 数学的に解析できるような簡単なモデルを作る
– それと現実のモデルの比較を行う
• 『よく混ざる』とは数学的に何か
– データを順番に並べかえる(ソーティング)は情報科学で
は定番の概念
– 混ぜる方が並べかえるのより易しそうに見えるが、『よく
混ぜる』のはそんなに易しくない
– 『よく混ぜる』ことは、統計やアルゴリズムでは必須の技術
シャッフルとは順列を変更する基本操作
• ゲームや手品でよくやるシャッフル
– カットシャッフル: トランプのデックを二分して、
上下を入れ替える
– 中抜きシャッフル: デックの中央部を適当に抜
いて、上部に移動する
– リッフルシャッフル: デックを上下に分け、両手
で持って、ぱらぱらと交互に混ぜる。
•
素人リッフルとプロフェッショナルリッフル
– トップインシャッフル:
• 一番上の札を、好きな場所に入れる
• 数学的には順列の置換操作
1
2
3
4
5
6
4
7
8
5
6
7
8
1
2
3
カットシャッフル
1
2
3
4
5
1
4
2
5
6
7
8
3
6
7
8
中抜きシャッフル
1
2
3
2
3
1
4
4
5
6
7
8
5
6
7
8
トップインシャッフル
カードの並びと置換
• 1からnまでの数を並べた、長さnの順列
– π=(π1, π2, …, πn)
n=52
• 総数はnの階乗。超巨大な数。
• Ω: 長さnの順列全体の集合
• 置換: σ=(σ1, σ2,.., σn)
–
–
–
–
–
{1,2,.., n} から{1,2,..,n}への1対1射像
j をσjに移す
順列に置換を施す: σ(π)
順列の σj 番目の要素を j 番目に移す
(2,3,4,1,5,6,7)はどんな置換?
シャッフルの条件
• 無限にシャッフルすると、全ての順列が生成
される
• 無限にシャッフルすると、順列の分布が「収束
する」
– 一様分布: 全ての順列が等確率で生成される
– 確率論の言葉では「エルゴード性」と呼ぶ
•
少ない回数で、一様に近い分布になる
中抜きシャッフル
• 中抜きシャッフルの解析はなかなか面倒
• 中抜きシャッフルの逆操作
– 上から何枚かのところで2つに分け、上半分を
カードデックにまとめて差し込む
• 「何枚か」を『1枚』に限定すると、トップイン
シャッフルになる
• トップインシャッフルを解析してみよう
トップインランダムシャッフル
• カードデッキの一番上のカードを取り、ランダム
な位置に入れる
• (2,3,4,…, 1, …,n-2,n-1,n) という形の置換
第i 番目
• 何回シャッフルすれば『十分ランダムに混ざる』
だろうか?
1
2
3
2
3
1
4
4
5
6
7
8
5
6
7
8
トップインシャッフル
2つの確率分布の距離
•
『一様に近い』とは何か? 確率分布に距離
を入れよう (確率空間の考え方)
• 一様分布 U: 全ての順列πが、確率1/n! で
出現する分布
• 二つの分布Q1とQ2の『距離』
1
|| Q1  Q 2 ||  | Q1 ( )  Q 2 ( ) |
2  
分布Q1で順列πが出現する確率
分布の混ざり方と、距離
• 一様分布 U: 全ての順列πが、確率1/n! で
出現する分布
• 分布の「混ざり方」の尺度
1
|| Q U ||   | Q ( )  U ( ) |
2  
• 問題:初期状態では、Uとの距離はいくつ
か?
• 一回のトップインシャッフルでUとの距離はい
くつか?
完全に一様になる瞬間の判定
• 全てのカードが表向きだとしよう
• トップインランダムシャッフルをしていて、ある
時点で、『完全に混ざった』と判定できる瞬間
がある
• それはどのような瞬間か?
• そのような瞬間は(期待値として)何回目の
シャッフルで起きるだろうか
• クーポンコレクタ問題を用いて解析しよう
カジノオーナーの停止ルール
• 全てのカードが『見える』とすると、 最初に一
番下にあったカードが一番上に来て、それが
ランダムな位置に入れられた瞬間に『ストッ
プ』と叫ぼう
• カードは完全にランダムにシャッフルされてい
る それはなぜか?
• ストップと叫ぶまでのシャッフル回数は、クー
ポンコレクタ問題の答えと同じである。それは
なぜか?
トップインシャッフルの回数
• 完全にランダムになるまでのシャッフルの期
待値はn H(n)
– H(n): 調和数、大体ln n
• n ln n + cn 回のシャッフルでストップが掛か
らない確率はe-c 未満
• 同じ回数での分布Qと一様分布Uに対して
– ||Q- U|| < e –c
リッフルシャッフル
• リッフルシャッフルで、2組に分けた後での混
ぜ合わせがランダムになると仮定しよう
• 何回リッフルシャッフルすればよいか?
– 5回では駄目 (52枚のカードの場合)
– 8回やれば大体大丈夫
• なぜでしょう? 『ストップ』を叫ぶための条件
はなんでしょうか?
• リッフルシャッフルの逆操作を考えるのがミソ
1
2
3
1
4
5
4
2
5
6
7
8
6
3
7
8
ランダムリッフルシャッフル
1
4
6
1
2
3
2
4
3
5
7
8
5
逆リッフルシャッフル
6
7
8
1(0)
4(0)
6(0)
1
2
3
2(1)
4
3(1)
5(1)
7(1)
8(1)
5
6
7
8
逆リッフルシャッフルでの履歴ビット
1(00)
4(00)
2(10)
1(0)
4(0)
6(0)
1
2
3
8(10)
6(01)
2(1)
3(1)
4
3(11)
5(11)
5(1)
7(1)
6
7
7(11)
8(1)
8
逆リッフルシャッフルでの履歴ビット
5
4(000)
2(001)
5(011)
1(00)
4(00)
2(01)
1(0)
4(0)
6(0)
1
2
3
1(100)
8(101)
8(01)
6(10)
2(1)
3(1)
4
6(110)
3(111)
3(11)
5(11)
5(1)
7(1)
6
7
7(111)
7(11)
8(1)
8
履歴ビットが全部異なったらSTOP
5
リッフルシャッフルの解析原理
• ストップが掛かったら完全にランダムにシャッ
フルされている
• ストップが掛かる時間の解析:
– バースデートリックと類似
– なぜでしょうか?
乱数とアルゴリズム
• 素敵な発明をした。これから開発を行う
– 発明をしたことを登録したい
– 発明の内容は秘密にしたい
– 発明していたことを証明できるようにしたい
• 発明の内容: 1000ビットのデータ = x
• 発明の秘密登録はどうすればよいか?
離散対数を用いた暗号
• xより大きい素数pを選ぶ
• p未満の数gを取る (原始根条件あり)
• gのx乗をpで割った剰余をyとする。
• (p, g, y) を公開する。
• x を知っていることを証明することは簡単
• 公開データからxを計算するのは難しい
離散対数とバースデートリック
•
•
•
(p, g, y) からxを計算しよう
gz をz=1,2,..,p-1まで計算すればいい
もっといい方法はないか?
素数生成と乱数
• 素数pの生成
– 適当な数を取り、素数かどうか判定する
– 素数分布定理から、1%程度の確率で素数にあ
たる
•
素数の判定は?
– フェルマテスト
• p が素数なら、すべての数a < p について
• ap-1 –1 はpで割り切れる
• 普通の数だと、確率1/2以下でしか成り立たない
• 素数とカーマイケル数
– ラビンテスト: 素数のみを選び出す
素数判定アルゴリズム
• ランダムにa<p を100個選ぶ。
• ラビンテストをおのおののaで行う
• すべてのa でパスすれば、素数
• 乱数を使わないと
– 一般化リーマン予想を仮定すると、小さいほう
から桁数(今の場合100個)選べばOK
– 仮定しないアルゴリズム: 2003年に発明