はじめに
やったこと
あみだくじにはどうやら偏りがあるらしい。
Wikipediaにも書いてあるし、数学的に正しい「あみだくじ必勝法」とはにも書いてある。
僕は理系ながら、数学が致命的にできないためプログラマらしくパソコンを使ってゴリ押し検証してみました。
実行条件とコード
この記事のコードはGoogleColaboratoryを用い、Python 3.7.10で実行しています。
私のGitHubに公開しており、そこからGoogleColaboratoryのソースコードを見ることができます。
あみだくじの定義
この記事でいうあみだくじとは、ごくごく一般的な真っ直ぐな横棒と縦棒で構成されるものを言います。
こんなものとか
こんなものはあみだくじと言いません（過激派）
プログラム中でのあみだくじはどう作るか
定義
縦棒をV本引き、横棒をH本引くとします。
縦棒をV個分の配列として考えれば、初期の値を通し番号として格納できます。
横棒はH回隣同士で置換することと考えることができます。
例
縦棒が4本なので、配列の値の個数は4つですね。
初期値として、配列potision = [0,1,2,3]が入っています。
横棒は4本なので、4回置換しましよう。
最初の横棒は、potision[0]とpotision[1]を置換します。
この時点で、potisionは[1,0,2,3]になります。
これをあと3回繰り返せば、[0,1,2,3]→[1,0,2,3]→[1,2,0,3]→[1,0,2,3]→[1,0,3,2]と結果が出ました。
偏りがあることの検証
まず、変数を準備します。今回は、35人クラスの席替えを想定し、35人分の縦棒と、1人1回横棒を引くと想定します。
#縦棒の本数
v_num = 35
#横棒の本数
h_num = 35
#試行回数
test_num = 10000
potision = []
result = np.zeros((v_num,v_num))
次にあみだくじを作成→記録を繰り返し行います。
関数は後述しますが、repoti(potision)は配列を通し番号で初期化、swap(potision)はランダムに配列中の場所を選び、、隣と入れ替えを行なう関数です。
横棒の本数である、h_num回入れ替えを行なっています。
最終的にできた結果を二次元result配列に整理しています。j番目の縦棒に、どの数字が入っているかをインクリメントしています。
for i in tqdm.tqdm(range(test_num)):
potision = repoti(potision)
for j in range(h_num):
swap(potision)
for j in range(v_num):
result[j][potision[j]] += 1
さっき飛ばした関数の中身
repoti()関数は0からv_numまで初期化をしています。
swap()関数は0からv_num-2までの値をランダムに取ります。
ランダムに取った値の次の値と置換するため、-2にしないとオーバーフローしますね。
def repoti(potision):
potision = list(range(v_num ))
return potision
def swap(potision):
s = random.randint(0,v_num-2)
temp = potision[s]
potision[s] = potision [s+1]
potision [s+1] = temp
return potision
この結果を表で見たかったため、エクセルで開けるCSV形式で保存します。Pandasを用いました。
GoogleColabratoryを使ったのでfiles.download()関数を用いてダウンロードが必要です。
sheet = pd.DataFrame(result)
sheet.to_csv("result.csv")
files.download('result.csv')
結果
何パターンか試行したため、もし結果だけ見たい方はGitHubからCSVファイルダウンロードしてください。
今回は35×35の結果を紹介します。
まず表をお見せしましょう。
明らかに偏りがありますね。
特に、一番左である0番目の縦棒に、元々の数値である0が入った回数は10,000回中5,134回となりました。
真ん中ら辺を見てみましょう。下は17番目の縦棒の結果をグラフにしたものです。
明らかに17が多い、結果として正規分布のようなグラフになりました。
さらに特筆すべき点として、7ほど離れると個数が0になります。
偏りがあるということが、これでわかったと思います。
結論
あみだくじをやるときは、狙うあたりの真上を選択しましょう。
作る側は、結果部分を隠さないと狙われます。
あとがき
この記事は、私の最初のQiita記事になります。
知ってる人は知ってることで、今更記事にすることではないかもしれませんが、私の衝撃がこれを上回り思わず記事にしました。
過不足や改善点などありましたら教えていただけると、とってもとっても嬉しいです。