公平なシャッフルの数学

シャッフルは厳密な数学的問題を提起します：n 個の異なるオブジェクトが与えられたとき、n! 通りの可能な並び順のうち1つを、すべて等しい確率で生成することです。10 個の整数の場合、3,628,800 通りの順列が存在します。上記の数列はその空間から均一な確率で選ばれ、Fisher-YatesアルゴリズムとWeb Cryptography APIを使用してブラウザ内で完全に生成されました。

Fisher-Yates：決定版アルゴリズム

Ronald FisherとFrank Yatesは、1938年の著書Statistical Tables for Biological, Agricultural and Medical Researchで元のシャッフル手法を記述しました。Donald Knuthは後にThe Art of Computer Programming（1969年）でコンピュータ実装向けに改良しました。現代版は配列を後ろから走査します。各位置で、まだシャッフルされていない部分からランダムな要素を選び、交換します。データを1回走査するだけで、O(n)時間、O(1)の追加空間で完全な均一シャッフルが実現します。

正当性の証明は、位置kの処理後、最初のk個の要素のk!通りの部分配列がすべて等しい確率であることを示します。帰納法により、最終結果はn!通りの順列すべてを均一な確率でカバーします。よくある実装ミスである「素朴なシャッフル」は、未処理部分だけでなく配列全体から各ステップで選択してしまいます。これによりnⁿ通りの交換列がn!通りの順列に対応付けられます。一般にnⁿはn!で割り切れないため、一部の順列が他よりも出やすくなります。Fisher-Yatesアルゴリズムはこの問題を完全に回避します。

順列の驚異的な規模

階乗の増加は、他のあらゆる一般的な数学関数を凌駕します。10個の項目は3,628,800通りの配列を生成します。20個では2.4京（クインティリオン）以上になります。標準的な52枚のトランプデッキは、約8.07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7通りの並び順を生成します。この数は、観測可能な宇宙の推定原子数を超えています。

こう考えてみてください：宇宙のすべての原子が1ナノ秒に1回デッキをシャッフルし、138億年前のビッグバン以来それを続けていたとしても、行われたシャッフルの合計は52!のごくわずかな割合にすぎません。このページで行うすべてのシャッフルは、ほぼ確実に過去に存在したことがなく、今後も二度と存在しない配列を生み出します。

不動点：完全順列のパラドックス

不動点とは、シャッフル後も元の位置に留まった数のことです。上の金色のリングで囲まれた円に注目してください。それがあなたの不動点です。不動点の期待数は、シャッフルする項目数に関係なく、ちょうど1です。10個でも不動点の期待値は1。10,000個でも同じく1です。

特定の要素が固定されたまま残る確率は1/nです。n個の要素について合計すると、期待数は1になります。Leonhard Eulerが研究した完全順列（撹乱順列）の数学概念に関連するこの結果は、すべてのシャッフルの約36.8%が不動点ゼロ、36.8%がちょうど1つ、18.4%がちょうど2つであり、それ以降は急速に確率が低下することを意味します。

7回シャッフル定理

Persi DiaconisとDave Bayerは1992年に、標準的な52枚のトランプデッキのリフルシャッフルは、十分なランダム化に達するためにちょうど7回の反復が必要であることを証明しました。デジタルのFisher-Yatesシャッフルは、7回の物理的リフルシャッフルが近似するものを、1回の計算パスで完全な均一ランダム化として実現します。

教室での活用

各生徒に/sequence/1/10にアクセスして1回シャッフルしてもらいます。そして質問します：同じ順序になった人はいますか？3,628,800通りの配列があるため、一致する可能性は極めて低いです。プロジェクター実演には、/sequence/1/52を開いて繰り返しシャッフルしてください。鮮やかなリングが毎回新しいパターンに散らばり、ランダム性が即座に視覚化されます。このツールはアカウント不要、Cookie不使用、生徒のデータも保存しません。