Stochastic matrix

In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegativereal number representing a probability.^[1][2]:10 It is also called a probability matrix, transition matrix, substitution matrix, or Markov matrix. The stochastic matrix was first developed by Andrey Markov at the beginning of the 20th century, and has found use throughout a wide variety of scientific fields, including probability theory, statistics, mathematical finance and linear algebra, as well as computer science and population genetics. There are several different definitions and types of stochastic matrices:

• A right stochastic matrix is a square matrix of nonnegative real numbers, with each row summing to 1 (so it is also called a row stochastic matrix).
• A left stochastic matrix is a square matrix of nonnegative real numbers, with each column summing to 1 (so it is also called a column stochastic matrix).
• A doubly stochastic matrix is a square matrix of nonnegative real numbers with each row and column summing to 1.
• A substochastic matrix is a real square matrix whose row sums are all ${\displaystyle \leq 1.}$

In the same vein, one may define a probability vector as a vector whose elements are nonnegative real numbers which sum to 1. Thus, each row of a right stochastic matrix (or column of a left stochastic matrix) is a probability vector. Right stochastic matrices act upon row vectors of probabilities by multiplication from the right (hence their name) and the matrix entry in the i-th row and j-th column is the probability of transition from state i to state j. Left stochastic matrices act upon column vectors of probabilities by multiplication from the left (hence their name) and the matrix entry in the i-th row and j-th column is the probability of transition from state j to state i.

This article uses the right/row stochastic matrix convention.

確率行列は、ロシアの数学者でサンクトペテルブルク大学の教授であったアンドレイ・マルコフによってマルコフ連鎖とともに開発され、彼は1906年にこのテーマについて初めて発表しました。^{[ 3 ]}当初、彼の意図した用途は言語分析やカードシャッフルなどの他の数学分野でしたが、マルコフ連鎖と行列はどちらもすぐに他の分野でも使用されるようになりました。^{[ 3 ] [ 4 ]}

確率行列は、アンドレイ・コルモゴロフなどの学者によってさらに発展し、連続時間マルコフ過程を許容することでその可能性が拡大されました。^{[ 5 ]} 1950年代までに、計量経済学^{[ 6 ]}や回路理論^{[ 7 ]}の分野で確率行列を用いた論文が登場しました。1960年代には、確率行列は行動科学^{[ 8 ]}から地質学^{[ 9 ] [ 10 ]} 、住宅計画^{[ 11 ]}まで、さらに幅広い科学研究に登場しました。さらに、これらの数十年間を通して、確率行列とマルコフ過程の用途と機能の範囲をより一般的に改善するための多くの数学的研究も行われました。

1970年代から現在に至るまで、確率行列は構造科学^{[ 12 ]}から医療診断^{[ 13 ]} 、人事管理^{[ 14 ]}に至るまで、形式的な分析を必要とするほぼすべての分野で利用されてきました。さらに、確率行列は、通常マルコフ行列という用語で呼ばれる土地変化モデリングで広く利用されています^{[ 15 ] 。}

確率行列は、基数αの有限状態空間S上のマルコフ連鎖X _tを記述します。

1タイムステップでiからjへ移動する確率がPr( j | i ) = P _{i , j}である場合、確率行列Pは、 P _{i , j}をi行目とj列目の要素として使用して与えられます。例：

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

状態iから他のすべての状態への遷移確率の合計は 1 でなければならないため、 $${\displaystyle \forall i\in \{1,\ldots ,\alpha \},\quad \sum _{j=1}^{\alpha }P_{i,j}=1;\,}$$ したがって、この行列は右確率行列である。

上記のPの各行iにわたる要素ごとの和は、より簡潔にP 1 = 1と書くことができ、ここで1はすべて 1 のα次元列ベクトルです。これを用いると、2 つの右確率行列P ′とP ′′の積も右確率行列であることがわかります。P ′ P ′′ 1 = P ′ ( P ′′ 1 ) = P ′ 1 = 1。一般に、右確率行列Pのk乗P ^kも右確率行列です。2段階でiからjへ遷移する確率は、 Pの二乗の( i , j )番目の要素によって与えられます。

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

一般に、 kステップで行列Pで与えられる有限マルコフ連鎖において、任意の状態から別の状態へ遷移する確率はP ^kで与えられる。

システムが最初にどの状態にあり、どのような確率でその状態になる可能性があるかを指定する初期確率分布は、行ベクトルとして与えられます。

定常確率ベクトルπは、遷移行列を適用しても変化しない分布（行ベクトルとして記述）として定義されます。つまり、確率行列の左固有ベクトルであり、固有値1に対応する集合{1, …, n }上の確率分布として定義されます。

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

任意の確率行列のスペクトル半径は 1 であることが示せる。ゲルシュゴリンの円定理により、確率行列のすべての固有値の絶対値は 1 以下である。より正確には、${\displaystyle n}$-による-${\displaystyle n}$確率行列は、カルペレビッチ領域として知られる複素単位円盤の部分集合内に限定される。^{[ 16 ]}この結果は、もともとコルモゴロフ^{[ 18 ]}が提起し、ニコライ・ドミトリエフとユージン・ディンキン^{[ 19 ]}が部分的に取り組んだ問題に続いて、フリドリフ・カルペレビッチ^{[ 17 ]}によって最初に得られたものである。

さらに、すべての右確率行列には、固有値 1 に対応する「明白な」列固有ベクトルがあります。これは、上記で使用したベクトル1であり、その座標はすべて 1 です。正方行列の左固有値と右固有値は同じであるため、すべての確率行列には、少なくとも固有値1に対応する左固有ベクトルがあり、すべての固有値の絶対値の最大値も 1 です。最後に、Brouwer の不動点定理(有限集合{1, ..., n }のすべての確率分布のコンパクトな凸集合に適用) は、定常確率ベクトルでもある左固有ベクトルが存在することを意味します。

一方、ペロン・フロベニウスの定理は、すべての既約確率行列がそのような定常ベクトルを持ち、固有値の最大絶対値が常に 1 であることも保証します。ただし、このような行列は既約である必要がないため、この定理を直接適用することはできません。一般に、そのようなベクトルは複数存在する可能性があります。しかし、厳密に正の要素を持つ行列（または、より一般的には、既約非周期確率行列）の場合、このベクトルは一意であり、任意のiに対して次の極限が成り立つことを観察することで計算できます。

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

ここで、π _jは行ベクトルπのj番目の要素です。これは、とりわけ、状態jにある長期的な確率が初期状態iに依存しないことを示しています。これらの計算の両方が同じ定常ベクトルを与えることは、エルゴード定理の一種であり、これは一般的にさまざまな散逸力学系で真です。つまり、システムは時間とともに定常状態に進化します。

直感的に言えば、確率行列はマルコフ連鎖を表します。確率行列を確率分布に適用すると、元の分布の確率質量が再分配されますが、総質量は維持されます。このプロセスを繰り返し適用すると、分布はマルコフ連鎖の定常分布に収束します。^{[ 2 ]： 14-17 [ 20 ]： 116}

確率行列とその積は、行列のカテゴリとマルコフ核のカテゴリの両方のサブカテゴリであるカテゴリを形成します。

タイマーと、隣接する5つの箱が並んでいるとします。時刻ゼロでは、猫が最初の箱に、ネズミが5番目の箱にいます。タイマーが進むと、猫とネズミはどちらもランダムに隣接する箱に移動します。たとえば、猫が2番目の箱にいて、ネズミが4番目の箱にいる場合、タイマーが進んだ後に猫が最初の箱にいて、ネズミが5番目の箱にいる確率は4分の1です。猫が最初の箱にいて、ネズミが5番目の箱にいる場合、タイマーが進んだ後に猫が2番目の箱にいて、ネズミが4番目の箱にいる確率は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}$（以下）は、このシステムの遷移確率を表す（この行列の行と列は、上記の可能な状態によってインデックス付けされ、遷移前の状態が行、遷移後の状態が列となる）。たとえば、状態 1（1 行目）から始めると、システムがこの状態にとどまることは不可能なので、${\displaystyle P_{11}=0}$; また、システムは状態 2 に移行できません。なぜなら、猫は同じ箱の中に留まることになるからです。${\displaystyle P_{12}=0}$同様の議論でネズミについても、${\displaystyle 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}}.}$$

位相型表現

状態 5 は吸収状態であるため、吸収までの時間の分布は離散位相型分布になります。システムが状態 2 から開始すると仮定します。状態 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である列行列を表し、状態の総和として機能します。

各状態は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進化のモデル
• ミュアヘッドの不平等
• 確率オートマトン
• 遷移率行列は、確率行列を連続時間に一般化するために使用される。