ガチャと損保と推移行列 -線形代数の応用-

 線形代数の応用の1つである推移行列について概説する。固有値固有ベクトルといった概念が確率的現象の解析に利用できる様を見る。本稿は大学初年度レベルの線形代数の知識を前提とする。

推移行列

定義

 有限個の状態 S = \{s_0, \dots, s_n\}を考える。ある時刻の状態がs_jであるとき次の時刻の状態がs_iである確率がp_{ij}で与えられている確率的現象Xがあるとする。(i,j)成分がp_{ij}で与えられる行列をXの推移行列という。

 Xの推移行列をPとおき、ある時刻tXが状態s_iである確率をq_i(t)とし、これらを縦に並べた状態分布ベクトルをx_tとおく。即ち

P =  \begin{pmatrix}p_{11} & \cdots & p_{1n}\\ \vdots & \ddots & \vdots\\ p_{n1} & \cdots & p_{nn} \end{pmatrix}
,\quad
x_t = \begin{pmatrix}q_1(t)\\ \vdots\\ q_n(t)\end{pmatrix}
,\qquad
0 \leq p_{ij}, q_i \leq 1,\ \sum_i p_{ij} = 1,\ \sum_i q_i = 1

とする。
 このとき x_{t+1} = Px_t が成り立つ。

 例えば2つの状態s_1, s_2を考え、s_1からs_2になる確率を0.4、s_1からs_2になる確率を0.3とすると推移行列は

\begin{pmatrix}0.6 & 0.3\\ 0.4 & 0.7 \end{pmatrix}

となる。

定常分布

 推移行列Pに対してPx = xとなる状態確率ベクトルをPの定常分布と呼ぶ。即ち次の時刻においても各状態をとる確率が変わらない状態のことである。これに関して以下の命題が成り立つ。

命題1
 任意の推移行列Pに対して定常状態が少なくとも1つは存在する。

 定常分布は線形代数的に言えばP固有値1に関する固有ベクトルなのでこの命題は

 「推移行列は固有値1を持ち、その固有ベクトルとして状態分布ベクトルとなるものが存在する」

ということを主張している。
 命題1の証明を与えよう。

 まず固有値1を持つことを示す。
\sum_i p_{ij} = 1であることから 1_n = ^t(1, 1, \dots, 1)とおけば^t1_nP = ^t1_nが成り立つ。
これは^t1_nPの右作用に関する固有値1の固有ベクトルであるということである。右作用と左作用の固有値は等しい(言い方を変えれば転置行列と元の行列の固有値は等しい)のでPは(左作用に関して)固有値1を持つ。
 あるn次元実ベクトルxが状態分布ベクトルであることと^t1_nx = 1かつxのすべての成分が0以上であることは同値である。あるベクトルのすべての成分が非負または非正ならばそのベクトルに適当に何倍かして^t1_nx = 1とできるので、P固有値1の固有ベクトルとしてすべての成分が非負または非正なものが存在することを示せばよい。
 これを示すために状態集合が"確率的に分割可能"という概念を導入する。これは状態集合を2つに分割してそのどちらかからもう一方に到達する確率が0となるようにできる、ということである。即ち、状態集合Sの添え字の集合I = \{1,\dots,n\}が2つの共通部分を持たない空でない2つの部分集合 I_1, I_2の和集合となっており、 q_{ij} = q_{ji} = 0がすべての i \in I_1, j \in I_2に対して成り立つとき、Sは確率的に分割可能であるという。
 P固有値1の固有ベクトルとしてすべての成分が非負なものが存在することを示す。状態集合Sは確率的に分割可能でないと仮定してよい。なぜならばもしSが確率的に分割可能であるならば分割されたより小さい状態集合に対して定常分布を求めればよいからである。
 vP固有値1の固有ベクトルとし、vの第i成分をv_iとかく。

 I_1 = \{i \in I | v_i \geq 0\},\ I_2 = \{i \in I | v_i <0\}

 とおく。このとき

  \sum_{i \in I_2} v_i = \sum_{i \in I_2} \sum_{j \in I} p_{ij}v_j \geq \sum_{i \in I_2} \sum_{j \in I_2} p_{ij}v_j = \sum_{j \in I_2} (\sum_{i \in I_2} p_{ij}) v_j \geq \sum_{j \in I_2} v_j

であり、1つ目の不等式の等号が成立するのは  p_{ij} = 0,\ i \in I_2, j \in I_1 のときで、2つ目の等号が成立するのは  p_{ij} = 0,\ i \in I_1, j \in I_2 のとき。もしI_1, I_2のいずれも空集合でないならば状態集合Sは確率的に分割可能でないことと矛盾する。よってI_1I_2のいずれかは空集合。即ちvの成分はすべて非負あるいはすべて負となる。これが求めるベクトルである。(証明終わり)


 一般に定常分布はただ1つとは限らない。また、時刻が十分経過したときに定常分布に収束するとも限らない。実際、推移行列が\begin{pmatrix}1&0\\0&1\end{pmatrix}で与えらえる場合、すべての状態分布ベクトルが定常分布となるし、推移行列が\begin{pmatrix}0&1\\1&0\end{pmatrix}で与えらえる場合、定常分布\begin{pmatrix}1/2\\1/2\end{pmatrix}を除くすべての状態分布ベクトルは収束しない。

自動車保険料率

 推移行列の応用の1つとして自動車保険のクラス別料率が挙げられる。
 ある期間に事故を起こしたかどうかに応じて保険加入者のクラスが決定され、それによって保険料の異なる自動車保険を考える。保険料を決定する時点では加入者のクラス分布はわからないため、これに対してなんらかの仮定を置いて将来予想される保険料収入と保険金支払いがバランスるように保険料を設定する必要がある。この際にクラス分布として前項で述べた定常分布を用いるという考え方がある。その正当性を簡単な例を用いて説明しよう。
 3つのクラスが存在する自動車保険を考える。ある期間の事故発生確率はクラスによらずpで与えらており、ある期間に事故を起こすと次の期間では一つ下のクラスになり、無事故であると1つ上のクラスになる契約であるとする。このとき上のクラスから順に番号付けされているものとするとクラス分布の推移行列は

 P = \begin{pmatrix}
 1-p & 1-p & 0\\
 p & 0 & 1-p\\
 0 & p & p\\
\end{pmatrix}

で与えらえる。
 この推移行列はただ1つ定常分布を持ち、どのような初期状態から始めても定常分布に収束することを証明しよう。
 推移行列の固有多項式を計算することで固有値1, \pm\sqrt{p(1-p)}であることがわかる。したがって推移行列は対角化可能である。固有値1, \sqrt{p(1-p)}, -\sqrt{p(1-p)}固有ベクトルを1つずつとりv_1, v_2, v_3とおく。ただしv_1としては定常分布をとる。このとき、v_1, v_2, v_3は3次元ベクトル空間の基底となっているので任意の初期状態xc_1v_1 + c_2v_2 + c_3v_3,\ c_1, c_2, c_3 \in \mathbb{R} の形に書ける。
 このとき

  P^{\tau}x = c_1P^{\tau}v_1 + c_2P^{\tau}v_2 + c_3P^{\tau}v_3 = c_1v_1 + (\sqrt{p(1-p)})^{\tau}c_2v_2 + (-\sqrt{p(1-p)})^{\tau}c_3v_3

 であり、|\sqrt{p(1-p)}| < 1より\tau \rightarrow \inftyx \rightarrow c_1v_1.
 極限においても各成分の合計が1であるという条件は成り立つのでc_1 = 1がいえる。即ちx \rightarrow v_1. つまりxは定常分布に収束する。(証明終わり)

 上記の証明が具体的に固有ベクトルを求めることなく完了している点に線形代数のありがたみがある。つまり対角化可能であることさえわかれば時刻\tauにおける分布が指数関数の線形結合であることわかるのである。この例のように対角化可能であることさえわかれば固有ベクトルを具体的に求めることなく有用な情報を引き出せることが多々ある。

ガチャ

 推移行列のもう1つの応用例として最近のゲームにおけるガチャで特定の数の景品をそろえる確率を計算しよう。
 即ち、以下のような問題を考える。

 n種類のあたり景品があるくじ(復元抽出) を考える。あたりを引く確率はどれも同じであるとする。この確率をpとおく。くじを\tau回引いた後、あたり景品をi種類持っている確率をi = 0, 1, \dots, nに対して求めよ。

 景品をi種類持っている状態を第i + 1状態とすると推移行列P

  P = \begin{pmatrix}
    1 - np & & & &\\
    np & 1 - (n-1)p & & &\\
     & (n-1)p & 1 - (n-2)p & &\\
     &  & \ddots & \ddots & \\
    & & & p & 1
  \end{pmatrix}

で与えられる。
 初期状態はs_0 = ^t (1, 0, \dots, 0)(確率1で0種類の景品を持っている)なので求める確率は  P^{\tau}s_0 となる。
 これを求めるために固有値固有ベクトルを計算する。
 Pが三角行列なので固有値は対角成分に並んでいる数である。いくつかの固有ベクトルを具体的に計算することで固有ベクトルは以下となることが予想できる。

 u_i = \begin{pmatrix}
  {}_ {n}\mathrm{C}_{i}\\{}_{n-1}\mathrm{C}_{i}\\\vdots\\{}_{0}\mathrm{C}_{i}
\end{pmatrix},
\qquad
v_i = \begin{pmatrix}
  (-1)^{n-i} {}_{i}\mathrm{C}_{n}\\(-1)^{n-1-i} {}_{i}\mathrm{C}_{n-1}\\\vdots\\(-1)^{-i} {}_{i}\mathrm{C}_{0}
\end{pmatrix}, \qquad i = 0, 1, \dots, n

ただし、{}_{k}\mathrm{C}_{l}は二項係数で k < lのとき{}_{k}\mathrm{C}_{l} = 0と定義する。

 これらは実際、P固有ベクトルとなっている。即ち、以下の命題が成り立つ。

命題2
 i = 0, \dots, nに対して
  ^tu_iP = (1 - ip)^tu_i, \quad Pv_i = (1 - ip)v_i
 が成り立つ。

 証明は二項係数の計算に習熟していれば容易なので省略する。

 さらに\{u_i\}の変換行列と\{v_i\}の変換行列は互いに逆行列となる。即ち、

命題3
 ^tu_iv_j = \delta_{i,j}.
 ただし\delta_{i,j}はKroneckerのデルタ関数

 これも証明は二項係数の計算をがんばるだけである。

 これらの命題より Q = \begin{pmatrix}v_0 \cdots v_n\end{pmatrix}とおくとQ^{-1} = {}^t\begin{pmatrix}u_0 \cdots u_n\end{pmatrix}であり、

 Q^{-1}PQ = \begin{pmatrix}
  1 & & & \\
   & 1 - p & &\\
   & & \ddots &\\
   & & & 1 - np
\end{pmatrix}

が成り立つ。
 これより景品を持っていない状態から始めて\tau回くじを引いた後、景品をi種類持っている確率は

 {}_{n}\mathrm{C}_{i}\sum_{l=0}^{i} (-1)^{i-l}(1 - (n-l)p)^{\tau} {}_{i}\mathrm{C}_{l}

と計算できる。(これも二項係数の計算をがんばる。)

 例えば  n = 5, p = 0.01 の場合で100回くじを引いた後、景品を持っている確率はおよそ

0種類 : 0.59%
1種類 : 5.47%
2種類 : 19.73%
3種類 : 34.65%
4種類 : 29.65%
5種類 : 9.89%

と計算できる。