PDF 測度論的確率論 2015 Kengo Kato

非負行列とマルコフ・チェインの収束

作成：加藤賢悟¹  非負行列とは成分がすべて非負実数の行列のことを指す．本ノートの目標は，非負行列 に関する基本的な定理であるPerron-Frobenius定理を証明することである．経済学にお

いては，Perron-Frobenius定理は産業連関分析に応用され，かつては大きな関心をもたれ

てたいたようである(二階堂 (1959)を参照せよ)．そのほかに，有限状態空間上の強既約 マルコフ・チェインの定常分布への収束の証明にも応用される．Perron-Frobenius定理は 最近になって，Googleが運営するPageRankの性能保証に応用されているが判明し，再 び脚光を浴びている印象である(Bryan and Leise (2006)を参照せよ)．

本論に入る前に，いくつかの定義を紹介する．既に述べたように，成分がすべて非負実 数の行列を 非負行列 と呼ぶ．行列Aが非負行列であることを，A ≥ Oと書く．また成 分がすべて正実数の行列を 正行列 と呼ぶ．Aが正行列であることを，A > Oと書く．非 負ベクトル，正ベクトルに関しても同様に定義する．同じサイズの行列A, Bに対して， A − B ≥ OならA ≥ B，A − B > OならA > Bと書く．数ベクトルに対しても同様の 記法を用いる．以下，とくに断らなければ，行列はすべてn次実正方行列とし，ベクトル は^Rnのベクトルとする．∥ · ∥を^Rnの標準ノルムとする：∥x∥²= x^tx．また1を並べた Rⁿ_{のベクトルを}1_と書く：1= (1, . . . , 1)^t.

Perron-Frobenius_定理

まず非負行列に対するPerron-Frobenius定理を証明する．

定理 ¹ (非負行列に対するPerron-Frobenius定理). 任意の非負正方行列Aに対して，次 の性質をみたす非負固有値λ(A)が存在する．

(1) λ(A)に属する固有ベクトルとして非負ベクトルをとれる．

(2) Aのそのほかの固有値の絶対値はλ(A)を超えない．

定理1のλ(A)をAのFrobenius根 と呼ぶ．一般に固有値の絶対値の最大値をスペクト ル半径と呼ぶが，(2)よりFrobenius根λ(A)はAのスペクトル半径に等しい．

定理 1の証明に移る．まず次の補題を示す．

補題 ^1. Aを非負正方行列とし，あるx≥ 0に対して，(I − A)x > 0とする．このとき (I − A)は正則であり，

(I − A)⁻¹ = I + A + A²+ · · ·

と展開できる．ただし，右辺は成分ごとの収束を意味する．とくに，(I − A)⁻¹≥ O.

1東京大学大学院経済学研究科．〒113-0033東京都文京区本郷7-3-1. E-mail: [email protected].

証明^. (I − A)x = yを書き直すと，

x= Ax + y = A(Ax + y) + y = A²x+ (I + A)y

= · · · = A^Nx+ (I + A + · · · + A^{N −1})

| {z }

=B^N

y

と展開できる．BN = (b^{(N )}_ij )とおくと，各(i, j)に対して，数列(b^{(N )}_ij )N ∈Nは単調非減少で あり，^∑n_j=1b^{(N )}_ij y_j ≤ x_i (i = 1, . . . , n)をみたす．yは正ベクトルより，b^{(N )}_ij はN に関し て有界なので，N → ∞のとき収束する：B_N → B. このとき(I − A)B_N = I − A^N → I より，(I − A)B = Iを得る．ゆえに(I − A)は正則であり，(I − A)⁻¹= B.

定理 ¹の証明^. 集合M (A) ⊂ (0, +∞)を

M (A) = {ρ > 0 : (ρI − A)は正則 & (ρI − A)⁻¹ ≥ O}

と定義すると，ρ > 0に対して(ρI − A)x > 0なるx ≥ 0が存在すれば，補題 1より ρ ∈ M (A)．逆に(ρI − A)⁻¹≥ Oなら，任意のy> 0に対してx= (ρI − A)⁻¹y≥ 0と おくと，(ρI − A)x = y > 0となる．ゆえに，ρ > 0に対して，

ρ ∈ M (A) ⇔ ∃x ≥ 0 s.t. (ρI − A)x > 0.

ここで，十分大きなρ > 0に対してはρ1 > A1となるから，M (A) ̸= ∅．そこで， λ = inf M (A)

とおいて，λがAのFrobenius根になることを示す．

ステップ ^1. まずM (A) = (λ, +∞)となることを示す．ρ ∈ M (A), µ > ρ なら， (ρI − A)x > 0なるx≥ 0に対して，(µI − A)x = (µ − ρ)x + (ρI − A)x > 0だから，µ ∈ M (A)．ゆえにM (A)は[λ, +∞)か(λ, +∞)のいずれかである．いま，仮にあるx≥ 0に対 して(λI − A)x > 0なら，λx ≥ (λI − A)x > 0より，x> 0となる．y= (λI − A)x (> 0) とおくと，0 < ϵ < min_1≤i≤ny_i/x_i(≤ λ)に対して，{(λ−ϵ)I −A}x = (λI −A)x−ϵx > 0 となるが，このときλ − ϵ ∈ M (A)となり，λの定義に反する．従って，λ /∈ M (A)だか ら，M (A) = (λ, +∞)を得る．

ステップ ^2. あるx≥ 0, x ̸= 0が存在して，Ax = λxとなることを示す．ρN ↓ λなる 数列ρ_N をとる．このとき(ρ_NI − A)⁻¹¹̸= 0より，

ϵ_N = 1/∥(ρ_NI − A)⁻¹¹∥, x_N = ϵ_N(ρ_NI − A)⁻¹¹

とおくと，x_N ≥ 0, ∥x_N∥ = 1, (ρ_NI − A)x_N = ϵ_N¹．ここで集合{x ∈ Rⁿ : ∥x∥ = 1} はコンパクトだから，Boltzano-Weierstrassの定理より，x_N は収束部分列x_Nk をもつ： x_Nk → x ≥ 0, ∥x∥ = 1. いま

(ρ_NkI − A)x_Nk = ϵ_Nk¹

の左辺の各成分はk → ∞のとき収束するので，ϵ_Nkも収束する：ϵ_Nk → ϵ. ゆえに (λI − A)x = ϵ1

が成り立つ．λ /∈ M (A)より，ϵ > 0はありえないので，(λI − A)x = 0を得る．

ステップ ^3. 最後に，µをAの任意の固有値としたとき，|µ| ≤ λを示す．zをµに 属する固有ベクトルとすると，Az = µzより，^∑n_k=1a_jk|z_k| ≥ |µ||z_j| (j = 1, . . . , n).

|z| = (|z1|, . . . , |zn|)^tとおくと，(|µ|I − A)|z| ≤ 0. このとき(|µ|I − A)は特異か，正 則だとしても(|µ|I − A)⁻¹ ≥ Oにはならない(∵ 仮に(|µ|I − A)⁻¹ ≥ Oなら，|z| = (|µ|I − A)⁻¹(|µ|I − A)|z| ≤ 0となり矛盾)．ゆえに|µ| /∈ M (A)より，|µ| ≤ λを得る．

Frobenius根はA^NのN → ∞のときの漸近挙動に関する閾値を与える．

系^1. ρ > λ(A)なら，N → ∞のとき，(A/ρ)^N → O. 一方，0 < ρ < λ(A)なら，(A/ρ)^N の成分のうち少なくとも1つは+∞に発散する．

証明^. ρ > λ(A)なら，(ρI − A)⁻¹= ρ⁻¹(I − ρ⁻¹A)⁻¹ ≥ O. ゆえに補題1をA/ρに適用 して，(A/ρ)^N → O．一方，0 < ρ < λ(A) = λなら，Ax = λxなるx≥ 0をとると，

A ρ^x=

λ ρ^x,

( A ρ

)N

x=^{( λ} ρ

)N

x.

(λ/ρ)^N → +∞より，(A/ρ)^N の成分のうち少なくとも1つは+∞に発散する． ρ = λ(A) = λのときは，(A/λ)^N は収束するとは限らない．例えば，

A = (0 1

1 0 )

とすると，Aの固有値は±1だから，そのFrobenius根は1であるが，N が奇数のとき A^N = A, Nが偶数のときA^N = I₂となるから，A^N はN → ∞とき収束しない．しかし ある正整数mに対してA^mが正行列になれば，(A/λ)^Nはある行列に収束する．その前に 正行列に対するPerron-Frobenius定理を証明する．

定理 ² (正行列に対するPerron-Frobenius定理). Aが正行列なら，λ = λ(A)に対して， 次の(1)–(4)が成り立つ：

(1) λ > 0.

(2) λに属する固有ベクトルとして，正ベクトルx> 0をとれる．

(3) Aのそのほかの固有値の絶対値はλより小さい．

(4) λに属する固有空間は1次元である．

証明^. (1). ρ > 0を十分小さくとると，(ρI − A)のある行の成分はすべて負になる．この とき任意のx≥ 0に対して，(ρI − A)xのその行に対応する成分は正になりえない．ゆえ にρ /∈ M (A)より，λ ≥ ρ > 0.

(2). x ≥ 0をλに属する非負固有ベクトルとすると，

x= ^Ax λ ^{> 0.}

(3). A^tはAと同じ固有値の組をもつ正行列であるから，λ(A^t) = λ(A)となる．y> 0 をλに属するA^tの正固有ベクトルとする．いま仮に|µ| = λなるAの固有値µが存在す るとして，µ = λを示す．zをµに属するAの固有ベクトルとする．|z| = (|z₁|, . . . , |z_n|)^t とおくと，|µ||z| ≤ A|z|より，

|µ|y^t|z| ≤ y^tA|z| = (Ay)^t|z| = λy^t|z|. (*) (*)の両辺は等号が成立して，y> 0より，|µ||z| = A|z|となる．さらに，A > Oである から，z1, . . . , znはすべて同じ偏角θをもつ：z = e^iθ|z|. w = e^−iθzとおくと，wはµに 属するAの非負固有ベクトルである：Aw = µw, w ≥ 0. ゆえに，

λy^tw= y^tAw = µy^tw. y> 0, w ≥ 0より，y^tw> 0だから，µ = λを得る．

(4). zをλに属する任意の固有ベクトルとする：Az = λz. w = x − czなるベクト ルを考えると，Aw = λwとなる．そこでcをwの1つの成分が0となり，かつw≥ 0 となるように選ぶ．仮にw̸= 0なら，wはλに属する固有ベクトルとなるが，このとき w= Aw/λ > 0となり，矛盾が生じる．ゆえにw= 0，すなわち，z= cx.

Aが正行列という仮定は緩めることができる．

系 ^2. A ≥ Oはある正整数mに対してA^m > Oをみたすとする．このときλ = λ(A)に 対して，定理 2の(1)–(4)が成り立つ．

証明^. λ(A^m) = λ^m > 0より，λ > 0．またx≥ 0をλに属するAの固有ベクトルとする と，Ax = λx, A^mx= λ^mx. ゆえにx= A^mx/λ^m > 0. 次にµをλとは異なるAの任意 の固有値とし，zをµに属する固有ベクトルとすると，Az = µz, A^mz= µ^mz. A^m > O より，|µ|^m = |µ^m| < λ^mだから，|µ| < λ. 最後にwをλに属する任意の固有ベクトルと すると，A^mw= λ^mw. いまA^m> Oよりwはxのスカラー倍になる．

定理 ^3. A ≥ Oはある正整数mに対してA^m > Oをみたすとする．またλ = λ(A)とお く．このとき次をみたす一意な正ベクトルの組x, y > 0が存在する：

Ax = λx, A^ty= λy, y^tx= 1, lim

N →∞

( A λ

)N

= xy^t.

証明^. (A^t)^m = (A^m)^tより，λに属するA^tの固有空間の次元は1である．ゆえにAx = λx, A^ty = λy, y^tx = 1をみたす正ベクトルの組x, y > 0が一意に存在する．あとは lim_{N →∞}(A/λ)^N = xy^tを示せばよい．

まずm = 1とする．このときA > Oだから，c > 0を十分小さく選んで，A_c = A−cxy^t> Oとできる．すると(λI − A_c)x = {(λI − A) + cxy^t}x = cx > 0より，λ > λ(A_c). ゆ

えに ( Ac

λ )N

→ O.

いまB = A − λxy^tとおくと，B² = (A − λxy^t)(A − λxy^t) = A²− λ(xy^tA + Axy^t) + λ²x(y^tx)y^t= A²−λ²xy^t. 帰納的にB^N = A^N−λ^Nxy^tを得る．一方，B = A_c−(λ−c)xy^t とも表せて，A_cx= (λ − c)x, A^t_cy= (λ − c)yを用いると，B^N = A^N_c − (λ − c)^Nxy^tと なる．ゆえに

( B λ

)N

=^{( Ac} λ

)N

−^{( λ − c} λ

)N

xy^t→ O

より， ( A

λ )N

=^{( B} λ

)N

+ xy^t→ xy^t を得る．

mが一般の正整数のときは，λ(A^m) = λ^m, A^mx = λ^mx, (A^m)^ty = λ^my より， (A^m/λ^m)^N → xy^tが成り立つ．Nをmで割った商をq_N，余りをr_N とおくと，

( A λ

)N

=^{( A}

m

λ^m )qN

×^{( A} λ

)rN

.

ここで，(A^m/λ^m)^qN → xy^tより，∆_N = (A^m/λ^m)^qN − xy^tとおくと，(A^m/λ^m)^qN = xy^t+ ∆_N, ∆_N → O. 一方，0 ≤ r_N ≤ k − 1だから，∆_N(A/λ)^rN → O. ゆえに

( A λ

)N

= xy^t×^A

rN

λ^{rN + ∆N} ( A

λ )rN

= xy^t+ ∆N^{( A}

λ )rN

→ xy^t を得る．

マルコフ・チェイン

Perron-Frobenius定理の応用として，強既約マルコフ・チェインの定常分布への収束を

証明する．n次非負正方行列P = (p_ij)が 確率行列 (stochastic matrix)であるとは，

∑n j=1

pij = 1, i = 1, . . . , n

が成り立つことを言う．確率行列Pに対して，{1, . . . , n}に値をとる確率変数列X₀, X₁, . . . , X_N, . . . が推移行列P をもつ マルコフ・チェイン(Markov chain)であるとは，

P_{(XN +1= j | XN = iN}, . . . , X₀= i₀)

= P(X_{N +1}= j | X_N = i_N) = p_iN_j, ∀i₀, , . . . , i_N, j ∈ {1, . . . , n}; ∀N = 0, 1, 2, . . . が成り立つことを言う．マルコフ・チェインは一期先の値が現在の値 のみ に依存して確 率的に決まる数学モデルである．本ノートではマルコフ・チェインのいろいろな例や一般 論を紹介する余裕はないので，これらのことに関心がある場合は，適当な文献(例えば， Billingsley (1995)のSection 1.8)を参照すること．

マルコフ・チェイン(X_N)に対して，初期値X₀の分布を 初期分布(initial distribution) と呼ぶ．X0は{1, . . . , n}に値をとるので，X0の分布は^Rnのベクトル

ν = (ν1, . . . , νn)^t= (P(X0 = 1), P(X0= 2), . . . , P(X0= n))^t と同一視できて，νは

ν ≥ 0, ν^t1= 1 (1)

をみたす．(1)をみたすベクトルを 確率ベクトル (stochastic vector)と呼ぶ．初期分布が 決まると，X_N の分布は

P_{(XN = j) =} ^∑

iN

−¹

P_{(XN = j | XN −1= iN −1)P(XN −1= iN −1)}

= ^∑

i^N₋1,i^m₋²

P_{(XN = j | XN −1= iN −1)P(XN −1| Xm−2 = im−2)P(Xm−2= im−2)}

= · · · = ^∑

iN

−^1,...,i1,i0

P_{(XN = j | XN −1= iN −1}) · · · P(X₁ = i₁| X₀ = i₀)P(X₀ = i₀)

= ^∑

iN

−^1,...,i1,i0

p_iN₋1j^{· · · p}i0i1ν_i0 = ^∑

i0,i1,...,iN

−¹

ν_i0p_i0i1· · · p_iN₋1j

と計算できる．最右辺はν^tP^N の第j行だから，N → ∞のときのX_Nの挙動を調べるに

は，P^NのN → ∞のときの挙動を調べればよい．なお，任意の確率ベクトルと確率行列

に対して，それらを初期分布と推移行列にもつマルコフ・チェインの存在が知られている (Billingsley, 1995, Theorem 8.1)．

確率ベクトルπがP の 定常分布 (stationary distribution)であるとは， π^tP = π^t

が成り立つことを言う．推移行列が定常分布πをもつとき，πをマルコフ・チェインの定 常分布と呼ぶ．また確率行列P が 強既約(strongly irreducible)であるとは，ある正整数 mに対して，P^m > Oとなることを言う．推移行列が強既約なとき，マルコフ・チェイン を強既約と呼ぶ．

定理 ^4. 強既約な確率行列P = (p_ij)に対して，一意な定常分布π= (π_i) > 0が存在して， N → ∞のとき，

P^N → 1π^t (*)

が成り立つ．さらに(*)の収束は指数的に速い：ある0 < c ≤ 1が存在して，

1≤i,j≤nmax ^|(P

N₎

ij^{− π}j| ≤ (1 − c)^⌊N/m⌋, ∀N ≥ m (*2) が成り立つ．ただし，⌊a⌋はaを超えない最大の整数である．

証明^. Pは確率行列だから，P 1 = 1より，固有値1とそれに属する固有ベクトル¹をも つ．さらにP の任意の固有値µに対して，µに属する固有ベクトルをx = (x₁, . . . , x_n)^t として，P x = µxの第i行を比較すると，

|µ| · |x_i| ≤

∑n j=1

p_ij|x_j| ≤ max

1≤j≤n^|xj|

∑n j=1

p_ij = max

1≤j≤n^|xj|.

左辺を1 ≤ i ≤ nに関して最大値をとって，|µ| ≤ 1を得る．ゆえにP のFrobenius根は 1であるから，定理3より，一意な定常分布π > 0の存在と収束(*)が従う．次に(*2)を 示す．P^∞= 1π^tとおくと，π > 0よりP^∞> Oである．

P P^∞= P 1π^t= 1π^t= P^∞, P^∞P = 1π^tP = 1π^t= P^∞ に注意する．いま

c = min

1≤i,j≤n^(P m₎

ij^/(P∞)ij ^{> 0}

とおくと，(P^m)_ij ≥ c(P^∞)_ij (∀i, j)であり，jに関して和をとると，c ≤ 1である．c = 1な らP^m = P^∞であり，このとき任意のN ≥ mに対して，P^N = P^{N −m}P^m= P^{N −m}P^∞= P^∞となる．ゆえにc < 1の場合を考える．ここで

Q = ¹ 1 − c^(P

m_{− cP}∞₎

とおくと，Qも確率行列であり，QP^∞= P^∞Q = P^∞をみたす．このとき(Q − P^∞)^N = Q^N − P^∞となるから，左辺の成分の絶対値はすべて1以下である．さらに

P^m− P^∞= (1 − c)(Q − P^∞),

P^{N m}− P^∞= (P^m− P^∞)^N = (1 − c)^N(Q − P^∞)^N であるから，

1≤i,j≤nmax ^|(P

N m₎

ij^{− (P∞)}ij| ≤ (1 − c)^N

を得る．行列A = (a_ij)に対して，∥A∥_∞ = max_i,j|a_ij|と定めると，P^{N +1}− P^∞ = P (P^N − P^∞)なる関係より，

(P^{N +1}− P^∞)_ij =^∑

k

p_ik(P^N − P^∞)_kj ≤ (

∑

k

p_ik )

∥P^N − P^∞∥_∞= ∥P^N − P^∞∥_∞.

ゆえに，

N 7→ ∥P^N − P^∞∥∞

は単調非増加であるから，∥P^N − P^∞∥∞≤ (1 − c)^⌊N/m⌋を得る．

定理4の意味を述べる．(X_N)を初期分布ν，推移行列Pをもつマルコフ・チェインとす ると，X_Nの分布は^Rnの横ベクトルと同一視すると，ν^tP^Nである．いまマルコフ・チェ インが強既約なら，一意な定常分布πが存在して，N → ∞のとき，

ν^tP^N → ν^t1π^t= π^t

となる．πはνによらず決まるから，これは初期分布に関わらずX_Nの分布が定常分布π に収束することを意味する．さらにその収束は指数的に速い：

1≤j≤nmax ^{|P(XN = j) − πj}| ≤ (1 − c)^⌊N/m⌋, N ≥ m.

もちろん具体的なマルコフ・チェインに対しては，定数cの値も重要になってくるが，そ の精密な評価にはまったく異なったテクニックが必要である．詳細はSaloff-Coste (1997) を参照せよ．なお(*2)の証明はSaloff-Coste (1997, Theorem 2.1)の証明を参考にした．

コメント

非負行列をカバーしてるいる線形代数の教科書はそれなりにある．例えば，斎藤(1966)， 竹内(1966)，Horn and Johnson (1990)，室田・杉原 (2013)などである．そのほかだと， 二階堂(1959, 1961)が非負行列を詳細に扱っている．Perron-Frobenius定理の経済学にお ける意義に関しては二階堂(1959)が参考になる．本ノートの前半部分は竹内 (1966)を参 考にした．

なお，定理2はより一般に既約な非負行列に対して成り立つ．既約性の定義はいくつか あるが，非負正方行列Aが既約であるとは，各(i, j)に対して，ある正整数mが存在して， (A^m)_ij > 0となることを言う．mは(i, j)に依存してよい．定理 2の直前に現れる行列の 例は，既約であるが，A^m> Oとなるmは存在しない(従って，既約なだけでは定理3は 成り立たない)．ただ議論が複雑になるのを避けるために，既約な場合のPerron-Frobenius 定理は扱わなかった．詳細は前述の参考文献を参照されたい．

参考文献

Billingsley, P. (1995). Probability and Measures (3rd edition). Wiley.

Bryan, C. and Leise, T. (2006). The 25,000,000,000 eigenvector: the linear algebra behind Google. SIAM Review 48 569–581.

Horn, R.A. and Johnson, C.R. (1990). Matrix Analysis. Cambridge University Press. Saloff-Coste, L. (1997). Lectures on finite Markov chains. In: ´Ecole d’ ´Et´e de Probabilit´es

de Saint-Flour XXVI (Lecture Notes in Mathematics 1665), Springer, 301–413. 斎藤正彦．(1966)．「線型代数入門」．東京大学出版会．

竹内啓．(1966)．「線形数学」．培風館．

二階堂副包．(1959)．「現代経済学の数学的方法」．岩波書店． 二階堂副包．(1961)．「経済のための線型代数」．培風館． 室田一雄・杉原正顯．(2013)．「線形代数II」．丸善出版．