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

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

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

組合せ数学 （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通り ゲームやギャンブル（ブリッジ、マージャン，バカラ、クラップスなど）､　情報処理に必須

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世紀の中国の本） どこでも見出せる恋人 　数学､化学､物理､哲学､情報、経済学、建築学… 高校で習う確率　＝　場合の数　=　組合せ数 でも、ちょっと数が大きいと、組合せ数は莫大になる。 だから、もう少し賢い確率論を考えよう

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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