tomohxxの日記

麻雀プログラミング

一人麻雀における和了確率を書き下す(4)

はじめに

今回はついに非復元抽出を想定して一人麻雀における和了確率を書き下します。これが本当の意味での一人麻雀です。非復元抽出を想定するとこれまで扱ってきた復元抽出よりも問題の難易度が上がります。当初は前回の解法を踏襲しようと試みたのですが私の計算能力不足のためそれが無理だったので、前回の「おわりに」で触れた手順少な目のルートを使って和了確率を導きます。

問題

n-1向聴の手があってこのときの有効牌の枚数を a_0枚、 n-2向聴のときの有効牌の枚数を a_1枚、以降同様に定め聴牌のときの有効牌の枚数を a_{n-1}枚とする。はじめ( t=0)に S枚の牌があるとして t巡目に和了している確率を求めよ。ただし一度捨てた牌は再び山に戻さないという非復元抽出を想定する。

解法

t巡目に n-1向聴である確率を p^{(0)}_t、 t巡目に n-2向聴である確率を p^{(1)}_t、以降同様に定め t巡目に和了している確率を p^{(n-1)}_tとする。これらは以下の連立確率漸化式に従う。

\left\{ \begin{aligned} p^{(0)}_{t+1} &= \left( 1-\frac{a_0}{S-t} \right) p^{(0)}_t & p^{(0)}_0 &= 1 \\ p^{(i)}_{t+1} &= \left( 1-\frac{a_i}{S-t} \right) p^{(i)}_t + \frac{a_{i-1}}{S-t} p^{(i-1)}_t & p^{(i)}_0 &= 0 & (0 \le i \le n-1) \\ p^{(n)}_{t+1} &= \frac{a_{n-1}}{S-t} p^{(n-1)}_t + p^{(n)}_t & p^{(n)}_0 &= 0 \end{aligned} \right. \tag{1}

(1)式を行列を使って書き直す。なお以降 a_n = 0とする。

A_t = \begin{pmatrix} 1-\frac{a_0}{S-t} & 0 & \dots & 0 & 0 \\ \frac{a_0}{S-t} & 1-\frac{a_1}{S-t} & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1-\frac{a_{n-1}}{S-t} & 0 \\ 0 & 0 & \dots & \frac{a_{n-1}}{S-t} & 1-\frac{a_n}{S-t} \\ \end{pmatrix} \tag{2}
P_t = \begin{pmatrix} p^{(0)}_t \\ p^{(1)}_t \\ \vdots \\ p^{(n-1)}_t \\ p^{(n)}_t \end{pmatrix} \tag{3}

とすると

P_{t+1} = A_t P_t \tag{4}

となる。(4)式を解くと

\displaystyle P_t = \left\{ \prod_{u=0}^{t-1} A_u \right\} P_0 \tag{5}

となる。ここで A_tは下三角行列であるから \displaystyle \prod_{u=0}^{t-1} A_uも下三角行列でありその対角成分は A_u \ (0 \le u \le t-1)の対角成分の積である。また下三角行列の固有値は対角成分であるが a_i \ (0 \le i \le n-1)はすべて異なるから \displaystyle \prod_{u=0}^{t-1} A_uは対角化可能である。よって適当な対角行列 Dと正則行列 Xが存在して

\displaystyle \prod_{u=0}^{t-1} A_u = X D X^{-1} \tag{6}

のように書ける。(6)式より適当な係数 c_i \ (0 \le i \le n)を定めればp^{(n)}_tは

\displaystyle \begin{aligned} p^{(n)}_t &= \sum_{i=0}^{n} c_i \prod_{u=0}^{t-1} \left( 1 - \frac{a_i}{S-u} \right) \\ &= \sum_{i=0}^{n} c_i \times \frac{_{S-a_i}P_t}{_{S}P_t} \\ &= \frac{1}{_{S}P_t} \sum_{i=0}^{n} c_i \times _{S-a_i} P_t \end{aligned} \tag{7}

と表せる。この係数 c_iを初期条件

\begin{aligned} p^{(n)}_0 &= p^{(n)}_1 = \dots = p^{(n)}_{n-1} = 0 \\ p^{(n)}_{n} &= \prod_{i=0}^{n-1} \frac{a_i}{S-i} = \frac{1}{_SP_n} \prod_{i=0}^{n-1} a_i = \frac{C}{_SP_n} \end{aligned} \tag{8}

によって定める。これは

\begin{pmatrix} 1 & 1 & \dots & 1 & 1 \\ S-a_0 & S-a_1 & \dots & S-a_{n-1} & S-a_n \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ _{S-a_0}P_{n-1} & _{S-a_1}P_{n-1} & \dots & _{S-a_{n-1}}P_{n-1} & _{S-a_{n}}P_{n-1} \\ _{S-a_0}P_{n} & _{S-a_1}P_{n} & \dots & _{S-a_{n-1}}P_{n} & _{S-a_{n}}P_{n} \\ \end{pmatrix} \begin{pmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-1} \\ c_{n} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ C \end{pmatrix} \tag{9}

と表せる。(9)式の行列を Vと表すことにする。 \det Vはヴァンデルモンド行列式のように計算できて

\displaystyle \det{V} = \prod_{0 \le j < k \le n} (a_j - a_k) \tag{10}

である。これとクラメルの公式を使って係数 c_iは

\displaystyle c_i = \frac{\det{V_i}}{\det{V}} \tag{11}

と表せる。 \det V_iは余因子展開を使えば

\displaystyle \det V_i = {(-1)}^{n+i} C \prod_{0 \le j < k \le n,\ j \neq i,\ k \neq i} (a_j - a_k) \tag{12}

と書ける。よって(11)式は

\displaystyle c_i = C \prod_{j \neq i} \frac{1}{a_j - a_i} \tag{13}

となる。ここで(7)式を整理する( a_n = 0に注意)。

\displaystyle \begin{aligned} p^{(n)}_t &= \sum_{i=0}^{n-1} c_i \times \frac{_{S-a_i}P_t}{_SP_t} + c_n \\ &= \sum_{i=0}^{n-1} c_i \times \frac{_{S-a_i}P_t}{_SP_t} + \sum_{i=0}^{n-1} c_i \\ &= \sum_{i=0}^{n-1} c_i \times \left( \frac{_{S-a_i}P_t}{_SP_t} - 1 \right) \end{aligned} \tag{14}

また

\displaystyle \begin{aligned} c_i &= C \left\{ \prod_{0 \le j \le n-1,\ j \neq i} \frac{1}{a_j - a_i} \right\} \times \frac{1}{a_n - a_i} \\ &= -C \left\{ \prod_{0 \le j \le n-1,\ j \neq i} \frac{1}{a_j - a_i} \right\} \times \frac{1}{a_i} & (0 \le i \le n-1) \end{aligned} \tag{15}

なので、これを(14)式に代入して整理すると

\displaystyle \begin{aligned} p^{(n)}_t &= C \sum_{i=0}^{n-1} \frac{1}{a_i} \left( 1 - \frac{_{S-a_i}P_t}{_SP_t} \right) \prod_{j \neq i} \frac{1}{a_j - a_i} \\ &= \left\{ \prod_{i=0}^{n-1} a_i \right\} \times \sum_{i=0}^{n-1} \frac{1}{a_i} \left( 1 - \frac{_{S-a_i}P_t}{_SP_t} \right) \prod_{j \neq i} \frac{1}{a_j - a_i} \end{aligned} \tag{16}

となり解を得る。

補足

復元抽出との関係

非復元抽出を想定した和了確率は復元抽出を想定した和了確率で \displaystyle \left( 1-\frac{a_i}{S} \right)^tを形式的に \displaystyle \frac{_{S-a_i}P_t}{_SP_t}に置き換えたものに等しい

証明

前回の記事の(15)式において \displaystyle \alpha_i = 1-\frac{a_i}{S}の置き換えを行うと

tomohxx.hatenablog.com

\displaystyle \begin{aligned} p^{(n)}_t &= \left\{ \prod_{i=0}^{n-1} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \frac{1-\alpha_i^t}{1-\alpha_i} \prod_{j \neq i} \frac{1}{\alpha_i - \alpha_j} \\ &= \left\{ \prod_{i=0}^{n-1} a_i \right\} \times \sum_{i=0}^{n-1} \frac{1}{a_i} \left\{ 1 - \left( 1 - \frac{a_i}{S} \right)^t \right\} \prod_{j \neq i} \frac{1}{a_j - a_i} \end{aligned} \tag{17}

となるが、 \displaystyle \left( 1-\frac{a_i}{S} \right)^tを \displaystyle \frac{_{S-a_i}P_t}{_SP_t}に置き換えると確かに(16)式に等しい。

最大値

p^{(n)}_tは t = S - \max\{a_i\}で p^{(n)}_t = 1となる。

近似

非復元抽出を想定した和了確率は S \gg tの条件で復元抽出を想定した和了確率に近似できる。

証明

\displaystyle \begin{aligned} \frac{_{S-a_i}P_t}{_SP_t} &= \prod_{u=0}^{t-1} \frac{S-u-a_i}{S-u} \\ &= \prod_{u=0}^{t-1} \frac{1 - \frac{u}{S} - \frac{a_i}{S}}{1 - \frac{u}{S}} \\ &\approx \left( 1 - \frac{a_i}{S} \right)^t \end{aligned} \tag{18}

よって

\displaystyle p^{(n)}_t \approx \left\{ \prod_{i=0}^{n-1} a_i \right\} \times \sum_{i=0}^{n-1} \frac{1}{a_i} \left\{ 1 - \left( 1 - \frac{a_i}{S} \right)^t \right\} \prod_{j \neq i} \frac{1}{a_j - a_i} \tag{19}

と近似できる。

おわりに

非復元抽出を想定した一人麻雀における和了確率を書き下しました。今後はこの成果を基に和了確率を計算するアルゴリズムを改良できないか考えてみます。もしかしたら否定的な結果に終わるかもしれません。