何回カードをシャッフルすれば、トランプは十分「混ざった」と言えるのでしょうか？ 数学の確率論は私たちのこんな素朴な疑問にも答えてくれます。
私は大学1年生のときの授业でマルコフ连锁という确率の理论に出会いました。それまでに学んできた数学を使って日常の现象が解き明かされていく様に感动し、そこから确率论の沼にはまっていきました。
本記事では、まずマルコフ连锁を使ってカードのシャッフルを数学的に考える方法 を紹介し、最後に少しだけパーコレーションという別の理論を紹介します。あなたも確率論の世界に少しだけ足を踏み入れてみませんか？
【今井柚希?理学院修士１年】
确率的な现象を记述するマルコフ连锁
まず、シャッフルの原理を理解する前提として、マルコフ连锁について紹介します。マルコフ连锁とは
- ある决まった确率に従って状态が推移していき
- 现在の情报だけから未来の情报を予测できる
もののことを言います。例えば { 晴れ, 曇り, 雨 } を状态とし，状态が遷移する確率 (推移確率) を下の図のように定めます。
例えば、一番上の行にある0.3は、今日の天気が晴れのときに明日の天気が曇りになる確率が0.3 (=60%) であることを表しています。各行 (0.6, 0.3, 0.1), (0.4, 0.4, 0.2), (0.3, 0.3, 0.4) を分布と呼びます。
では、2日后の天気がどうなるかを予测してみましょう。それは
今日曇り、2日後晴れの確率 = 曇り→晴れ→晴れ + 曇り→曇り→晴れ + 曇り→雨→晴れ
??????????????? = 0.4×0.6 + 0.4×0.4 + 0.2×0.3 = 0.46
?と計算できます。他の場合の「今日→ 2日後の確率」もこれと同じように計算し、上と同様に表してみると
となります。
これを何度も繰り返して计算していくと、
という確率に少しずつ近づいていきます。明日晴れになる確率は、今日の天気によって異なります。しかし、「∞日後」が晴れの確率は現在の天気によらず0.48で等しいということを言っています。つまり、ものすごく先の未来になると、「現在の情報」の影響はなくなっていくのです。この分布 (0.48, 0.33, 0.19) を平衡分布と呼びます。
カードシャッフルをマルコフ连锁で表す
では、このマルコフ连锁を使ってカードシャッフルを数学的に表現する方法の一つを紹介します。52枚のトランプをまず半分に分けます 。もちろん、いつでもピッタリ半分に分けられるとは限りません。何枚に分かれるかは、ある決まった確率に従っているとします。次に、2つの山からカードを1枚ずつとって重ねていき、1つの山にします。詳しくいうと，山①がa枚で山②がb枚のとき，①か②からそれぞれa:bの確率でカードを1枚選んで重ねるとします。
すると、
- 52枚のカードの并び方は决まった确率に従って推移し
- 次の并び方がどうなるかは现在の并び方だけから决まる
ので、これはマルコフ连锁と言えます。
例えばカードが3枚の場合、その状态は全部で以下の6通りあります。
このとき、同様の手顺でシャッフルをすると、推移确率は
と表されます。
(1, 0, 0, 0, 0, 0) という分布、つまりシャッフル前がAの状态から始めるとすると、1回シャッフルした後は (1/2, 1/8, 1/8, 1/8, 1/8, 0) という分布に変わり、最終的には (1/6, 1/6, 1/6, 1/6, 1/6, 1/6) という平衡分布に近づいていきます。 この平衡分布を「混ざった」とします。
ここで、(1/2, 1/8, 1/8, 1/8, 1/8, 0) と (1/6, 1/6, 1/6, 1/6, 1/6, 1/6) に対してそれぞれの確率の差を計算します。1/2と1/6の差は1/3、1/8と1/6の差は1/24、0と1/6の差は1/6です。1/3と1/24を4つ、そして1/6を合計すると2/3となります。これを半分にした1/3を2つの分布の距离と呼びます。これは「1回シャッフルしたことで平衡分布にどれだけ近づいたか」を定量化したものであると考えることができます。それをグラフに表したのが下の図です。これを见ると、52枚のカードは7回程度で「混ざった」と言えそうではないでしょうか。
一方で、何か不思議なことに気がつきませんか？4回目まではまったく混ざり具合が変わっておらず、5回目以降で急に混ざりだしているのです。このように、各時点での分布と平衡分布の距离が急激に変化する現象をカットオフ现象?と呼びます。このカットオフ现象が私の研究の主役です。
确率の伝播を记述するパーコレーション
私の研究について语るには、もう一つの理论が不可欠です。それがパーコレーションです。直訳は「浸透」という意味で、水や信号、伝染病などの「伝播」する现象を数学的に表すモデルとして使われています。
さて、下の左の図のような格子の上の点や辺を考えます。格子上の隣り合う2点をランダムに繋いでいきます。繋げば辺の上を通れる (実線) ようになり、繋げなければ通行止め (破線) です。すると、右の図のようなものができます。ここでは、2点を繋ぐ確率を p としています。
このような設定のもとで、繋がれた辺を通っていったときに「無限の彼方まで辿り着ける道が存在する確率」を考えていきます。? この点を「人」とみて「辺が通れる＝病気がうつる」とみなせば、コロナのような伝染病のモデルにも応用することもできます。この場合の「無限の彼方まで辿り着ける」という想定は「病気が蔓延する」という状況になります。
さて、数学ここで「一辺の長さが n の正方形の左辺から右辺を繋ぐ経路が存在する確率」というものを考えます。n が大きいほどこの確率は小さくなります。しかもその小さくなり方は、カットオフ现象のようにある値を境に急激に変化することが知られています。
私の目標は、マルコフ连锁がカットオフを起こす要因で、カットオフを起こしている「犯人」を特定することです。そのために、「急激な変化」という点で似た振る舞いをみせるパーコレーションの理論を応用できないかと考えています。
绍介した2つの理论はどちらも代表的な确率の理论で、様々な现象を数学的に解析するのに幅広く利用されています。そんな2つの间を横断するような理论が构筑できれば、もっと确率论の世界が広がるに违いないと信じています。
?
参考文献：
- マルコフ连锁の基本とコルモゴロフ方程式、
- P. Diaconis, The cutoff phenomenon in finite Markov chains, Proc. Natl. Acad. Sci. USA 93 (1996): 1659–1664.
- D. Bayer & P. Diaconis, Trailing the dovetail shuffle to its lair, The Annals of Applied Probability 2 (1992): No.2, 294-313.
- 樋口 保成, パーコレーション理論講義 基礎からSLE理論の入り口まで, 麻豆原创社, 2014.
- 原 隆, パーコレーションで（少し）理解する感染症の伝播,
この记事は、今井柚希さん（理学院修士1年）が、大学院共通授业科目「大学院生のためのセルフプロモーションⅠ」の履修を通して制作した作品です。
今井さんの所属研究室はこちら
理学院 数学専攻 (坂井 哲 教授)
研究室贬笔アドレス