確率行列

この項目では、マルコフ連鎖の遷移行列について説明しています。一般的な確率変数を要素とする行列については「ランダム行列」をご覧ください。

数学における確率行列（かくりつぎょうれつ、英: stochastic matrix）とは、マルコフ連鎖の遷移確率を表す正方行列である。全ての成分が、確率を表す非負実数となっている^[1][2]:9-11。文脈によって遷移行列（英: transition matrix）、置換行列（英: substitution matrix）、マルコフ行列（英: Markov matrix）と呼ばれることもある。また 英: probabilistic matrix と呼ばれることもある^[2]:9-11。

確率行列は20世紀初頭にアンドレイ・マルコフによって初めて導入され、確率論、統計学、数理ファイナンス、線形代数学、計算機科学、集団遺伝学といった様々な分野で活用されてきた^[2]:1-8。

確率行列には、いくつかの異なる定義・形式がある^[2]:9-11 ：

右確率行列（英: right stochastic matrix）とは、任意の行の和が1となる非負実数成分の正方行列である。

左確率行列（英: left stochastic matrix）とは、任意の列の和が1となる非負実数成分の正方行列である。

二重確率行列（英: doubly stochastic matrix）とは、任意の行、任意の列の和が1となる非負実数成分の正方行列である。

同様にして、確率ベクトル（英語版）（英: stochastic vector, probability vector） を、全ての成分が非負の実数で和が1となるベクトルと定義できる。右確率行列の全ての行（左確率行列の全ての列）は確率ベクトルである^[2]:9-11。

数学の文献での慣習に従い、本項では行ベクトルが確率ベクトルとなる右確率行列について述べる^[2]:1-8。

確率行列は、ロシア人数学者でサンクトペテルブルク大学教授であったアンドレイ・マルコフによってマルコフ連鎖とともに考案された。出版物への初めての記載は1906年である^{[2]:1-8 [3]}。マルコフは当初、これらを言語分析やカードシャッフル等の数学的題材に用いるつもりだったが、たちまち他の分野でも有用であることが分かってきた^{[2]:1-8 [3][4]}。

確率行列はアンドレイ・コルモゴロフ等の学者によってさらなる研究がなされ、連続時間マルコフ過程にも適用できるよう拡張が行われた^[5]。1950年代までに、計量経済学^[6]や回路網解析^[7]といった分野にも確率行列を用いた論文が現れた。1960年代には行動科学^[8]から地質学^[9][10]、居住地計画^[11]まで、さらに広範な科学領域で確率行列が用いられるようになった。同時に、この期間には確率行列やマルコフ過程の応用範囲や有用性を押し広げるような数学的研究もより一般的に行われた。

1970年代から現在にかけて、確率行列は建築構造設計^[12]から医療診断^[13]、人事労務管理^[14]まで、形式的な分析を必要とするほとんどあらゆる分野で用いられるようになってきた。土地利用変化モデリング（英語版）（land change modeling、この分野では「マルコフ行列」と呼ばれることが多い）においても広範に応用されている^[15]。

確率行列は、要素が有限個の状態空間 S （濃度 ${\displaystyle S}$ ）上のマルコフ連鎖 ${\displaystyle {\boldsymbol {X}}_{t}}$ を記述する。

1ステップで状態 ${\displaystyle i}$ から状態 ${\displaystyle j}$ へ遷移する確率が ${\displaystyle Pr(j\mid i)=P_{i,j}}$ であるとき、確率行列 ${\displaystyle P}$ は ${\displaystyle i}$行・${\displaystyle j}$列成分を ${\displaystyle P_{i,j}}$ とする行列で与えられる。例えば、

${\displaystyle P=\left[{\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,S}\\P_{2,1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{S,1}&P_{S,2}&\dots &P_{S,j}&\dots &P_{S,S}\\\end{matrix}}\right]}$

状態 ${\displaystyle i}$ から次の状態へ遷移する確率の総和は1なので、

${\displaystyle \sum _{j=1}^{S}P_{i,j}=1}$

となり右確率行列であるための条件を満たす^[2]:1-8。この性質を${\displaystyle P\mathbf {1} =\mathbf {1} }$ とも表せる^[16]。ここで ${\displaystyle \mathbf {1} }$ は全ての成分が ${\displaystyle 1}$ の ${\displaystyle S}$ 次元列ベクトルである。 これを使うと、2つの確率行列 ${\displaystyle P^{\prime }}$, ${\displaystyle P^{\prime \prime }}$ の積もまた右確率的であることがわかる： ${\displaystyle P^{\prime }P^{\prime \prime }\mathbf {1} =P^{\prime }(P^{\prime \prime }\mathbf {1} )=P^{\prime }\mathbf {1} =\mathbf {1} }$

一般に、確率行列 ${\displaystyle P}$ の ${\displaystyle k}$ 乗 ${\displaystyle P^{k}}$ もまた確率行列である。状態 ${\displaystyle i}$ から状態 ${\displaystyle j}$ へ2ステップで遷移する確率は${\displaystyle P^{2}}$ の第 ${\displaystyle (i,j)}$ 成分

${\displaystyle \left(P^{2}\right)_{i,j}}$

に等しく、さらに一般に、ある状態から次の状態へ ${\displaystyle k}$ ステップで遷移する確率は ${\displaystyle P^{k}}$ で与えられる。

初期状態の確率分布（系がどのような状態をどのような確率でとっているか）は行ベクトルとして与えられる。

定常（英: stationary）確率ベクトル ${\displaystyle {\boldsymbol {\pi }}}$ とは、右確率行列が右から作用しても不変な行確率ベクトルのことである。つまり、集合 ${\displaystyle \{1,...,n\}}$ 上の確率分布であって、左固有値1に対する左固有ベクトルとなるもののことである：

${\displaystyle {\boldsymbol {\pi }}P={\boldsymbol {\pi }}}$

任意の右確率行列のスペクトル半径の最大値は1であることがゲルシュゴリンの定理によりわかる。また右固有値1に対する右固有ベクトル ${\displaystyle {\boldsymbol {1}}}$ が存在することは明らかである。正方行列に対する右固有値と左固有値は一致するから、右確率行列に対して左固有値1が存在し、全ての左固有値の絶対値が1以下であることも同時に分かる。

行確率ベクトルに右確率行列を右から作用させて得られる行ベクトルもやはり確率ベクトルであるから、（各成分が非負で和が1に等しい ${\displaystyle n}$次元実ベクトル全体がコンパクト凸集合をなすことに注意すると）ブラウワーの不動点定理より定常な確率ベクトルが少なくとも一つは存在することが分かる。

一方でペロン＝フロベニウスの定理によっても、任意の既約な確率行列（任意の ${\displaystyle (i,j)}$ に対し ${\displaystyle P^{N}}$ の第 ${\displaystyle (i,j)}$ 成分が正になる自然数 ${\displaystyle N}$ が存在するような行列。行列の既約性を参照）が定常な確率ベクトルを持ち、固有値の絶対値の最大値が1となることが分かる。しかし、この定理は既約であるとは限らない確率行列には直接的に適用できない。

一般に定常な確率ベクトルは複数存在するかもしれないが、確率行列の全ての成分が正であれば（より一般的には、確率行列が既約かつ非周期的（エルゴード的（英語版）（英: ergodic））であれば）、このようなベクトルは一意的であり、任意の状態 ${\displaystyle i}$ に対し次の極限をとることで計算できる。

${\displaystyle \lim _{k\rightarrow \infty }\left(P^{k}\right)_{i,j}={\boldsymbol {\pi }}_{j}}$

ここで ${\displaystyle {\boldsymbol {\pi }}_{j}}$ は行ベクトル ${\displaystyle {\boldsymbol {\pi }}}$ の第 ${\displaystyle j}$ 成分。これより、長期的に見たとき状態 ${\displaystyle j}$ に到る確率は初期状態 ${\displaystyle i}$ に依らないことが分かる。どのような初期分布から計算しても極限では同一の定常分布に到るという事実はエルゴード定理の一形態であり、多様な散逸構造（系が時間発展し、安定的な状態に達する）において一般的に成り立っている。

直観的には確率行列はマルコフ連鎖を表し、（行ベクトルとしての）確率分布に右確率行列を右から作用させることは、元の分布の確率質量を（総和1を保ちつつ）次の確率分布へ再分配することに相当する。この作用を反復していくとマルコフ連鎖の定常状態に収束する^[2]:55–59。

5つの一列に並んだ箱と単位時間ずつ進むタイマーがあり、時刻0で、1番目の箱にはネコが、5番目の箱にはネズミが入っているとする。タイマーが進むたびに、ネコとネズミは隣の箱に全くのランダムに飛び移る。

例えば、ネコが2番目の箱・ネズミが4番目の箱に入っていれば、次の時刻にネコが1番目の箱・ネズミが5番目の箱にいる確率は 1/4、ネコが1番目の箱・ネズミが5番目の箱に入っていれば、ネコが2番目の箱・ネズミが2番目の箱に移る確率は 1 である。ネコとネズミが同じ箱に飛び移った時点でネコはネズミを食べてしまうものとし、これを「ゲーム終了」の時刻とする。確率変数 K でゲーム終了までの時間を表すことにする。

このゲームを表すマルコフ連鎖は以下のような（ネコ,ネズミ）の5通りの状態で表せる。状態の組み合わせは単純に数えると25通りだが、「ネズミの箱の番号はネコの箱の番号より小さくはならず」、「2つの箱の番号の和は偶数でなければいけない」ことから、多くの組み合わせは排除される。また、ネズミがネコに食べられる3つの場合は1つの状態としてまとめるものとする：

• 状態 1: (1,3)
• 状態 2: (1,5)
• 状態 3: (2,4)
• 状態 4: (3,5)
• 状態 5: ゲーム終了 (2,2), (3,3), (4,4)

以下の行列 ${\displaystyle P}$ で、このゲームの遷移確率を表す（行と列の番号は上記の状態の番号と対応する：行番号が遷移前の状態で、列番号が遷移後の状態^[2]:1-8）。例えば状態 1 から始めたとすると、この状態に留まったり、状態 2、状態 4 に遷移することはできない（ ${\displaystyle P_{11}=0,P_{12}=0,P_{14}=0}$ ）が、状態 3 または 5 への遷移は可能である（ ${\displaystyle P_{13},P_{15}\neq 0}$ ）。

${\displaystyle P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&1&0&0\\1/4&1/4&0&1/4&1/4\\0&0&1/2&0&1/2\\0&0&0&0&1\end{bmatrix}}}$

初期状態がいずれであっても、ネコは最終的にはネズミを捕えて、定常状態 ${\displaystyle {\boldsymbol {\pi }}=(0,0,0,0,1)}$に到達する^[2]:55–59。生存時間の平均（期待値）を計算するには、すべての状態 ${\displaystyle S_{j}}$ と時間 ${\displaystyle t_{k}}$ についての寄与 ${\displaystyle Y_{j,k}P(S=S_{j},t=t_{k})}$ を足しあげればよい。ここで ${\displaystyle Y}$ は生存状態に対しては ${\displaystyle Y_{j,k}=1}$、死亡状態に対しては ${\displaystyle Y_{j,k}=0}$ の2値をとる変数である（Y=0は和に寄与しない）。

状態 5 は吸収状態であり、吸収までの時間は離散的相型分布（英語版）に従う。系が状態 2 から始まったとする（ベクトルで表すと ${\displaystyle [0,1,0,0,0]}$ ）。ネズミが死んでしまう状態は平均生存時間に寄与しないから、状態 5 は考えなくてよい。すると初期状態と遷移確率を表す行列は次のように縮小化できる。

${\displaystyle {\boldsymbol {\tau }}=[0,1,0,0],\qquad T={\begin{bmatrix}0&0&{\frac {1}{2}}&0\\0&0&1&0\\{\frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix}}}$

また、

${\displaystyle (I-T)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}}}$

ここで ${\displaystyle I}$ は単位行列、${\displaystyle \mathbf {1} }$ は全ての成分が1の列ベクトルであり、各状態に対してその状態への遷移確率を合計するはたらきをする。

各ステップで系はどれかの状態をとるから、ネズミの平均生存時間は、系がいずれかの生存状態にある確率を全ての時間にわたって合計したものに等しく（和は行列項級数として考える）、

${\displaystyle E[K]={\boldsymbol {\tau }}\left(I+T+T^{2}+\cdots \right){\boldsymbol {1}}={\boldsymbol {\tau }}(I-T)^{-1}{\boldsymbol {1}}=4.5}$

となる。高次のモーメントは

${\displaystyle E[K(K-1)\dots (K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n-1}\mathbf {1} }$

で与えられる。

• ムーアヘッドの不等式（英語版）
• ペロン＝フロベニウスの定理
• 密度行列
• 二重確率行列
• 相型分布（英語版）
• 確率的オートマトン（英語版）
• 分子進化モデル （DNA進化のモデル（英語版））
• マルコフ核（英語版） （連続的な状態空間における確率行列の対応物）