【計算機工学】続・僕のシャッフル、本当に無作為化できてる？【検証】

この記事の続きです。

上の記事で僕のシャッフルがきちんとできているかについて、僕のシャッフルをマネするchapuddingマシーンを100万人作ってその結果について議論をしました。
この際に評価方法として、シャッフルする前のカードがシャッフルした後にどこに移動したか、という情報を用いていました。
この観点からみれば、僕のシャッフルはきちんと無作為化できているということが示せました。

しかし、カードの並び順が予測できてしまうと真に無作為化できたとは言えません。
たとえば、トランプでハートの7を引いたら次はジョーカーが引ける、と予測できてしまう状態は無作為化できているとは言えないわけです。
以前書いた記事で用いた評価方法はこのようなパターンを検知できないため、今回はそれについて考察していきます。

いつも通り、誤りなど見つけた方は以下のtwitterアカウントにわかるように晒してください。
また、統計検定については勘弁のために厳密な表現を怠っていますが多めに見てください。(表現の問題で済まないような間違いがあればぜひご連絡ください)
@chapuddingEA

位置関係のデータ化

シャッフル前にデッキの上から$${i,j}$$番目にあったカードを$${c_i,c_j}$$とする。
2枚のカード$${c_i,c_j}$$のシャッフル後の位置$${a,b}$$のパターンの組み合わせを列挙すると、デッキの枚数が$${n}$$枚のとき全部で$${n\times (n-1)}$$になる。

$$
(a,b)の列挙\\
\begin{array}{cccccc}
&(1,2),&(1,3),&(1,4),&\cdots&(1,n-1),&(1,n)\\
(2,1)&&(2,3),&(2,4),&\cdots&(2,n-1),&(2,n)\\
(3,1)&(3,2),&&(2,4),&\cdots&(3,n-1),&(3,n)\\
&\vdots&&&\ddots&&\vdots\\
(n,1)&(n,2),&(n,3),&(n,4),&\cdots&(n,n-1)
\end{array}
$$

完全な無作為化がなされた場合これらはすべて等確率で出現するため、$${c_i,c_j}$$がシャッフル後にそれぞれ$${a,b}$$に移動する確率$${p_{c_i,c_j,a,b}}$$はすべて$${\frac{1}{n(n-1)}}$$となる。

検証方法

前回の記事と同様にカイ二乗適合検定を行う。
カイ二乗適合検定とはデータが予想されている割合になっているかを確認する検定であり、例えばダイスが歪んでいるかなどを検定できる。
カイ二乗検定について分かりやすく解説しているサイトがあるため、詳細に知りたい場合は以下のサイトを参照してもらいたい。

X2(カイ二乗)適合検定

$${c_i,c_j}$$がシャッフル後にそれぞれ$${a,b}$$に移動した回数$${O_{c_i,c_j,a,b}}$$を検定対象とする。
完全な無作為化がなされている場合、$${k}$$回のシャッフルをした際の$${O_{c_i,c_j,a,b}}$$の期待度数$${E_{c_i,c_j,a,b}}$$は$${k\times p_{c_i,c_j,a,b}=\frac{k}{n(n-1)}}$$となる。

検証

前回と同様に実際にプログラムに著者自身のシャッフルを再現させた上で、プログラム上の著者にデュエルマスターズのデッキ(40枚)で対戦前にするシャッフルを100万回させて上側カイ二乗適合検定を行った。
100万回のシャッフルの結果から、$${c_i,c_j}$$がシャッフル後にそれぞれ$${a,b}$$に移動した回数$${O_{c_i,c_j,a,b}}$$を測定し、以下で定義される$${\chi^2}$$値を求める。

$$
\chi^2=\sum_{i\in \\\{1,,,n\}}\sum_{j\in\{1,,,n\}\backslash \{i\}}\sum_{a\in \\\{1,,,n\}}\sum_{b\in\{1,,,n\}\backslash \{a\}}\frac{(O_{c_i,c_j,a,b}-E_{c_i,c_j,a,b})^2}{E_{c_i,c_j,a,b}}
$$

すべての$${O_{c_ic_js_is_j}}$$の期待度数は等しく$${E_{c_ic_js_is_j}}$$の値は$${\frac{1,000,000}{40\times 39}\simeq 641.0 }$$であり、自由度は$${40\times 39 \times 40\times 39-1 = 2433599}$$である。
下記サイトで調査したところ自由度2433599のカイ2乗分布の上側5%点は$${2,435,800}$$であるため、得られた$${\chi^2}$$の値がこれ以上であった場合偏りがあるといえる。(桁数があまりにも大きいため、厳密な値ではないと推測される。)

カイ２乗分布

実際に計算してみた結果、著者のシャッフルの$${\chi^2}$$値は$${2,426,382}$$だった。
この値は$${2,435,800}$$よりも小さいため、著者のシャッフの結果と完全な無作為化の間に差異が見られなかった。

まとめ

今回は、以前執筆した記事の追加実験を行いました。
前回の調査ではそれぞれのカードのシャッフル後の位置に偏りがないことを、今回の調査では2枚のカードの位置関係に偏りがないことを示しました。
今回の結果からも、僕が普段行っているファロー3～4回したのちにディールシャッフルを1回行い、そのあとファローを7～10回行うというシャッフルはよさそうだということがわかりました。
シャッフルに苦手意識を持っている方はヒンズーシャッフルを行わなくても山札の無作為化はできるので、山をひっくり返すリスクのあるヒンズーを避けてファローシャッフルをいっぱい練習しましょう。

この記事を書いた前の日に有名な数学系youtuberのヨビノリさんがシャッフルについて動画を出していたのでぜひそちらもご確認ください。
こちらの動画では、解析的にリフルシャッフル(ファローとだいたい等価)を考える論文(1992 Dave Bayer, Persi Diaconis)の紹介をしています。
(ちなみに、カードの位置関係についてはこの動画で説明されている上昇列という概念から着想を得ました。)

7回という数字は個人的に説得力が少しないと感じているのと、リフルシャッフルを解析的に考えるにあたって都合のいい確率設定をしていると感じたため、この動画で説明されている論文もそのうち読みたいなーと思っています。

ちなみに今回の検証の結果を全部テキストファイルに書き出したらテキストだけで8900キロバイトになりました。すごいデータ量。

おわり。