確率行列のソースを表示

{{Otheruses|[[マルコフ連鎖]]の遷移行列|一般的な確率変数を要素とする行列|ランダム行列}}

[[数学]]における'''確率行列'''（かくりつぎょうれつ、{{Lang-en-short|stochastic matrix}}）とは、[[マルコフ連鎖]]の遷移確率を表す[[正方行列]]である。全ての成分が、確率を表す非負実数となっている<ref>{{Cite book | doi = 10.1007/0-387-21525-5_1 | first1 = S. R. | last1 = Asmussen| chapter = Markov Chains | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 3–8 | year = 2003 | isbn = 978-0-387-00211-8 | pmid = | pmc = }}</ref><ref name=Gagniuc2017>{{Cite book|title=Markov Chains: From Theory to Implementation and Experimentation|last=Gagniuc|first=Paul A.|publisher=John Wiley & Sons|year=2017|isbn=978-1-119-38755-8|location=USA, NJ|pages=9–11}}</ref>{{rp|9-11}}。文脈によって'''遷移行列'''（{{Lang-en-short|transition matrix|links=no}}）、'''置換行列'''（{{Lang-en-short|substitution matrix|links=no}}）、'''マルコフ行列'''（{{Lang-en-short|Markov matrix|links=no}}）と呼ばれることもある。また {{Lang-en-short|probabilistic matrix|links=no}} と呼ばれることもある<ref name=Gagniuc2017/>{{rp|9-11}}。

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

確率行列には、いくつかの異なる定義・形式がある<ref name=Gagniuc2017/>{{rp|9-11}} ：

:'''右確率行列'''（{{Lang-en-short|right stochastic matrix|links=no}}）とは、任意の行の和が1となる非負実数成分の正方行列である。
:'''左確率行列'''（{{Lang-en-short|left stochastic matrix|links=no}}）とは、任意の列の和が1となる非負実数成分の正方行列である。
:'''[[二重確率行列]]'''（{{Lang-en-short|doubly stochastic matrix|links=no}}）とは、任意の行、任意の列の和が1となる非負実数成分の正方行列である。

同様にして、'''{{仮リンク|確率ベクトル|en|stochastic vector}}'''（{{Lang-en-short|stochastic vector, probability vector|links=no}}） を、全ての成分が非負の実数で和が1となる[[数ベクトル|ベクトル]]と定義できる。右確率行列の全ての行（左確率行列の全ての列）は確率ベクトルである<ref name=Gagniuc2017/>{{rp|9-11}}。

数学の文献での慣習に従い、本項では行ベクトルが確率ベクトルとなる右確率行列について述べる<ref name=Gagniuc2017/>{{rp|1-8}}。

== 歴史 ==
[[File:Andrej Markov.jpg|thumb|アンドレイ・マルコフ（1886年）]]
確率行列は、[[ロシア人]][[数学者]]で[[サンクトペテルブルク大学]]教授であったアンドレイ・マルコフによってマルコフ連鎖とともに考案された。出版物への初めての記載は1906年である<ref name=Gagniuc2017/>{{rp|1-8}} <ref name=":0">{{cite journal | last1 = Hayes | first1 = Brian | year = 2013 | title = First links in the Markov chain | url = | journal = American Scientist | volume = 101 | issue = 2| pages = 92–96 }}</ref>。マルコフは当初、これらを言語分析や[[シャッフル (カード)|カードシャッフル]]等の数学的題材に用いるつもりだったが、たちまち他の分野でも有用であることが分かってきた<ref name=Gagniuc2017/>{{rp|1-8}} <ref name=":0" /><ref>''Charles Miller Grinstead; James Laurie Snell (1997). Introduction to Probability. American Mathematical Soc. pp. 464–466. {{ISBN2|978-0-8218-0749-1}}.''</ref>。

確率行列は[[アンドレイ・コルモゴロフ]]等の学者によってさらなる研究がなされ、連続時間マルコフ過程にも適用できるよう拡張が行われた<ref>{{cite journal | last1 = Kendall | first1 = D. G. | last2 = Batchelor | first2 = G. K. | last3 = Bingham | first3 = N. H. | last4 = Hayman | first4 = W. K. | last5 = Hyland | first5 = J. M. E. | last6 = Lorentz | first6 = G. G. | last7 = Moffatt | first7 = H. K. | last8 = Parry | first8 = W. | last9 = Razborov | first9 = A. A. | last10 = Robinson | first10 = C. A. | last11 = Whittle | first11 = P. | year = 1990 | title = Andrei Nikolaevich Kolmogorov (1903–1987) | url = | journal = Bulletin of the London Mathematical Society | volume = 22 | issue = 1| page = 33 | doi = 10.1112/blms/22.1.31 }}</ref>。1950年代までに、[[計量経済学]]<ref>{{Cite journal|last=Solow|first=Robert|date=1952-01-01|title=On the Structure of Linear Models|journal=Econometrica|volume=20|issue=1|pages=29–46|doi=10.2307/1907805|jstor=1907805}}</ref>や[[回路網解析]]<ref>{{Cite journal|last=Sittler|first=R.|date=1956-12-01|title=Systems Analysis of Discrete Markov Processes|url=http://ieeexplore.ieee.org/abstract/document/1086324/|journal=IRE Transactions on Circuit Theory|volume=3|issue=4|pages=257–266|doi=10.1109/TCT.1956.1086324|issn=0096-2007}}</ref>といった分野にも確率行列を用いた論文が現れた。1960年代には[[行動科学]]<ref>{{Cite journal|last=Evans|first=Selby|date=1967-07-01|title=Vargus 7: Computed patterns from markov processes|url=http://onlinelibrary.wiley.com/doi/10.1002/bs.3830120407/abstract|journal=Behavioral Science|language=en|volume=12|issue=4|pages=323–328|doi=10.1002/bs.3830120407|issn=1099-1743}}</ref>から[[地質学]]<ref>{{Cite journal|last=Gingerich|first=P. D.|date=1969-01-01|title=Markov analysis of cyclic alluvial sediments|url=http://archives.datapages.com/data/doi/10.1306/74D71C4E-2B21-11D7-8648000102C1865D|journal=Journal of Sedimentary Research|language=en-US|volume=39|issue=1|pages=330–332|doi=10.1306/74d71c4e-2b21-11d7-8648000102c1865d|issn=1527-1404}}</ref><ref>{{Cite journal|last=Krumbein|first=W. C.|last2=Dacey|first2=Michael F.|date=1969-03-01|title=Markov chains and embedded Markov chains in geology|url=https://link.springer.com/article/10.1007/BF02047072|journal=Journal of the International Association for Mathematical Geology|language=en|volume=1|issue=1|pages=79–96|doi=10.1007/BF02047072|issn=0020-5958}}</ref>、[[住宅地|居住地]]計画<ref>{{Cite journal|last=Wolfe|first=Harry B.|date=1967-05-01|title=Models for Conditioning Aging of Residential Structures|url=https://doi.org/10.1080/01944366708977915|journal=Journal of the American Institute of Planners|volume=33|issue=3|pages=192–196|doi=10.1080/01944366708977915|issn=0002-8991}}</ref>まで、さらに広範な科学領域で確率行列が用いられるようになった。同時に、この期間には確率行列や[[マルコフ過程]]の応用範囲や有用性を押し広げるような数学的研究もより一般的に行われた。

1970年代から現在にかけて、確率行列は[[建築構造設計]]<ref>{{Cite journal|url=http://www.sciencedirect.com/science/article/pii/0167473089900258|title=A Markov matrix for fatigue load simulation and rainflow range evaluation |language=en|access-date=2017-05-05|doi=10.1016/0167-4730(89)90025-8|volume=6|issue=2–4|journal=Structural Safety|pages=247–258 | last1 = Krenk | first1 = S.}}</ref>から[[診断|医療診断]]<ref>{{Cite journal|last=Beck|first=J.Robert|last2=Pauker|first2=Stephen G.|date=1983-12-01|title=The Markov Process in Medical Prognosis|url=https://doi.org/10.1177/0272989X8300300403|journal=Medical Decision Making|language=en|volume=3|issue=4|pages=419–458|doi=10.1177/0272989X8300300403|issn=0272-989X}}</ref>、[[人事労務管理]]<ref>{{Cite journal|last=Gotz|first=Glenn A.|last2=McCall|first2=John J.|date=1983-03-01|title=Sequential Analysis of the Stay/Leave Decision: U.S. Air Force Officers|url=http://pubsonline.informs.org/doi/abs/10.1287/mnsc.29.3.335|journal=Management Science|volume=29|issue=3|pages=335–351|doi=10.1287/mnsc.29.3.335|issn=0025-1909}}</ref>まで、形式的な分析を必要とするほとんどあらゆる分野で用いられるようになってきた。{{仮リンク|土地利用変化モデリング|en|land change modeling}}（land change modeling、この分野では「マルコフ行列」と呼ばれることが多い）においても広範に応用されている<ref>{{Cite journal|last=Kamusoko|first=Courage|last2=Aniya|first2=Masamu|last3=Adi|first3=Bongo|last4=Manjoro|first4=Munyaradzi|date=2009-07-01|title=Rural sustainability under threat in Zimbabwe – Simulation of future land use/cover changes in the Bindura district based on the Markov-cellular automata model|url=http://www.sciencedirect.com/science/article/pii/S0143622808000702|journal=Applied Geography|volume=29|issue=3|pages=435–447|doi=10.1016/j.apgeog.2008.10.002}}</ref>。

==定義と性質==
確率行列は、要素が[[有限集合|有限]]個の[[確率空間|状態空間]] ''S'' （[[濃度 (数学)|濃度]] <math>S</math> ）上のマルコフ連鎖 <math>\boldsymbol{X}_{t}</math> を記述する。

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

:<math>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]</math>

状態 <math>i</math> から次の状態へ遷移する確率の総和は1なので、

:<math>\sum_{j=1}^S P_{i,j}=1</math>

となり右確率行列であるための条件を満たす<ref name=Gagniuc2017/>{{rp|1-8}}。この性質を<math>P\mathbf{1}=\mathbf{1}</math> とも表せる<ref><math>P\mathbf{1}=\mathbf{1}</math>であることにより、確率行列 <math>P</math> は固有値を <math>1</math> ，固有ベクトルを <math>\mathbf{1}</math> とする固有空間を持つことが分かる。</ref>。ここで <math>\mathbf{1}</math> は全ての成分が <math>1</math> の <math>S</math> 次元列ベクトルである。
これを使うと、2つの確率行列 <math>P^\prime</math>, <math>P^{\prime\prime}</math> の[[行列の乗法|積]]もまた右確率的であることがわかる： <math>P^\prime P^{\prime\prime}\mathbf{1}=P^\prime(P^{\prime\prime} \mathbf{1})=P^\prime \mathbf{1}=\mathbf{1}</math>

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

:<math>\left(P ^{2}\right)_{i,j}</math>

に等しく、さらに一般に、ある状態から次の状態へ <math>k</math> ステップで遷移する確率は <math>P^k</math> で与えられる。

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

'''定常'''（{{Lang-en-short|stationary|links=no}}）確率ベクトル <math>\boldsymbol{\pi}</math> とは、右確率行列が右から作用しても不変な行確率ベクトルのことである。つまり、集合 <math>\{1, ..., n\}</math> 上の確率分布であって、左[[固有値]]1に対する左[[固有ベクトル]]となるもののことである：

:<math>\boldsymbol{\pi}P=\boldsymbol{\pi}</math>

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

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

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

一般に定常な確率ベクトルは複数存在するかもしれないが、確率行列の全ての成分が正であれば（より一般的には、確率行列が既約かつ非周期的（{{仮リンク|エルゴード的|en|ergodicity}}（{{Lang-en-short|ergodic|links=no}}））であれば）、このようなベクトルは一意的であり、任意の状態 <math>i</math> に対し次の極限をとることで計算できる。

:<math>\lim_{k\rightarrow\infty}\left(P^k \right)_{i,j}=\boldsymbol{\pi}_j</math>

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

直観的には確率行列はマルコフ連鎖を表し、（行ベクトルとしての）確率分布に右確率行列を右から作用させることは、元の分布の[[確率質量関数|確率質量]]を（総和1を保ちつつ）次の確率分布へ再分配することに相当する。この作用を反復していくとマルコフ連鎖の定常状態に収束する<ref name=Gagniuc2017/>{{rp|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)

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

:<math> 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}</math>

===長時間平均===

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

===相型分布としての表現===
[[Image:Mousesurvival.jpg|thumb|right|350px|ネズミの生存確率関数。少なくとも最初の1ステップでは生き残っている。]]

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

:<math>\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}</math>

また、

:<math>(I-T)^{-1}\boldsymbol{1} =\begin{bmatrix}2.75 \\ 4.5 \\ 3.5 \\ 2.75\end{bmatrix}</math>

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

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

:<math>E[K]=\boldsymbol{\tau} \left (I+T+T^2+\cdots \right )\boldsymbol{1}=\boldsymbol{\tau}(I-T)^{-1}\boldsymbol{1}=4.5</math>

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

:<math>E[K(K-1)\dots(K-n+1)]=n!\boldsymbol{\tau}(I-{T})^{-n}{T}^{n-1}\mathbf{1}</math>

で与えられる。

== 関連項目 ==
* {{仮リンク|ムーアヘッドの不等式|en|Muirhead's inequality}}
* [[ペロン＝フロベニウスの定理]]
* [[密度行列]]
* [[二重確率行列]]
* {{仮リンク|相型分布|en|phase-type distribution}}
* {{仮リンク|確率的オートマトン|en|Probabilistic automaton}}
* [[分子進化モデル]] （{{仮リンク|DNA進化のモデル|en|Models of DNA evolution}}）
* {{仮リンク|マルコフ核|en|Markov kernel}} （連続的な状態空間における確率行列の対応物）

==脚注==
{{Reflist}}

{{DEFAULTSORT:かくりつきようれつ}}
[[Category:行列]]
[[Category:確率論]]
[[Category:確率過程]]
[[Category:数学に関する記事]]