問題概略
"The Chase" とは 2 つのサイコロと偶数人のプレイヤーによって行われるゲームである。
各プレイヤーはテーブルのまわりに座っている。
対面にいるある 2 人のプレイヤーがそれぞれ 1 つのサイコロをもっているところからゲームを開始する。
各ターンにサイコロをもっている 2 人のプレイヤーがそれぞれサイコロを振る。
- 1 を出した場合，プレイヤーは自分のサイコロを左隣の人に渡す
- 6 を出した場合は右隣の人に渡す
- 1, 6 以外の目を出した場合はサイコロは移動しない
サイコロの移動が終わったときに 1 人のプレイヤーが 2 つのサイコロをもっていた場合，そのプレイヤーは負けとなりゲームは終了する。
100 人のプレイヤーでゲームを行ったとき，ゲームが終了するまでのターン数の期待値はいくつか？ 四捨五入して小数点以下 10 桁まで答えよ。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
漸化式の立式
プレイヤーの座席に時計まわりに 1, 2, …, 100 と番号をふって，これを座標として扱います。
2 つのサイコロの距離（座標の差）ははじめ 50 で，これが 0 になるまでのターン数の期待値が答えです。
サイコロの距離が の状態からゲームが終了するまでのターン数の期待値を
とおいて，サイコロの座標の差が
変化する確率を
とおきます。
の値は簡単に計算できます。
\begin{align*}
\mathrm{prob}(-2)=\frac{1}{36},\,
\mathrm{prob}(-1)=\frac{2}{9},\,
\mathrm{prob}(0)=\frac{1}{2},\,
\mathrm{prob}(1)=\frac{2}{9},\,
\mathrm{prob}(2)=\frac{1}{36}
\end{align*}
については大まかには
の和です。
\begin{align*}
e(0)=0,\, e(n)=1+\sum_{k=-2}^2 e(n+k)\mathrm{prob}(k)\quad (n\geqq 1)
\end{align*}
実際にはプレイヤーが円状に並んでいるので少し修正が必要です。
たとえば のときに
の目が出たら
になるのではなく，
になります。
の状態で
の目が出たときのサイコロの距離を
であらわします。
\begin{align*}
&\mathrm{pos}(n+k)=\min\{|n+k|,\, 100-(n+k)\}\\
&e(0)=0,\, e(n)=1+\sum_{k=-2}^2 e\left(\mathrm{pos}(n+k)\right)\mathrm{prob}(k)\quad (n\geqq 1)
\end{align*}
6人のとき
100 人の場合を考える前に例として 6 人のときを考えます。 は
以下です。
\begin{align*}
e(1) &=1+\sum_{k=-2}^2 e\left(\mathrm{pos}(1+k)\right)\mathrm{prob}(k)\\
&=1+e(\mathrm{pos}(-1))\mathrm{prob}(-2)+e(\mathrm{pos}(0))\mathrm{prob}(-1)
+e(\mathrm{pos}(1))\mathrm{prob}(0)\\
&\qquad +e(\mathrm{pos}(2))\mathrm{prob}(1)+e(\mathrm{pos}(3))\mathrm{prob}(2)\\
&=1+e(1)\cdot\frac{1}{36}+e(0)\cdot\frac{2}{9}+e(1)\cdot\frac{1}{2}
+e(2)\cdot\frac{2}{9}+e(3)\cdot\frac{1}{36}\\
&=1+\frac{19}{36}e(1)+\frac{2}{9}e(2)+\frac{1}{36}e(3)
\end{align*}
\begin{align*}
\therefore \frac{17}{36}e(1)-\frac{2}{9}e(2)-\frac{1}{36}e(3)=1
\end{align*}
,
についても同様です。
\begin{align*}
-\frac{2}{9}e(1)+\frac{17}{36}e(2)-\frac{2}{9}e(3)=1,\, -\frac{1}{18}e(1)-\frac{4}{9}e(1)e(2)+\frac{1}{1}e(3)=1
\end{align*}
これらを行列に直して解きます。
\begin{align*}
&\begin{pmatrix}
\frac{17}{36} & -\frac{2}{9} & -\frac{1}{36} \\[3pt]
-\frac{2}{9} & \frac{17}{36} & -\frac{2}{9} \\[3pt]
-\frac{1}{18} & -\frac{4}{9} & \frac{1}{2}
\end{pmatrix}
\begin{pmatrix}
e(1)\\
e(2)\\
e(3)
\end{pmatrix}
=\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}\\
&\therefore \begin{pmatrix}
e(1)\\
e(2)\\
e(3)
\end{pmatrix}
=\begin{pmatrix}
\frac{17}{36} & -\frac{2}{9} & -\frac{1}{36} \\[3pt]
-\frac{2}{9} & \frac{17}{36} & -\frac{2}{9} \\[3pt]
-\frac{1}{18} & -\frac{4}{9} & \frac{1}{2}
\end{pmatrix}^{-1}
\begin{pmatrix}
1\\
1\\
1
\end{pmatrix}=
\begin{pmatrix}
\frac{419}{44}\\[3pt]
\frac{152}{1}\\[3pt]
\frac{675}{44}
\end{pmatrix}
\end{align*}
を小数に直したものが答えになります。
mathematicaによる解答
mathematica で解きました。計算時間は約 0.02 秒です。
In[]:= ClearAll["Global`*"];
AbsoluteTiming[
nmax = 100;
pos[n_] := Min[Abs@n, nmax - Abs@n];
prob[-2] = 1/36;
prob[-1] = 2/9;
prob[0] = 1/2;
prob[1] = 2/9;
prob[2] = 1/36;
mat = IdentityMatrix[nmax/2];
For[i = 1, i <= Length@mat, i++,
For[j = -2, j <= 2, j++,
If[pos[i + j] != 0, mat[[i]][[pos[i + j]]] -= prob@j]]];
a = Transpose@ConstantArray[1, nmax/2];
ans = N[Last[(Inverse@mat) . a], 10];]
Out[]= {0.0232107, Null}
