博士たちの愛する確率 徳山 豪 東北大学 Probability that professors love

Presentation on theme: "博士たちの愛する確率 徳山 豪 東北大学 Probability that professors love"— Presentation transcript:

1 博士たちの愛する確率 徳山 豪 東北大学 Probability that professors love
Mathematics that the professor loved 徳山　豪 東北大学 Probability that professors love 博士たちの愛する確率

2 内容 数学の定理の面白さと証明アイデアの紹介 組み合わせ数学と確率 カードのシャッフル ランダムネスの利用と、その難しさ
カードのシャッフル　 　何回カードを『切れば』ランダムに混ざるか？ 　いろいろな確率の考え方 　順列とその上の確率空間 　確率状態の「距離」　 　挿入シャッフルの解析 　リッフルシャッフルの解析 ランダムネスの利用と、その難しさ

3 確率論と組合せ 日本シリーズ(7回戦、先に４勝した方が勝ち）　で、第７戦を仙台に誘致するとしよう。　誘致コスト(たとえゲームがなくても）が５百万円、開催したときの利益が二千万円だとする。　 あなたは誘致しますか？ (いろいろな落とし穴がある問題） 注意：　統計と確率は違う

4 組合せ数学 （Combinatorics)： データの分割と組み立ての数学
1 1, 1 1, 2, 1 1, 3, 3, 1 1, 4, 6, 4, 1 1, 5, 10, 10, 5, 1 1, 6, 15, 20, 15, 6, 1 Pascal’s　triangle 6C2 = 15　=　（6×5）÷2 6人の生徒から2人を選ぶ組合せ数は15通り 6枚のカードを2枚と4枚に分ける方法は15通り ゲームやギャンブル（ブリッジ、マージャン，バカラ、クラップスなど）､　情報処理に必須

5 1 1, 1 1, 2, 1 1, 3, 3, 1 1, 4, 6, 4, 1 1, 5, 10, 10, 5, 1 1, 6, 15, 20, 15, 6, 1 綺麗だと思いません? パスカルとフェルマのギャンブルに関する文通 算法統宗(16世紀の中国の本） どこでも見出せる恋人 　数学､化学､物理､哲学､情報、経済学、建築学… 高校で習う確率　＝　場合の数　=　組合せ数 でも、ちょっと数が大きいと、組合せ数は莫大になる。 だから、もう少し賢い確率論を考えよう

6 バースデートリック 確率と期待値の両方でアタックしてみよう クラスにｎ人の生徒が居る。 全員が違う誕生日である確率はどのくらいだろうか？
クラスにｎ人の生徒が居る。　全員が違う誕生日である確率はどのくらいだろうか？ ３０人のクラスだと、同じ誕生日が居る確率はどのくらい？ 確率と期待値の両方でアタックしてみよう

7 ２つの有名な確率論の道具 クーポンコレクタ定理
ｎ枚のポケモンカードがある。　チョコレートを買うとどれか１枚のカードが(等確率で）はいっている。　全部のカードを揃えるのに、何個のチョコレートを買えばいいだろうか？

8 カードのシャッフル トランプゲームでは５２枚のカードを使います。
「シャッフル」するので、いつでもカードは十分良く混ざっていると仮定しています 本当でしょうか？ 何回シャッフルすれば十分にランダムに混ざるでしょうか？

9 「定式化」：現実問題を数学にする道 カードの並び全体を数学的に捉えよう シャッフルとは数学的に何か 『よく混ざる』とは数学的に何か
数学的に解析できるような簡単なモデルを作る それと現実のモデルの比較を行う 『よく混ざる』とは数学的に何か データを順番に並べかえる(ソーティング）は情報科学では定番の概念　 混ぜる方が並べかえるのより易しそうに見えるが、『よく混ぜる』のはそんなに易しくない 『よく混ぜる』ことは、統計やアルゴリズムでは必須の技術

10 シャッフルとは順列を変更する基本操作 ゲームや手品でよくやるシャッフル 数学的には順列の置換操作
　カットシャッフル：　トランプのデックを二分して、上下を入れ替える 　中抜きシャッフル：　デックの中央部を適当に抜いて、上部に移動する 　リッフルシャッフル：　デックを上下に分け、両手で持って、ぱらぱらと交互に混ぜる。 　素人リッフルとプロフェッショナルリッフル トップインシャッフル： 一番上の札を、好きな場所に入れる 数学的には順列の置換操作

11 ４ １ ５ ２ ６ ３ ７ ４ ８ ５ ６ １ ７ ２ ８ ３ カットシャッフル

12 １ ４ ２ ５ ３ １ ４ ２ ５ ３ ６ ６ ７ ７ ８ ８ 中抜きシャッフル

13 １ ２ ２ ３ ３ １ ４ ４ ５ ５ ６ ６ ７ ７ ８ ８ トップインシャッフル

14 カードの並びと置換 １からnまでの数を並べた、長さnの順列 総数はnの階乗。超巨大な数。 Ω： 長さnの順列全体の集合
　j をσjに移す 　順列に置換を施す：　σ（π） 　順列の　σｊ　番目の要素を　ｊ　番目に移す　 　（２，３，４，１，５，６，７）はどんな置換？

15 シャッフルの条件 無限にシャッフルすると、全ての順列が生成される 無限にシャッフルすると、順列の分布が「収束する」
シャッフルの条件　 無限にシャッフルすると、全ての順列が生成される 無限にシャッフルすると、順列の分布が「収束する」 　一様分布：　全ての順列が等確率で生成される 確率論の言葉では「エルゴード性」と呼ぶ 　少ない回数で、一様に近い分布になる

16 中抜きシャッフル 中抜きシャッフルの解析はなかなか面倒 中抜きシャッフルの逆操作
　上から何枚かのところで２つに分け、上半分をカードデックにまとめて差し込む 「何枚か」を『１枚』に限定すると、トップインシャッフルになる トップインシャッフルを解析してみよう

17 トップインランダムシャッフル カードデッキの一番上のカードを取り、ランダムな位置に入れる
（2,3,4,…, 1, …,n-2,n-1,n) という形の置換 何回シャッフルすれば『十分ランダムに混ざる』 だろうか？ 第i 番目

18 １ ２ ２ ３ ３ １ ４ ４ ５ ５ ６ ６ ７ ７ ８ ８ トップインシャッフル

19 ２つの確率分布の距離 『一様に近い』とは何か？ 確率分布に距離を入れよう (確率空間の考え方）
　『一様に近い』とは何か？　確率分布に距離を入れよう　(確率空間の考え方） 一様分布　U：　全ての順列πが、確率１/n! で出現する分布 二つの分布Q1とQ２の『距離』 分布Q1で順列πが出現する確率

20 分布の混ざり方と、距離 一様分布 U： 全ての順列πが、確率１/n! で出現する分布 分布の「混ざり方」の尺度

21 完全に一様になる瞬間の判定 全てのカードが表向きだとしよう
トップインランダムシャッフルをしていて、ある時点で、『完全に混ざった』と判定できる瞬間がある それはどのような瞬間か？ そのような瞬間は(期待値として）何回目のシャッフルで起きるだろうか クーポンコレクタ問題を用いて解析しよう

22 カジノオーナーの停止ルール 全てのカードが『見える』とすると、　最初に一番下にあったカードが一番上に来て、それがランダムな位置に入れられた瞬間に『ストップ』と叫ぼう カードは完全にランダムにシャッフルされている　それはなぜか？ ストップと叫ぶまでのシャッフル回数は、クーポンコレクタ問題の答えと同じである。それはなぜか？

23 トップインシャッフルの回数 完全にランダムになるまでのシャッフルの期待値はｎ H(n)
H(n): 調和数、大体lｎ n n lｎ n + cn 回のシャッフルでストップが掛からない確率はe-c 未満 同じ回数での分布Qと一様分布Uに対して 　||Q- U|| < e –c

24 リッフルシャッフル リッフルシャッフルで、2組に分けた後での混ぜ合わせがランダムになると仮定しよう 何回リッフルシャッフルすればよいか？
5回では駄目　(52枚のカードの場合） 8回やれば大体大丈夫 なぜでしょう？　『ストップ』を叫ぶための条件はなんでしょうか？ リッフルシャッフルの逆操作を考えるのがミソ

25 １ １ ４ ２ ５ ３ ２ ４ ５ ６ ６ ３ ７ ７ ８ ８ ランダムリッフルシャッフル

26 １ １ ２ ４ ３ ６ ４ ２ ３ ５ ５ ６ ７ ７ ８ ８ 逆リッフルシャッフル

27 １ １（０） ２ ４（０） ３ ６（０） ４ ２（１） ３（１） ５ ５（１） ６ ７（１） ７ ８（１） ８ 逆リッフルシャッフルでの履歴ビット

28 １（００） １（０） １ ４（００） ４（０） ２ ２（１０） ６（０） ３ ８（１０） ２（１） ４ ６（０１） ３（１） ５ ３（１１） ５（１） ６ ５（１１） ７（１） ７ ７（１１） ８（１） ８ 逆リッフルシャッフルでの履歴ビット

29 ４（０００） １（００） １（０） １ ２（００１） ４（００） ４（０） ２ ５（０１１） ２（０１） ６（０） ３ １（１００） ８（０１） ２（１） ４ ８（１０１） ６（１０） ３（１） ５ ６（１１０） ３（１１） ５（１） ６ ３（１１１） ５（１１） ７（１） ７ ７（１１１） ７（１１） ８（１） ８ 履歴ビットが全部異なったらSTOP

30 リッフルシャッフルの解析原理 ストップが掛かったら完全にランダムにシャッフルされている ストップが掛かる時間の解析：
　バースデートリックと類似 　なぜでしょうか？

31 乱数とアルゴリズム 素敵な発明をした。これから開発を行う 発明の内容： 1000ビットのデータ ＝ ｘ 発明の秘密登録はどうすればよいか？
　発明をしたことを登録したい 　発明の内容は秘密にしたい 　発明していたことを証明できるようにしたい 発明の内容：　1000ビットのデータ　＝　ｘ 発明の秘密登録はどうすればよいか？　

32 離散対数を用いた暗号 xより大きい素数pを選ぶ p未満の数gを取る （原始根条件あり） gのx乗をpで割った剰余をyとする。
（p, g, y) を公開する。 　x を知っていることを証明することは簡単 　公開データからxを計算するのは難しい

33 離散対数とバースデートリック （p, g, y) からxを計算しよう gz をz=1,2,..,p-1まで計算すればいい
　もっといい方法はないか？

34 素数生成と乱数 素数pの生成 素数の判定は？ 適当な数を取り、素数かどうか判定する 素数分布定理から、１％程度の確率で素数にあたる
　素数の判定は？ 　フェルマテスト 　p　が素数なら、すべての数a < p について ap-1 –1 はpで割り切れる 普通の数だと、確率1/2以下でしか成り立たない 　素数とカーマイケル数 　ラビンテスト：　素数のみを選び出す

35 素数判定アルゴリズム ランダムにa<p を１００個選ぶ。 ラビンテストをおのおののaで行う すべてのa でパスすれば、素数
乱数を使わないと 　一般化リーマン予想を仮定すると、小さいほうから桁数（今の場合１００個）選べばOK 　仮定しないアルゴリズム：　2003年に発明