問題提起
一般的なあみだくじでは, 真下に行く確率が一番高くなり, 離れた箇所に行く確率が一番低い.
この性質は, 横線が少ないほど顕著であり, 多いと十分に無視できるようになるだろう.
では, 誤差が十分に無視できるような(十分に一様分布に近い)あみだくじを作るには何本横線が必要だろうか.
問題設定
あみだくじとして, 一番ベーシックな以下のパターンを考える.
- 縦線が計$N$本ある
- 横線が計$m$本ある
- 横線がどこを引くかは一様分布のランダムとする
- 横線は真横に引く
横線を一本だけ引いた場合
ある場所nに一本引いた時
あみだくじの一番上の状態を$\vec{p}^{(0)}$とする.
仮に縦軸の右から$n$番目と$n+1$番目の間に横線を引いたとする.
そうしたときに$\vec{p}^{(0)}$の$n$番目の要素$p_n$と$n+1$番目の要素$p_{n+1}$を入れ替えるため,
最終的な状態$\vec{p}^{(1)}$は
\vec{p}^{(1)}=A_n p^{(0)}
\\
A_n=\left(\matrix{
1&& &\\\
&1 & &\\
&&\cdots&&\\
&&&0&1\\
&&&1&0\\
&&&&&\cdots\\
&&&&&&1&0\\
&&&&&&0&1
}\right )
と$n$,$n+1$番目だけ
\matrix{0&1\\1&0}
にした単位行列$A_n$で表現できる.
この行列$A_n$は状態の遷移行列である.
($A_n$の$(i,j)$成分は状態$i$から状態$j$へ遷移する確率を返す)
ランダムに横線を一本だけ引いたとき
横線の引き方は$1\to 2$から$(N-1) \to N$まで計$N-1$通り存在する.
そのため, ランダムな箇所に一本引いた際の遷移行列は, 各遷移行列$A_n$の期待値をとればいい.
\vec{p}^{(1)}
=\frac{1}{N-1}\sum_n A_n \vec{p}^{(0)} \equiv A\vec{p}^{(0)}
\\
A=\frac{1}{N-1}\sum_n A_n=\left(\matrix{
1-\alpha & \alpha\\
\alpha & 1-2\alpha & \alpha\\
& \alpha & 1-2\alpha & \alpha\\
&&\cdots&\cdots&\cdots \\
&&&\alpha&1-2\alpha & \alpha\\
&&&&\alpha&1-\alpha
}\right)\\
\alpha=\frac{1}{N-1}
ランダムに横線をm本引いた場合
横線を$m$本引いた場合のあみだくじも, 前節の考え方が適用できるため
\vec{p}^{(m)}=A\vec{p}^{(m-1)}
このことから, 漸化的に計算ができ(マルコフ性)
\vec{p}^{(m)}=A\vec{p}^{(m-1)}=A^2\vec{p}^{(m-2)}=\cdots =A^m\vec{p}^{(0)}
となる.
ここで,遷移行列$A$が$U^T\Lambda U$で対角化できるとすると
\vec{p}^{(m)}=U^T\Lambda^mU\vec{p}^{(0)}
となる.
よって, $A$の固有値行列$\Lambda$を計算していく.
遷移行列Aの固有値計算
固有値の脚付き表記
$A$の要素$A_{ij}$は
A_{ij}=\begin{cases}
1-\alpha & (i=j=1,N)
\\
1-2\alpha & (i=j\neq1,N)
\\
\alpha &(i=j\pm 1)
\\
0 &\mathrm{otherwise}
\end{cases}
固有値$\lambda$と固有ベクトル$\vec{u}$はその定義から
0=(A-\lambda I)\vec{u}
そのため, 脚付き表記に書き直すと
0=\sum_j (A_{ij}-\lambda \delta_{ij})u_j =\begin{cases}
\alpha u_{i+1}+(1-2\alpha -\lambda)u_i+\alpha u_{i-1} & (i\neq 1,N)
\\
(1-\alpha -\lambda)u_1 +\alpha u_2& (i=1)
\\
(1-\alpha -\lambda)u_N +\alpha u_{N-1} & (i=N)
\end{cases}
隣接三項間漸化式を解く
計算簡略化のため, $u_0$と$u_{N+1}$分$u$を拡張する.
\alpha u_{i+1}+(1-2\alpha -\lambda)u_i+\alpha u_{i-1}\ \ \ \ \ \ \ \ \ \ (1)
\\
u_0=u_1
\\
u_{N+1}=u_{N}
この３つのうち, 一番上は隣接三項間漸化式である.
そのため,
u_{i+1}+\gamma_\pm u_i =\gamma_\mp (u_i+\gamma_\pm u_{i-1}) \ \ \ \ \ \ \ \ \ \ (2)
という等比級数の形に式変形することで
u_{i+1}+\gamma_\pm u_i =\gamma_\mp^{i} (1+\gamma_\pm )u_1
と解くことができる.
このとき式1と式2の係数から$1=\gamma_+\gamma_-$が言えるため, $\gamma=\gamma_+=1/\gamma$とする.
また, 同様に係数の比較から
\gamma+\gamma^{-1}=\frac{\lambda +2\alpha -1}{\alpha}
となる.
λについて解く
一旦ここまでで, 使用できる数式をまとめる.
u_{i+1}+\gamma^\pm u_i =\gamma^{\mp i-1} (1+\gamma^\pm )u_1
\\
\gamma+\gamma^{-1}=\frac{\lambda +2\alpha -1}{\alpha}
\\
u_{N+1}=u_N
一番上の$(\pm,\mp)=(+,-)$の式と$(\pm,\mp)=(-,+)$の式の差から
(\gamma -\gamma^{-1})u^i=[\gamma^{-i}(1+\gamma)-\gamma^{i}(1+\gamma^{-1})]u_1
$i=N$のとき$u_N=u_{N+1}$から
\gamma^{-N}(1+\gamma)-\gamma^{N}(1+\gamma^{-1})=\gamma^{-N-1}(1+\gamma)-\gamma^{N+1}(1+\gamma^{-1})
これを解くと
\gamma =\exp ( i\pi {n}/{N} )\ \ \ n=0,1,2,\cdots
となる.
このことから固有値$\lambda$は
$$
\lambda =1-2\alpha \left( 1-\frac{\gamma+\gamma^{-1}}{2} \right)=1-2\alpha\left( 1-\cos \frac{\pi n}{2N} \right)=1-4\alpha \sin^2\frac{\pi n}{2N}$$
$$(n=0,1,\cdots)$$
となる.
あみだくじの横線は何本引くべきか
求めたい状態$\vec{p}^{(m)}$は固有値の$m$乗の線形結合で表現できる.
$$
\vec{p}^{(m)}=\vec{q}^{(0)}+\lambda_1^m \vec{q}^{(1)}+\lambda_2^m \vec{q}^{(2)}+\cdots
$$
ここで, 第一項は$1-4\alpha \sin^2\frac{\pi \times 0}{2N}=1 $を用いた.
ここで, $\lambda_1,\lambda_2,\cdots $の絶対値は1未満のため,
$$
\vec{p}^{(m)}\to \vec{q}_0 \ \ \ \ \ \ \ \ (m\to \infty)
$$
である.
よって, $\vec{q}_0$は一様分布と予想できる.
このことから, あみだくじに必要な横線の数$m$は, $\lambda_1^m,\lambda_2^m,\cdots $が0とみなせる条件, すなわち二番目に大きい固有値$\lambda_1^m$が0とみなせる条件と言い換えられる.
仮に誤差が1%程度許容されると仮定すると, 引くべき横線の数$m$は
\lambda_1^m <0.01
\\
m>\frac{\log 0.01}{\log \lambda}\simeq \frac{\log 0.01}{\pi^2} N^2(N-1)=0.467 N^2(N-1)
と見積もれる(詳しい計算はおまけ参照).
同様に誤差が5%程度許容されると仮定すると
m>0.303 N^2(N-1)
数値計算での検証
実際に横線を$m$本引いた時の分布の一様分布のズレを求めた.
初期値は$p^{(0)}$をどこか一箇所が1のベクトルとして, 実際にあみだくじを繰り返すことで$p^{(m)}$を計算し
RMSE=E[ (p^{(m)}-p_{一様})^2 ]^{1/2}
の指標を$m$ごとに調べた.
結果として, $0.467 N^2(N-1)$は誤差1%程度, $0.303 N^2(N-1)$は誤差5%程度に収束することが確認できた.
[おまけ]近似の計算
\lambda_n=1-\frac{4}{N-1}\sin^2\frac{\pi n}{2N}=1-\frac{\pi^2 n^2}{N^2(N-1)}+\mathcal{O}(N^{-5})
\\
\log \lambda_n=-\sum_i \frac{1}{i}\left [1-\frac{\pi^2 n^2}{N^2(N-1)}+\mathcal{O}(N^{-5}) \right ]^i=-\frac{\pi^2 n^2}{N^2(N-1)}+\mathcal{O}(N^{-5})