コンテンツにスキップ

確率行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』

確率行列(かくりつぎょうれつ、(英: stochastic matrix)は任意の行(あるいは列)の和が 1 となる非負実数成分の正方行列である[1][2]:9-11, [3]。遷移行列(英: transition matrix)、置換行列(英: substitution matrix)、マルコフ行列(英: Markov matrix)、英: probabilistic matrix とも[2]:9-11。

確率行列には複数の形式があり(⇒ #定義)、明記されない限り、本稿では数学の文献での慣習に従って右確率行列を採用する[2]:1-8。

概要

[編集]

確率行列はすべての行あるいは列が確率ベクトルである実正方行列である(⇒ #定義)。状態遷移を記述するのに良い性質を持っている(⇒ #性質)。20世紀初頭にアンドレイ・マルコフによって初めて導入され、確率論、統計学、数理ファイナンス、線形代数学、計算機科学、集団遺伝学といった様々な分野で活用されてきた(⇒ #歴史)[2]:1-8。有限状態マルコフ連鎖は確率行列を利用する典型例である(遷移確率行列)。

定義

[編集]

確率行列には複数の形式がある[2]:9-11, [3] 。右確率行列・左確率行列・二重確率行列が代表例であり[3]、前者ふたつをここで定義する。また、説明に必要な「確率ベクトル」もここで定義する。

右確率行列の定義

[編集]

右確率行列(みぎかくりつぎょうれつ、(英: right stochastic matrix)は任意の行の和が1となる非負実数成分の正方行列である[2]:9-11, [3]。

実正方行列 A=(aij)∈ℝN×N が次の条件、

  • ∀i,j∈{1,…,N};0≤aij≤1,
  • ∀i∈{1,…,N};∑j=1Naij=1,

を満たすとき、行列 A は右確率行列である。

全1ベクトル 1 と要素の大きさ制約 ≤ を用いれば、条件は「 0≤A≤1 ∧ A1=1」に集約される。

同義の別の言い方をするなら、右確率行列は「全ての行が確率ベクトルである実正方行列」である[2]:9-11, [3]。

左確率行列の定義

[編集]

左確率行列(ひだりかくりつぎょうれつ、(英: left stochastic matrix)は任意の列の和が1となる非負実数成分の正方行列である[2]:9-11, [3]。

実正方行列 A=(aij)∈ℝN×N が次の条件、

  • ∀i,j∈{1,…,N};0≤aij≤1,
  • ∀j∈{1,…,N};∑i=1Naij=1,

を満たすとき、A は左確率行列である。

同義の別の言い方をするなら、左確率行列は「全ての列が確率ベクトルである実正方行列」である[2]:9-11, [3]。

確率ベクトルの定義

[編集]

確率ベクトル(かくりつベクトル、(英: stochastic vector, probability vector) は全ての成分が非負の実数で和が1となるベクトルである。

実ベクトル 𝒂=(ai)∈ℝN が次の条件、

  • ∀i∈{1,…,N};0≤ai≤1,
  • ∑i=1Nai=1,

を満たすとき、𝒂 は確率ベクトルである。

歴史

[編集]
アンドレイ・マルコフ(1886年)

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

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

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

性質

[編集]

確率ベクトルの変換

[編集]

確率ベクトルに対して右から確率行列を作用させると確率ベクトルを(壊さずに)変換できる。

確率ベクトル 𝒑∈ℝ1×N と確率行列 A∈ℝN×N に対して、𝒑 に右から A を作用させたベクトル 𝒒=𝒑A を考える。確率行列と確率ベクトルの定義より A1=1, 𝒑1=1 であるため、𝒒 に右から 1 を作用させると 𝒒1=𝒑(A1)=𝒑1=1 となる。確率行列と確率ベクトルの定義より 0≤𝒑,A≤1 であり非負の積は非負・非負の和は非負であるため、0≤𝒒 である。また非負の和が 1 のとき各成分は 1 を超えないため 𝒒≤1 である。よって 𝒒 は 0≤𝒒≤1 ∧ 𝒒1=1 であり、𝒒 は確率ベクトルの定義を満たす。すなわち確率ベクトルに対して右から確率行列を作用させると確率ベクトルになる。これは確率行列が確率ベクトルを(壊さずに)変換していると解釈できる。

確率行列の変換

[編集]

確率行列に対して右から確率行列を作用させると確率行列を(壊さずに)変換できる[17]。

2 つの確率行列 A,B∈ℝN×N に対して、A に右から B を作用させた行列 C=AB を考える。確率行列の定義より A1=1, B1=1 であるため、C に右から 1 を作用させると C1=A(B1)=A1=1 となる。確率行列の定義より 0≤A,B≤1 であり非負の積は非負・非負の和は非負であるため、0≤C である。また非負の和が 1 のとき各成分は 1 を超えないため C≤1 である。よって C は 0≤C≤1 ∧ C1=1 であり、C は確率行列の定義を満たす。すなわち確率行列に対して右から確率行列を作用させると確率行列になる[17]。これは確率行列が確率行列を(壊さずに)変換していると解釈できる。

この特性より、同じ確率行列を k 回作用させる行列 Pk(行列の冪表示) もまた確率行列である。

固有値と固有ベクトル

[編集]

P𝟏=𝟏であることにより、確率行列 P は固有値を 1 ,固有ベクトルを 𝟏 とする固有空間を持つことが分かる。

マルコフ連鎖

[編集]

確率行列は有限状態マルコフ連鎖 𝑿t を記述する。

𝑿t の状態空間の濃度を S とする(有限状態マルコフ連鎖なので S は有限)。1ステップで状態 i から状態 j へ遷移する確率を Pr(j∣i)=Pi,j としたとき、行列 P を i行・j列成分が Pi,j の行列で以下のように与える:

P=[P1,1P1,2…P1,j…P1,SP2,1P2,2…P2,j…P2,S⋮⋮⋱⋮⋱⋮Pi,1Pi,2…Pi,j…Pi,S⋮⋮⋱⋮⋱⋮PS,1PS,2…PS,j…PS,S]

このとき状態 i から次の状態へ遷移する確率の総和は1なので ∀i∈{1,2…,S}, ∑j=1SPi,j=1 となり、かつ、Pi,j は確率なので 0≤Pi,j≤1 となるため、P は確率行列である(⇒ #右確率行列の定義)[2]:1-8。

状態 i から状態 j へ2ステップで遷移する確率は P2 の第 (i,j) 成分 (P2)i,j に等しく、さらに一般に、ある状態から次の状態へ k ステップで遷移する確率は Pk で与えられる。初期状態の確率分布(系がどのような状態をどのような確率でとっているか)は行ベクトルとして与えられる。

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

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

𝝅P=𝝅

定常確率ベクトルの存在

[編集]

確率行列は定常確率ベクトルを有する。

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

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

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

定常確率ベクトルへの収束

[編集]

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

limk→∞(Pk)i,j=𝝅j

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

直観的には、斉次有限状態マルコフ連鎖は初期状態に依らず確率行列の反復によって定常状態へ収束するといえる[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)

以下の行列 P で、このゲームの遷移確率を表す(行と列の番号は上記の状態の番号と対応する:行番号が遷移前の状態で、列番号が遷移後の状態[2]:1-8)。例えば状態 1 から始めたとすると、この状態に留まったり、状態 2、状態 4 に遷移することはできない( P11=0,P12=0,P14=0 )が、状態 3 または 5 への遷移は可能である( P13,P15≠0 )。

P=[001/201/2001001/41/401/41/4001/201/200001]

長時間平均

[編集]

初期状態がいずれであっても、ネコは最終的にはネズミを捕えて、定常状態 𝝅=(0,0,0,0,1)に到達する[2]:55–59。生存時間の平均(期待値)を計算するには、すべての状態 Sj と時間 tk についての寄与 Yj,kP(S=Sj,t=tk) を足しあげればよい。ここで Y は生存状態に対しては Yj,k=1、死亡状態に対しては Yj,k=0 の2値をとる変数である(Y=0は和に寄与しない)。

相型分布としての表現

[編集]
ネズミの生存確率関数。少なくとも最初の1ステップでは生き残っている。

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

𝝉=[0,1,0,0],T=[001200010141401400120]

また、

(I−T)−11=[2.754.53.52.75]

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

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

E[K]=𝝉(I+T+T2+⋯)1=𝝉(I−T)−11=4.5

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

E[K(K−1)…(K−n+1)]=n!𝝉(I−T)−nTn−1𝟏

で与えられる。

脚注

[編集]

注釈

[編集]

出典

[編集]
  1. ↑ Asmussen, S. R. (2003). “Markov Chains”. Applied Probability and Queues. Stochastic Modelling and Applied Probability. 51. pp. 3–8. doi:10.1007/0-387-21525-5_1. ISBN 978-0-387-00211-8
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Gagniuc, Paul A. (2017). Markov Chains: From Theory to Implementation and Experimentation. USA, NJ: John Wiley & Sons. pp. 9–11. ISBN 978-1-119-38755-8
  3. 1 2 3 4 5 6 7 遷移確率行列は、さらに行ごとの和が全て1の右確率行列 (Right Stochastic Matrix) と、列ごとの和が全て1となる左確率行列 (Left Stochastic Matrix) の2種類がある。... さらに、行・列の和がともに1となる行列、すなわち二重確率行列 (Doubly Stochastic Matrix)p.60 より引用。露崎, 弘毅 (2025). “行列・テンソル分解によるヘテロバイオデータ統合解析の数理 ―第7回 行列バランス化、最適輸送―”. JSBi Bioinformatics Review. 6 (2): 60–68. doi:10.11234/jsbibr.2025.5.
  4. 1 2 Hayes, Brian (2013). “First links in the Markov chain”. American Scientist 101 (2): 92–96.
  5. ↑ Charles Miller Grinstead; James Laurie Snell (1997). Introduction to Probability. American Mathematical Soc. pp. 464–466. ISBN 978-0-8218-0749-1.
  6. ↑ Kendall, D. G.; Batchelor, G. K.; Bingham, N. H.; Hayman, W. K.; Hyland, J. M. E.; Lorentz, G. G.; Moffatt, H. K.; Parry, W. et al. (1990). “Andrei Nikolaevich Kolmogorov (1903–1987)”. Bulletin of the London Mathematical Society 22 (1): 33. doi:10.1112/blms/22.1.31.
  7. ↑ Solow, Robert (1952-01-01). “On the Structure of Linear Models”. Econometrica 20 (1): 29–46. doi:10.2307/1907805. JSTOR 1907805.
  8. ↑ Sittler, R. (1956-12-01). “Systems Analysis of Discrete Markov Processes”. IRE Transactions on Circuit Theory 3 (4): 257–266. doi:10.1109/TCT.1956.1086324. ISSN 0096-2007.
  9. ↑ Evans, Selby (1967-07-01). “Vargus 7: Computed patterns from markov processes” (英語). Behavioral Science 12 (4): 323–328. doi:10.1002/bs.3830120407. ISSN 1099-1743.
  10. ↑ Gingerich, P. D. (1969-01-01). “Markov analysis of cyclic alluvial sediments” (英語). Journal of Sedimentary Research 39 (1): 330–332. doi:10.1306/74d71c4e-2b21-11d7-8648000102c1865d. ISSN 1527-1404.
  11. ↑ Krumbein, W. C.; Dacey, Michael F. (1969-03-01). “Markov chains and embedded Markov chains in geology” (英語). Journal of the International Association for Mathematical Geology 1 (1): 79–96. doi:10.1007/BF02047072. ISSN 0020-5958.
  12. ↑ Wolfe, Harry B. (1967-05-01). “Models for Conditioning Aging of Residential Structures”. Journal of the American Institute of Planners 33 (3): 192–196. doi:10.1080/01944366708977915. ISSN 0002-8991.
  13. ↑ Krenk, S.. “A Markov matrix for fatigue load simulation and rainflow range evaluation” (英語). Structural Safety 6 (2–4): 247–258. doi:10.1016/0167-4730(89)90025-8 2017年5月5日閲覧。.
  14. ↑ Beck, J.Robert; Pauker, Stephen G. (1983-12-01). “The Markov Process in Medical Prognosis” (英語). Medical Decision Making 3 (4): 419–458. doi:10.1177/0272989X8300300403. ISSN 0272-989X.
  15. ↑ Gotz, Glenn A.; McCall, John J. (1983-03-01). “Sequential Analysis of the Stay/Leave Decision: U.S. Air Force Officers”. Management Science 29 (3): 335–351. doi:10.1287/mnsc.29.3.335. ISSN 0025-1909.
  16. ↑ Kamusoko, Courage; Aniya, Masamu; Adi, Bongo; Manjoro, Munyaradzi (2009-07-01). “Rural sustainability under threat in Zimbabwe – Simulation of future land use/cover changes in the Bindura district based on the Markov-cellular automata model”. Applied Geography 29 (3): 435–447. doi:10.1016/j.apgeog.2008.10.002.
  17. 1 2 確率行列どうしの積は確率行列である 。p.68 より引用。永田, 聖二 (1987). “安定行列と価格 : Leontief-Sraffa体系における価 格の収束性” (PDF). 經濟學研究. 52 (6): 63–84.

関連項目

[編集]