tomohxxの日記

麻雀プログラミング

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

はじめに

これまで2回にわたって一人麻雀における和了確率を求めてきましたが、そこで扱ったのはそれぞれ一向聴と二向聴の手でした。今回は前回記事の最後で触れた一般の n-1向聴の手を扱います。前回も述べたように行列を使った解法が見通しがよいので今回もそれを踏襲します。

問題

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とする。また表記を簡単にするため有効牌を引かない確率として \displaystyle \alpha_i = 1-\frac{a_{i}}{S} \ (0 \le i \le n-1)を導入する。これらは以下の連立確率漸化式に従う。

\left\{ \begin{aligned} p^{(0)}_{t+1} &= \alpha_0 p^{(0)}_t & p^{(0)}_0 &= 1 \\ p^{(i)}_{t+1} &= \alpha_i p^{(i)}_t + (1-\alpha_{i-1}) p^{(i-1)}_t & p^{(i)}_0 &= 0 & (0 \le i \le n-1) \\ p^{(n)}_{t+1} &= (1-\alpha_{n-1}) p^{(n-1)}_t + p^{(n)}_t & p^{(n)}_0 &= 0 \end{aligned} \right. \tag{1}

(1)式を形式的に解くと

\displaystyle p^{(n)}_t = (1-\alpha_{n-1}) \sum_{u=0}^{t-1} p^{(n-1)}_u \ (t \ge 1) \tag{2}

が得られるから p^{(n-1)}_tを求めることにする。 p^{(n)}_tを除いた(1)式を行列を使って書き直す。

A = \begin{pmatrix} \alpha_0 & 0 & \dots & 0 & 0 \\ 1-\alpha_0 & \alpha_1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & \alpha_{n-2} & 0 \\ 0 & 0 & \dots & 1-\alpha_{n-2} & \alpha_{n-1} \\ \end{pmatrix} \tag{3}
P_t = \begin{pmatrix} p^{(0)}_t \\ p^{(1)}_t \\ \vdots \\ p^{(n-2)}_t \\ p^{(n-1)}_t \end{pmatrix} \tag{4}

とすると

P_{t+1} = AP_t \tag{5}

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

P_t = A^t P_0 \tag{6}

となるから A^tを求めればよい。ここで Aの固有値 \alpha_i \ (0 \le i \le n-1)はすべて異なるから Aは対角化可能である。 D = X^{-1} A Xのように対角化できるとすると A^t = X D^t X^{-1}である。よって適当な係数 c_i \ (0 \le i \le n-1)を定めればp^{(n-1)}_tは

\displaystyle p^{(n-1)}_t = \sum_{i=0}^{n-1} c_i \alpha_i^t \tag{7}

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

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

によって定める。これは

\begin{pmatrix} 1 & 1 & \dots & 1 & 1 \\ \alpha_0 & \alpha_1 & \dots & \alpha_{n-2} & \alpha_{n-1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \alpha_0^{n-2} & \alpha_1^{n-2} & \dots & \alpha_{n-2}^{n-2} & \alpha_{n-1}^{n-2} \\ \alpha_0^{n-1} & \alpha_1^{n-1} & \dots & \alpha_{n-1}^{n-1} & \alpha_{n-1}^{n-1} \\ \end{pmatrix} \begin{pmatrix} c_0 \\ c_1 \\ \vdots \\ c_{n-2} \\ c_{n-1} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ C \end{pmatrix} \tag{9}

と表せる。(9)式の行列はヴァンデルモンド行列であり Vと表すことにする。ヴァンデルモンド行列式は

\displaystyle \det{V} = \prod_{0 \le j < k \le n-1} (\alpha_k - \alpha_j) \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+1} C \prod_{0 \le j < k \le n-1,\ j \neq i,\ k \neq i} (\alpha_k - \alpha_j) \tag{12}

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

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

となる。(8)式(13)式を(7)式に代入して整理すると

\displaystyle p^{(n-1)}_t = \left\{ \prod_{i=0}^{n-2} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \alpha_i^t \prod_{j \neq i} \frac{1}{\alpha_i - \alpha_j} \tag{14}

(14)式を(2)式に代入して計算すると p^{(n)}_tは

\displaystyle 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} \tag{15}

となり解を得る。なお(15)式において p^{(n)}_0 = 0となるため(2)式の tの範囲の制限を削除した。

補足

対称性

任意の \alpha_j, \alpha_kの置換に対して(14)式(15)式は不変である。

証明

c_i = c_i (\alpha_0, \alpha_1, \ldots, \alpha_{n-1})と表すことにすると以下より成り立つ。

\begin{aligned} c_i (\alpha_0, \alpha_1, \ldots, \alpha_k, \ldots, \alpha_j, \alpha_{n-1}) &= c_i (\alpha_0, \alpha_1, \ldots, \alpha_j, \ldots, \alpha_k, \alpha_{n-1}) & (i \neq j,\ i \neq k) \\ c_j (\alpha_0, \alpha_1, \ldots, \alpha_k, \ldots, \alpha_j, \alpha_{n-1}) &= c_k (\alpha_0, \alpha_1, \ldots, \alpha_j, \ldots, \alpha_k, \alpha_{n-1}) \\ c_k (\alpha_0, \alpha_1, \ldots, \alpha_k, \ldots, \alpha_j, \alpha_{n-1}) &= c_j (\alpha_0, \alpha_1, \ldots, \alpha_j, \ldots, \alpha_k, \alpha_{n-1}) \end{aligned} \tag{16}

極限値

\displaystyle \lim_{t \to \infty} p^{(n)}_t =1である。

証明1

p^{(i)}_t \ (0 \le i \le n-2)についても(7)式と同様に書けるので

\displaystyle \lim_{t \to \infty} p^{(i)}_t = 0 \ {(0 \le i \le n-1)} \tag{17}

である。すべての tに対して全事象の確率が保存されなければならないからこの命題が成り立つ。

証明2

(15)式より以下が成り立つ。

\displaystyle \lim_{t \to \infty} p^{(n)}_t = \left\{ \prod_{i=0}^{n-1} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \frac{1}{1-\alpha_i} \prod_{j \neq i} \frac{1}{\alpha_i - \alpha_j} \tag{18}

\alpha_n = 1を導入すると(18)式は

\displaystyle \begin{aligned} \lim_{t \to \infty} p^{(n)}_t &= \left\{ \prod_{i=0}^{n-1} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \left(-\frac{1}{\alpha_i - \alpha_n} \right) \prod_{j \neq i} \frac{1}{\alpha_i - \alpha_j} \\ &= \left\{ \prod_{i=0}^{n-1} (1-\alpha_i) \right\} \times \sum_{i=0}^{n-1} \left(- \prod_{0 \le j \le n,\ j \neq i} \frac{1}{\alpha_i - \alpha_j} \right) \end{aligned} \tag{18}

と書ける。ここで

\displaystyle c'_i = \prod_{0 \le j \le n,\ j \neq i} \frac{1}{\alpha_i - \alpha_j} \tag{19}

とすると c'_iは次の連立方程式の解である。

\begin{pmatrix} 1 & 1 & \dots & 1 & 1 \\ \alpha_0 & \alpha_1 & \dots & \alpha_{n-1} & \alpha_{n} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \alpha_0^{n-1} & \alpha_1^{n-1} & \dots & \alpha_{n-1}^{n-1} & \alpha_{n}^{n-1} \\ \alpha_0^{n} & \alpha_1^{n} & \dots & \alpha_{n-1}^{n} & \alpha_{n}^{n} \\ \end{pmatrix} \begin{pmatrix} c'_0 \\ c'_1 \\ \vdots \\ c'_{n-2} \\ c'_{n-1} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ 1 \end{pmatrix} \tag{20}

(19)式(20)式より

\displaystyle \sum_{i=0}^{n-1} \left(- \prod_{0 \le j \le n,\ j \neq i} \frac{1}{\alpha_i - \alpha_j} \right) = - \sum_{i=0}^{n-1} c'_i = c'_n \tag{21}

を得る。 c'_nは

\displaystyle c'_n = \prod_{i=0}^{n-1} \frac{1}{\alpha_n - \alpha_i} = \prod_{i=0}^{n-1} \frac{1}{1 - \alpha_i} \tag{22}

だから

\displaystyle \sum_{i=0}^{n-1} \left(- \prod_{0 \le j \le n,\ j \neq i} \frac{1}{\alpha_i - \alpha_j} \right) = \prod_{i=0}^{n-1} \frac{1}{1 - \alpha_i} \tag{23}

である。これを(18)式に代入すると \displaystyle \lim_{t \to \infty} p^{(n)}_t =1となる。

おわりに

復元抽出の条件でようやく一般の向聴数の手の和了確率を求めることができました。補足の極限値ですが個人的には証明2のほうが好きです。ところで極限値を求める際に N+1次行列を使いましたが(3)式の行列も N次ではなく N+1次でもよかった気がします。そのほうが解を求める手順が減り、極限値が1になることの証明も簡単になります。 \alpha_n = 1なのは(1)式の p^{(n)}_tの係数が1であることに関係していたわけです。まあ今回示した解法では事実上 p^{(i)}_t \ (1 \le i \le n-1)も求めているのでこちらのほうがお得なのではないかと思います。さて次は非復元抽出の条件で和了確率を求めたいと思います。