Mathematics that the professor loved 徳山豪東北大学 Probability that professors love 博士たちの愛する確率内容 • 数学の定理の面白さと証明アイデアの紹介 • 組み合わせ数学と確率 • カードのシャッフル – – 何回カードを『切れば』ランダムに混ざるか？いろいろな確率の考え方 • • – – 順列とその上の確率空間確率状態の「距離」挿入シャッフルの解析リッフルシャッフルの解析 • ランダムネスの利用と、その難しさ確率論と組合せ日本シリーズ(7回戦、先に４勝した方が勝ち）で、第７戦を仙台に誘致するとしよう。誘致コスト(たとえゲームがなくても）が５百万円、開催したときの利益が二千万円だとする。あなたは誘致しますか？ (いろいろな落とし穴がある問題）注意：統計と確率は違う組合せ数学（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までの数を並べた、長さnの順列 – π=(π1, π2, …, πn) n=52 • 総数はnの階乗。超巨大な数。 • Ω：長さnの順列全体の集合 • 置換： σ=（σ1, σ2,.., σn) – – – – – {1,2,.., n} から{1,2,..,n}への１対１射像 j をσjに移す順列に置換を施す： σ（π）順列の σｊ番目の要素をｊ番目に移す（２，３，４，１，５，６，７）はどんな置換？シャッフルの条件 • 無限にシャッフルすると、全ての順列が生成される • 無限にシャッフルすると、順列の分布が「収束する」 – 一様分布：全ての順列が等確率で生成される – 確率論の言葉では「エルゴード性」と呼ぶ • 少ない回数で、一様に近い分布になる中抜きシャッフル • 中抜きシャッフルの解析はなかなか面倒 • 中抜きシャッフルの逆操作 – 上から何枚かのところで２つに分け、上半分をカードデックにまとめて差し込む • 「何枚か」を『１枚』に限定すると、トップインシャッフルになる • トップインシャッフルを解析してみようトップインランダムシャッフル • カードデッキの一番上のカードを取り、ランダムな位置に入れる • （2,3,4,…, 1, …,n-2,n-1,n) という形の置換第i 番目 • 何回シャッフルすれば『十分ランダムに混ざる』だろうか？１２３２３１４４５６７８５６７８トップインシャッフル２つの確率分布の距離 • 『一様に近い』とは何か？確率分布に距離を入れよう (確率空間の考え方） • 一様分布 U：全ての順列πが、確率１/n! で出現する分布 • 二つの分布Q1とQ２の『距離』 1 || Q1  Q 2 ||  | Q1 ( )  Q 2 ( ) | 2   分布Q1で順列πが出現する確率分布の混ざり方と、距離 • 一様分布 U：全ての順列πが、確率１/n! で出現する分布 • 分布の「混ざり方」の尺度 1 || Q U ||   | Q ( )  U ( ) | 2   • 問題：初期状態では、Uとの距離はいくつか？ • 一回のトップインシャッフルでUとの距離はいくつか？完全に一様になる瞬間の判定 • 全てのカードが表向きだとしよう • トップインランダムシャッフルをしていて、ある時点で、『完全に混ざった』と判定できる瞬間がある • それはどのような瞬間か？ • そのような瞬間は(期待値として）何回目のシャッフルで起きるだろうか • クーポンコレクタ問題を用いて解析しようカジノオーナーの停止ルール • 全てのカードが『見える』とすると、最初に一番下にあったカードが一番上に来て、それがランダムな位置に入れられた瞬間に『ストップ』と叫ぼう • カードは完全にランダムにシャッフルされているそれはなぜか？ • ストップと叫ぶまでのシャッフル回数は、クーポンコレクタ問題の答えと同じである。それはなぜか？トップインシャッフルの回数 • 完全にランダムになるまでのシャッフルの期待値はｎ H(n) – H(n): 調和数、大体lｎ n • n lｎ n + cn 回のシャッフルでストップが掛からない確率はe-c 未満 • 同じ回数での分布Qと一様分布Uに対して – ||Q- U|| < e –c リッフルシャッフル • リッフルシャッフルで、2組に分けた後での混ぜ合わせがランダムになると仮定しよう • 何回リッフルシャッフルすればよいか？ – 5回では駄目 (52枚のカードの場合） – 8回やれば大体大丈夫 • なぜでしょう？『ストップ』を叫ぶための条件はなんでしょうか？ • リッフルシャッフルの逆操作を考えるのがミソ１２３１４５４２５６７８６３７８ランダムリッフルシャッフル１４６１２３２４３５７８５逆リッフルシャッフル６７８１（０）４（０）６（０）１２３２（１）４３（１）５（１）７（１）８（１）５６７８逆リッフルシャッフルでの履歴ビット１（００）４（００）２（１０）１（０）４（０）６（０）１２３８（１０）６（０１）２（１）３（１）４３（１１）５（１１）５（１）７（１）６７７（１１）８（１）８逆リッフルシャッフルでの履歴ビット５４（０００）２（００１）５（０１１）１（００）４（００）２（０１）１（０）４（０）６（０）１２３１（１００）８（１０１）８（０１）６（１０）２（１）３（１）４６（１１０）３（１１１）３（１１）５（１１）５（１）７（１）６７７（１１１）７（１１）８（１）８履歴ビットが全部異なったらSTOP ５リッフルシャッフルの解析原理 • ストップが掛かったら完全にランダムにシャッフルされている • ストップが掛かる時間の解析： – バースデートリックと類似 – なぜでしょうか？乱数とアルゴリズム • 素敵な発明をした。これから開発を行う – 発明をしたことを登録したい – 発明の内容は秘密にしたい – 発明していたことを証明できるようにしたい • 発明の内容： 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年に発明