2015/06/22

あみだくじの確率を計算してみた

分野: データの分析,確率  レベル: マニアック

あみだくじの確率にはかなりの偏りが生じる。

あみだくじの確率を計算しようと試みてみたら,思ったよりも面白い数学の話になったので紹介します。

問題設定

縦線が $m+1$ 本,横棒が $n$ 本であるようなあみだくじを考えます。

あみだくじ

$n$ 本の横棒は「ランダムに」引かれています。ここで言うランダムとは,各々の横棒が $m$ 箇所のどこに引かれる確率も $\dfrac{1}{m}$ であるという意味です。実現されうるあみだくじのパターンは $m^n$ 通りあります。

このとき, $a$ 番からスタートして $b$ 番に到達する確率 $P_{m,n}(a,b)$ がどうなるのかという問題を考えます。(左端を $0$ 番,右端を $m$ 番とします)

実験と考察

実際に確率を計算する部分はけっこう大変な数学になるので後回しにして,まずは $m=5$ の場合の計算結果を紹介します。


〜 $n=10$ の場合〜
下の表は縦がスタート地点の場所,横がゴール地点の場所,数値が確率を表しています。例えば二行目の三列目が $0.203$ なので,左から二番目からスタートすると左から三番目にゴールする確率が $20$ %くらいということです。

$\begin{pmatrix} 0.374 & 0.297 & 0.187 & 0.093 & 0.036 & 0.013\\
0.297& 0.264 & 0.203 & 0.131 & 0.070 & 0.036\\
0.187 & 0.203 & 0.207 & 0.180 & 0.131 & 0.093\\
0.093 & 0.131 & 0.180 & 0.207 & 0.203 & 0.187\\
0.036 & 0.070 & 0.131 & 0.203 & 0.264 & 0.297\\
0.013 & 0.036 & 0.093 & 0.187 & 0.297 & 0.374
\end{pmatrix}$

  • 端からスタートすると同じ場所に到着する確率が $37$ %以上もあり,反対側の端に到着する確率は $1$ %程度しかありません。確率がかなり偏っています!
  • 対角成分が大きい,つまりスタート地点と同じ場所にゴールする確率が高い傾向があります。

〜 $n=50$ の場合〜
$\begin{pmatrix} 0.187 & 0.181 & 0.172 & 0.161 & 0.152 & 0.147\\
0.181 & 0.177 & 0.171 & 0.163 & 0.156 & 0.152\\
0.172 & 0.171 & 0.168 & 0.165 & 0.163 & 0.161\\
0.161 & 0.163 & 0.165 & 0.168 & 0.171 & 0.172\\
0.152 & 0.156 & 0.163 & 0.171 & 0.177 & 0.181\\
0.147 & 0.152 & 0.161 & 0.172 & 0.181 & 0.187\end{pmatrix}$

・偏りがだいぶなくなりましたが,横棒を $50$ 本も引いたのにまだ完全に均等にはなっていません!
($6$ 人であみだくじをやるときに横棒を $50$ 本も引く人はあまりいないと思います)

確率の計算

ここからはどうやって確率を計算するかについて説明します。行列積の定義を知っている必要があります。

(確率の計算)
まず $n=1$,つまり横棒が一本の場合を考えてみる。

丁寧に場合分けして考えてみると,
$P_{m,1}(0,0)=P_{m,1}(m,m)=1-\frac{1}{m}$
$P_{m,1}(a,a)=1-\frac{2}{m}\:(a=1,2,\cdots,m-1)$
$P_{m,1}(a,a+1)=\frac{1}{m}\:(a=0,1,\cdots, m-1)$
$P_{m,1}(a,a-1)=\frac{1}{m}\:(a=1,2,\cdots, m)$
上記以外のとき $P_{m,1}(a,b)=0$ となる。これを行列で表すと,
$P_m=\begin{pmatrix}1-\frac{1}{m}&\frac{1}{m}& & & \\\frac{1}{m}&1-\frac{2}{m}&\frac{1}{m}& &\\&\ddots&\ddots&\ddots&\\&&\frac{1}{m}&1-\frac{2}{m}&\frac{1}{m}\\&&&\frac{1}{m}&1-\frac{1}{m}\end{pmatrix}$
となる。

また,$P_{m,n}(a,b)=\displaystyle\sum_{c=0}^mP_{m,n-1}(a,c)P_{m,1}(c,b)$ であることに注意すると,行列 $P_m$ の $n$ 乗の各成分が $P_{m,n}(a,b)$ を与えることが分かる。

注:推移確率行列が $P_m$ であるようなマルコフ連鎖です。→マルコフ連鎖の基本とコルモゴロフ方程式

これで,与えられた $m,n,a,b$ に対して $P_{m,n}(a,b)$ を求めることができます(コンピュータに行列のべき乗を計算させればよい)!
例えば先ほどの実験結果で紹介した表は $P_5^{10}$,$P_5^{50}$ を計算したものです。

解析的に確率を求める

行列 $P_m$ の $n$ 乗を解析的に計算するのは無理そうだと思っていたのですが,僕の知人が気合いで(固有値,固有ベクトルを求めて)計算してくれました。

$P_{m,n}(a,b)\\=\dfrac{1}{m+1}+\dfrac{2}{m+1}\displaystyle\sum_{k=1}^m\left\{1-\frac{4}{m}\sin^2\left(\frac{k\pi}{2(m+1)}\right)\right\}^nF_k(a)F_k(b)$
ただし,$F_k(a)=\cos\left\{\frac{k\pi}{m+1}(a+\frac{1}{2})\right\}$

自分は計算の詳細を確認していないのですがおそらく合っていると思います。三角関数が登場するのが非常に面白いですね。

($m\geq 2$ のとき)$m$ を固定して $n\to \infty$ とすると確率は $\dfrac{1}{m+1}$ となり,均等に混ざることも分かります。

最後の計算をはじめ,この記事に全面的な協力をしてくださった知人に感謝。

Tag: 難しめの数学雑学・ネタまとめ

分野: データの分析,確率  レベル: マニアック