ヒンズーシャッフルがカードの並びを忘れるのはいつか

カードのシャッフルは、確率論の基本的な問いを具体的にしたものだ。ランダムな過程は、どこから始まったかを忘れるまでにどれくらいかかるのか。 開封したばかりのカードの山は順番に並んでいる。シャッフルするたびに少しずつかき混ぜられ、最後にはもとの順序の痕跡がまったく検出できなくなる。

数学者は答えを2つの段階に分ける。混合時間(mixing time)は桁の大きさを与える。カットオフ(cutoff)はそれよりはるかに多くを語る。ある正確な瞬間のまわりで、山は「明らかに混ざっていない」状態から「すっかり混ざった」状態へと、ほとんど一気に切り替わるのだ。それより少し少なくシャッフルすればまだ見分けられるが、少し多くすればもう見分けられない。

数学者の目から見たシャッフル

ヒンズーシャッフル(overhand shuffle)では、山を片方の手に持ち、カードの小さな束をもう片方の手に落としていく。論文はこれを次のようにモデル化する。隣り合うカードの間にあるn − 1個の隙間のそれぞれが、確率pで独立に切られ、こうしてできた束の順序が逆になる。山を最後まで1回通すことを、1回のシャッフルと数える。

論文によれば、先行研究はすでに桁の大きさを突き止めていた。ペマントル(Pemantle)は混合時間をn²とn² log nの間にはさみ込み、続いてヨナソン(Jonasson)がn² log nが正しい桁であることを示した。しかし正確な定数と、そもそも鋭いカットオフが起きるのかどうかは未解決のままだった。ダイアコニス(Diaconis)とパル(Pal)は2022年に、ヒンズーシャッフルのカットオフを未解決問題として挙げている。

結果

蒋雲江は、カットオフが存在することを証明し、その位置を特定した。

定理。 切る確率pを固定すると、ヒンズーシャッフルは、一次近似で

p² / (2(1 − p)π²) × n² log n

回のシャッフルで混ざる。それより少し前では山はランダムからほど遠く、少し後ではランダムに近い。

p = 1/2、つまり平均して隙間の半分で切る場合、この式は**n² log n / (4π²)**になる。

証明のしくみ

証明は独立した3つの部分からなる。

1. 下界は1枚のカードを追跡する。その位置は驚くほどきれいに変化する。正確な余弦の形をしたパターンが、有限の山であっても既知の速さで減衰していく。山全体について足し合わせると、それらは予言された瞬間まで、もとの順序の検出可能な痕跡を保ち続ける。
2. 上界は、2枚のカードを入れ替えたことだけが違う2つの山を比べる。同じランダムな切り方で動かすと、その違いは、山の中をさまよう2つの印のついた位置のようにふるまい、やがて隣り合って合流できるようになる。それが起きる速さは下界と一致する。
3. 順列についての静的な不等式は、シャッフルとは無関係のもので、この比較を山全体についての主張に変える。これは論文で最も技術的な部分で、カードがブロックにどう散らばっているかを数える表について、再帰によって組み立てられている。

論文はまた、乱雑さを測る別の方法である相対エントロピーについてもカットオフを証明しているが、その正確な位置は特定していない。

この式が実際の山について語ること

52枚の山をp = 1/2で式に当てはめると、52² × ln 52 / (4π²)、つまり約270回のシャッフルになる。これは私たち自身の計算で、論文に載っている数字ではない。大まかな目安として読むべきだ。定理が記述しているのは非常に大きな山のふるまいで、補正項は定量化されていない。比較のために、論文はリフルシャッフルについてベイヤー(Bayer)とダイアコニスが確立した(3/2) log₂ nという規模を引用している。52枚なら約8.6回で、同じ注意が当てはまる。n² log nとlog nの差こそが、ヒンズーシャッフルをこれほど遅くしているのだ。

一次近似、理想化された手

この結果は一次近似のものである。移行が起きる時間幅やその正確な形は与えない。切る確率は固定され、切り方は独立だと仮定されているが、これは実際の手の動きを理想化したものだ。著者は脚注で、AIシステムGPT-6 Astraを「議論の展開、計算の確認、説明の準備に使った」と述べ、数学的な内容については著者が責任を負うとしている。この論文はプレプリントである。