Fundamental Theorem of Markov Chains (1)

시작하기 앞서 Markov chain을 처음 들어보는 사람들을 위해 이를 간단하게 설명하고자 한다.

 

Markov chain은 시간이 흐르면서 변화가 어떻게 이루어지는 지에 대한 확률 과정인 stochastic process의 특수한 경우이다. 이때 Markov chain에서의 시간의 변화는 이산적이다. 예를 들어 동전을 계속 던지는 게임을 한다고 생각하자. 동전을 한 번 던지는 것을 한 라운드로 생각한다면, 여기서의 시간의 변화는 라운드의 변화로 생각할 수 있다. 즉 $t$ 시점에서 $t+1$ 시점으로 가는 것을 $t$ 라운드에서 $t+1$ 라운드로 가는 것으로 생각할 수 있다는 것이다.

 

여기서 "변화"라는 것은 Markov chain의 용어로 설명하자면 "어떤 상태(state)에서 어떤 상태로 이동"하는 것이다. 즉 Markov chain은 시점(라운드)이 바뀜에 따라 현재의 state에서 다른 state로 이동할 확률에 대한 것이다. 여기에서 중요한 성질이 하나 더 있다. 바로 이 변화 확률이 현재 시점의 state에만 의존한다는 것이다. 수식적으로 표현해보자. $X_t$를 $t$ 시점에 위치할 state에 대한 확률 변수라고 한다면, $X_{t+1}$는 $X_t$에만 의존하는 것이다.

$$Pr[X_{t+1}=j|X_0=i_0,X_1=i_1,...,X_t=i]=Pr[X_{t+1}=j|X_t=i]$$

즉, 이제까지 거쳐온 state의 기록이 $i_0\to i_1\to ...\to i$일 때 그다음에 위치할 state가 $j$인 확률은 마지막 시점인 $t$ 시점에 있었던 state 정보에만 의존하는 것이다. 우리는 이러한 성질을 memoryless하다고 부를 것이다. 이 성질 덕분에 Markov chain은 하나의 matrix $P$로 표현할 수 있다. 위 수식을 $P_{ij}$라고 하자.

$$P_{ij}=Pr[X_{t+1}=j|X_t=i]$$

$P_{ij}$의 뜻은 state $i$에 있을 때 다음 시점에 state $j$로 갈 확률이다. 따라서 모든 state $i,j$에 대해서 다음을 만족해야 한다.

$$0\le P_{ij}\le 1,\sum _j{P}_{ij}=1$$

종종 이 matrix $P$를 Markov chain 그 자체를 나타낼 때 사용할 것이다. 또한 $P$를 directed graph로 나타낼 수 있다. 각 state를 vertex로 두고, $P_{ij}$가 0보다 크면 $i$에서 $j$로 가는 directed edge를 만들고 그것의 weight를 $P_{ij}$로 두는 것이다. 그러면 모든 edge의 weight는 0보다 클 것이고 모든 vertex에 대해서 그것에서 나가는 edge들의 weight를 합하면 1이 될 것이다.)

Markov Chain의 간단한 예시

 

 

---

이제 Fundamental Theorem of Markov Chain을 위한 설명을 하고자 한다.

 

우리는 finite한 state 수를 가지는 Markov chain에 대해서만 생각할 것이다. Markov chain의 state 수는 무한히 많을 수 있는데, 가령 동전 던지기를 계속하는 게임에서 "이제까지 앞면이 나온 수"를 state로 표현한다면 state 수는 무한히 많을 수 있다. 따라서 Markov chain의 엄밀한 정의에서는 state 수가 countably infinite하다는 것도 포함되어 있다. 어쨌든, Markov chain의 state의 수를 $n$이라고 하자. 이때 위치한 state에 대한 초기 분포를 나타내는 $n$ 크기의 (column) vector ${\mu }_0$를 만들고자 한다. 즉, 시작할 때 ${\mu }_0(i)$의 확률로 state $i$에 위치하는 것이다. 우리는 ${\mu }_0$가 주어졌을 때, 그다음 시점에서의 위치할 state에 대한 분포 ${\mu }_1$을 계산할 수 있다.

$${\mu }_1^T={\mu }_0^T\cdot P$$

그러면 그 다음 시점에서의 분포 ${\mu }_2$는 어떻게 될까?

$${\mu }_2^T={\mu }_1^T\cdot P={\mu }_0^T\cdot P^2$$

가 된다. 자연스럽게 초기 분포가 ${\mu }_0$이라면 $t$ 시점에서의 분포 ${\mu }_t$는

$${\mu }_t^T={\mu }_0^T\cdot P^t$$

가 될 것이다.

 

여기서 논의 진행을 위해 정의를 하나 하도록 하겠다.

Definition. Stationary Distribution

---

만약 state 분포 $\pi$가 시간이 흘러도 변하지 않는다면, $\pi$는 Markov chain $P$의 stationary distribution이다. 즉, $P$의 stationary distribution $\pi$는 ${\pi }^T={\pi }^T\cdot P$를 만족한다.

갑자기 왜 stationary distribution에 관심을 갖는지 말하기 위해 Markov Chain Monte Carlo 기법을 소개하고자 한다. 이는 sampling을 해야 하는 타겟 분포 $\pi$가 주어졌을 때, Markov chain 만들어서 sampling을 하겠다는 기법이다. 더 자세히 설명하자면 이렇다.

 

Markov Chain Monte Carlo

1. Stationary distribution이 $\pi$인 Markov chain을 만든다.

2. 이 Markov chain을 적당히 많이 수행시키고 그때의 state를 출력한다.

 

우리는 이 Markov chain이 충분히 큰 (모든) $t$에 대해서 $t$ 시점 이후의 state 분포가 $\pi$와 "크게 다르지 않기를"  바라고 있다. 즉, 충분히 큰 $t$에 대해서

$${\mu }_t^T\approx {\mu }_{t+1}^T\approx \cdots \approx \pi$$

이기를 바라는 것이다. 그래야지 수행이 끝났을 때의 state를 $\pi$에서 sampling한 결과라고 말할 수 있는 것이다.

 

그래서 Markov Chain Monte Carlo 기법과 관련해서 자연스러운 질문 중 하나는 다음과 같다. 어떤 분포가 주어졌을 때 그것을 stationary distribution으로 갖는 Markov chain을 만들 수 있는가? 이 질문에 대한 답은 다음 기회에 하는 것으로 하고, 우리는 이 질문의 (일종의) 역에 대해 답해보고자 한다.

 

과연 finite state space를 가지는 모든 Markov chain은
stationary distribution을 가질까?

 

이 질문에 대한 답을 시작하기 앞서 정답을 모르는 분들은 찍어보시길 바란다. 선택지를 좁혀보자면 (1) 그렇다 (2) 특정 조건에서만 그렇다 가 될 것이다.

 

일단 notaion부터 소개하도록 하겠다. 어떤 행렬 $A$가 주어졌을 때, $A>\mathbf{0}$이라고 적으면 모든 entry가 $0$보다 크다는 뜻이다. 이 정의는 $\ge$에 대해서도 적용 가능하다. 그리고 벡터 $x$와 행렬  $A$에 대해서 $|x|,|A|$라고 적으면 각각 $x$와 $A$의 모든 entry가 절댓값으로 바뀐 것을 뜻한다. 어떤 벡터 $x$의 infinity norm $||x|{|}_{\mathrm{\infty }}$는 $x$에서 절댓값이 가장 큰 원소를 의미하고 행렬 $A$의 infinity norm $||A|{|}_{\mathrm{\infty }}$은 row vector 중에서 그것의 entry의 합이 가장 큰 row를 $i^{\ast }$라고 했을 때 $i^{\ast }$번째 row에 있는 entry들의 합 $\sum _j{A}_{i^{\ast }j}$을 의미한다. 정방 행렬 $A$의 spectral radius $\rho (A)$는 $A$의 eigenvalue들의 절댓값의 최댓값, 즉 $max\{|{\lambda }_1|,...,|{\lambda }_n|\}$이다. (Eigenvalue $\lambda$와 eigenvector $x$는 $Ax=\lambda x$를 만족한다.)

 

이제 질문의 답에 아주 유용한 정보를 주는 정리를 소개하도록 하겠다. 이는 바로 행렬 이론에서 유명한 것으로 추정되는 Perron-Frobenius 정리이다.

Perron-Frobenius Theorem.

---

Each nonnegative matrix $A\ge \mathbf{0}$ has a nonnegative real eigenvalue with $\rho (A)=a$, and
$a$ has a corresponding nonnegative eigenvector.

 

갑자기 eigenvector, eigenvalue? 조금만 생각해보면 왜 이것에 관심을 가지는지 알 수 있다. Stationary distribution은 ${\pi }^{T}P={\pi }^T$를 만족함을 기억하자. 양 변에 transpose를 취하면 $P^T\pi =\pi$이다. 따라서 우리의 문제는 $P^T$ 행렬에 대해서 eigenvalue 1에 해당하는 nonnegative eigenvector가 존재함을 보이는 문제로 환원할 수 있다.

 

Perron-Frobenius 정리의 증명은 나중에 하고 이를 이용해 질문의 답을 먼저 해보도록 하겠다. 흐름은 다음과 같다.

[Step 1] 1은 $P$가 가질 수 있는 eigenvalue의 절댓값의 최댓값이다.

[Step 2] $P$는 값이 1인 eigenvalue를 가진다.

[Step 3] $P$와 $P^T$의 eigenvalue들은 동일하다.

[Step 4] $P^T\ge 0$이고 $\rho (P^T)=1$이다. Perron-Frobenius 정리에 의해 eigenvalue 1에 해당하는 nonnegative eigenvector ${\pi }^{\prime }$가 존재한다.

[Step 5] $\pi :={\pi }^{\prime }/||{\pi }^{\prime }|{|}_1$는 stationary distribution이다.

 

즉, finite Markov chain은 항상 stationary distribution을 가진다는 것이다!

이제 각 스텝이 성립함을 보이도록 하자.

 

[Step 1]

우리는 nonnegative matrix $A$가 있을 때 그것의 모든 eigenvalue의 절댓값이 $||A|{|}_{\mathrm{\infty }}$, 즉 $A$의 row vector 중에서 그것의 entry의 합이 가장 큰 row를 $i^{\ast }$라고 했을 때 $\sum _j{A}_{i^{\ast }j}$보다 작거나 같음을 알 수 있다. 이것은 다음 수식으로 간단히 보일 수 있다.

$$||\lambda x|{|}_{\mathrm{\infty }}=||Ax|{|}_{\mathrm{\infty }}=\sum _j{A}_{i^{\ast }j}{x}_j\le \sum _j{A}_{i^{\ast }j}||x|{|}_{\mathrm{\infty }}\le ||A|{|}_{\mathrm{\infty }}||x|{|}_{\mathrm{\infty }}$$

여기서 $|\lambda |\cdot ||x|{|}_{\mathrm{\infty }}=||\lambda x|{|}_{\mathrm{\infty }}$라는 것과 $x$가 eigenvector라는 것에서 오는 $||x|{|}_{\mathrm{\infty }}>0$를 이용한다면 $|\lambda |\le ||A|{|}_{\mathrm{\infty }}$를 보일 수 있다. 우리가 다루고 있는 matrix $P$는 stochastic matrix, 즉 모든 row vector의 entry들의 sum이 1인 matrix이다. 따라서 $P$의 eigenvalue는 $||P|{|}_{\mathrm{\infty }}=1$을 넘을 수 없다.

 

[Step 2]

간단하다. $v$를 모든 entry가 1인 크기 $n$짜리 벡터라고 하자. (즉, $v=\mathbf{1}$.) $P$가 stocastic matrix이므로 $Pv=v$가 성립한다. 즉 $P$는 eigenvalue 1을 갖는다.

 

[Step 3]

Characteristic polynomial을 소개하도록 하겠다. 어떤 matrix $A$의 characteristic polynomial $p_A(\lambda )$는 다음과 같이 정의된다.

$$p_A(\lambda ):=det(A-\lambda I_n)$$

우리는 어떤 ${\lambda }^{\prime }$가 $A$의 eigenvalue라는 조건과 $p_A({\lambda }^{\prime })=0$인 조건이 동치임을 알 수 있다.

$$p_A({\lambda }^{\prime })=det(A-{\lambda }^{\prime }{I}_n)=0⟺(A-{\lambda }^{\prime }{I}_n)\text{ is not invertible}$$

$$⟺(A-{\lambda }^{\prime }{I}_n)x=0\text{ has a nontrival solution}$$

$$⟺{\lambda }^{\prime }\text{ is an eigenvalue of }A$$

우리는 $P$와 $P^T$의 determinant가 같음을 통해 characteristic polynomial도 같음을 알 수 있다.

$$det(A-\lambda I_n)=det((A-\lambda I_n{)}^T)=det(A^T-\lambda I_n)$$

 

[Step 4, 5]

Perron-Frobenius 정리가 맞다는 가정하에 두 스텝은 자명하다. 마지막에 ${\pi }^{\prime }$를 그것의 ${\ell }_1$-norm으로 나눠주는 것은 entry의 합이 1이 되도록, 즉 distribution이 되도록 scaling을 해주는 것이다.

 

Fundamental Theorem of Markov Chains

Finite state space를 가지는 Markov chain이 stationary distribution을 가짐을 보였다. 그러면 그것은 unique 할까? Unique하다면 임의의 시작 분포 ${\mu }_0$에서 시작하더라도 적당히 큰 $t$에 대해서 ${\mu }_t$는 (unique한) stationary distribution으로 수렴할까? 해당 질문들에 답을 해주는 것이 Fundamental Theorem of Markov Chains이다.

Fundamental Theorem of Markov Chains

---

If a finite Markov chain is irreducible and aperiodic, then it has a unique stationary distribution $\pi$. Moreoever, for any distribution $\mu$,
$$\underset{t\to \mathrm{\infty }}{lim}{\mu }^T{P}^t={\pi }^T.$$

어떤 Markov chain이 irreducible 하거나 aperiodic 하다는 것을 정의하지 않았다. 다만 이것이 뭔지 모르더라도, "특정" 조건을 만족한다면 stationary distribution이 unique하고, 심지어 임의의 분포에서 시작하더라도 stationary distribution으로 수렴한다고 말하고 있다. 정의와 증명은 다음 글에서 하는 것으로 하고 여기서는 미뤄뒀던 Perron-Frobenius 정리를 증명하는 것으로 마무리하고자 한다.

 

Proof of Perron-Frobenius Theorem

이 증명을 위해 우선 nonnegativity가 positivity로 바뀐 버전에 대해 성립함을 보이고자 한다.

Perron-Frobenius Theorem for Positive Matrices

---

Each positive matrix $A>\mathbf{0}$ has a positive real eigenvalue with $\rho (A)=a$, and
$a$ has a corresponding positive eigenvector.

proof. 우선 $\rho (A)>0$임을 보이고자 한다. 만약 $\rho (A)=0$이었다면, 모든 eigenvalue들은 0이었다는 뜻이다. 따라서 $A$의 characteristic polynomial $p_A(\lambda )$을 적어보면 ${\lambda }^n$가 된다. 기존의 characteristic polynomial의 $\lambda$ 자리에는 constant가 들어갔는데 정의를 확장해서 matrix도 input으로 들어갈 수 있다고 하자. 그럼 함수의 output도 matrix가 될 것이다. $\lambda$ 자리에 $A$를 집어넣어보자. $p_A(A)=A^n$이 될 것이다.

 

이제 진짜 유명한 선형 대수의 정리를 하나 소개하겠다. (이것의 증명은 생략하도록 하겠다. 위키피디아 참고)

Cayley-Hamilton Theorem.   
$$p_A(A)=\mathbf{0}.$$

 

즉, 모든 정방 행렬에 대해서 그것의 characteristic polynomial에 자기 자신을 집어넣으면 zero matrix가 된다는 것이다. 따라서, 우리의 경우 $A^n=\mathbf{0}$가 성립하는 것이다. 그런데 $A>\mathbf{0}$을 만족하면서 $A^n=\mathbf{0}$을 만족할 수 있을까? 아니다. 이는 모순이고, 따라서 $\rho (A)>0$이 성립한다.

 

이제 $\lambda$를 $|\lambda |=\rho (A)$를 만족하는 $A$의 eigenvalue라고 하자. 우리는 $|\lambda ||x|=A|x|$임을 보일 것이다. 그러면 $\rho (A)$에 해당하는 positive eigenvector가 있음을 보인 것이기 때문이다. 우선 모든 index에 대해서 $|\lambda ||x|$의 entry가 $A|x|$의 entry보다 클 수 없음을 쉽게 볼 수 있다.

$$|\lambda ||x|=|\lambda x|=|Ax|\le A|x|$$

(수식에 등장하는 항들이 벡터임을 기억하자. 부등식은 모든 index에 대해 부등호가 성립함을 나타낸다.) 따라서 $|\lambda ||x|<A|x|$가 불가능함을 보이면 증명이 끝난다. 해당 부등식의 우변인 $A|x|$를 $z$라고 하자. 그리고 해당 부등식에서 우변과 좌변의 차이인 $A|x|-|\lambda ||x|$를 $y$라고 하자.

 

모순을 가정해서 $y>\mathbf{0}$이라고 하자. $A>\mathbf{0}$이기 때문에 $Ay>\mathbf{0}$가 성립한다. $z>\mathbf{0}$이 성립하므로 아주 작은 $ϵ$에 대해서 $Ay>ϵ\lambda z$가 성립한다. (혹은 이 조건을 만족하는 어떤 $ϵ$이 존재한다.) $y$ 자리에 원래 식을 대입해서 정리하면 다음과 같아진다.

$$\frac{A}{(1+ϵ)\lambda }z>z$$

양 변에 $\frac{A}{(1+ϵ)\lambda }$를 계속 곱해서 부등식을 여러 개 만들고 이들을 합치면

$$\cdots >{\left(\frac{A}{(1+ϵ)\lambda }\right)}^{k}z>\cdots >\frac{A}{(1+ϵ)\lambda }z>z$$

가 된다.

 

이제 spectral radius에 관한 정리를 하나 소개하고자 한다. (증명은 위키피디아 참고)

Theorem (The convergence of the power sequence of a matrix).
$$\rho (A)<1⟺\underset{k\to \mathrm{\infty }}{lim}{A}^k=0$$

 

$A^{\prime }:={\displaystyle \frac{A}{(1+ϵ)\lambda }}$라고 하자. 그러면 $A^{\prime }$의 spectral radius은 다음과 같다.

$$\rho (A^{\prime })=\frac{\rho (A)}{(1+ϵ)\rho (A)}<1$$

따라서 우리는 위의 정리를 적용해서 다음의 결론을 낼 수 있다.

$$\underset{k\to \mathrm{\infty }}{lim}{\left(A^{\prime }\right)}^k=\underset{k\to \mathrm{\infty }}{lim}{\left(\frac{A}{(1+ϵ)\lambda }\right)}^k=0$$

이것은 $\mathbf{0}>\cdot >z$임을 뜻하는데, $z>\mathbf{0}$와 모순이다. 따라서 $y=\mathbf{0}$이다. ■

 

이제 본 증명을 하고자 한다. 그전에 Gelfand's formula를 소개하고자 한다.

Theorem (Gelfand's formula)
For any sub-multiplicative matrix norm $||\cdot ||$,
$$\rho (A)=\underset{k\to \mathrm{\infty }}{lim}||A^k|{|}^{\frac{1}{k}}$$

proof sketch. 우리는 이 formula를 infinity norm에 대해서만 적용할 것이므로, sub-multiplicative norm을 infinity norm으로 생각해도 좋다.

Matrix의 power sequence의 수렴에 관한 정리에 의해 $\rho (A)<1$이면 $k$가 커질 때 $A^k$가 $0$에 수렴함을 알 수 있다. 이와 비슷하게 $\rho (A)>1$이면 $A^k$가 $\mathrm{\infty }$로 발산한다는 정리를 적을 수 있다. 이 두 사실을 이용해 $A_1:=\frac{A}{\rho (A)+ϵ},A_2:=\frac{A}{\rho (A)-ϵ}$에 대해서 $A_1^k\to 0,A_2^k\to \mathrm{\infty }$가 성립함을 알 수 있다. 그러면 각각으로부터 $||A^k|{|}^{\frac{1}{k}}$의 upper bound가 $\rho (A)+ϵ$임을, lower bound가 $\rho (A)-ϵ$임을 도출할 수 있다.

 

이 formula를 통해 다음 사실을 보일 수 있다.

Lemma For any matrix $A,B$, if $|A|<B$, then $\rho (A)\le \rho (B)$.

 

proof. $A^{\prime }:=|A|$라고 하자. 다음의 수식과 Gelfand's formula를 통해 위가 성립함을 보일 수 있다.

$$\mathrm{\forall }k\in \mathbb{N},||A^k|{|}_{\mathrm{\infty }}\le ||A^{\prime k}|{|}_{\mathrm{\infty }}\le ||B^k|{|}_{\mathrm{\infty }}\Rightarrow ||A^k|{|}_{\mathrm{\infty }}^{\frac{1}{k}}\le ||B^k|{|}_{\mathrm{\infty }}^{\frac{1}{k}}\Rightarrow \rho (A)\le \rho (B)$$

 

이제 원래 보이고자 했던 nonnegative 버전의 Perrron-Frobenius 정리를 증명해보겠다.

 

proof of Perron-Frobenius theorem. 증명 흐름을 설명하자면 다음과 같다. 먼저 $A_1>A_2>\cdots >\mathbf{0}$ 를 만족하는 positive matrix들의 무한한 sequence를 정의한다. Positive 버전의 Perron-Frobenius 정리에 따라 sequence의 모든 matrix에 대해, spectral radius가 positive이고 그것에 해당하는 positive eigenvector가 있다. 이때 positive eigenvector의 sequence에서 어떤 vector $z\ge 0$에 수렴하는 무한한 subsequence가 존재함을 알 수 있고 마찬가지로 positive spectral radius의 sequence에서 어떤 값 $a^{\prime }\ge 0$에 수렴하는 무한한 subsequence가 존재함을 알 수 있다. 이로부터 우리는 $Az=a^{\prime }z$를 만족함을 알 수 있고, $a$가 $\rho (A)$라는 사실을 통해 $a^{\prime }\le |a|$, 즉 $a^{\prime }=a$임을 알 수 있다.

 

$A_k=A+\frac{\mathbf{1}}{k}$인 decreasing하는 positive matrix의 seuquence $\{A_k{\}}_{k=1}^{\mathrm{\infty }}$를 정의한다. 이 sequence가 주어졌을 때 $a_k=\rho (A_k)$인 positive spectral radius sequence $\{a_k{\}}_{k=1}^{\mathrm{\infty }}$를 정의하고, $x_k$가 $a_k$에 해당하는 eigenvector인 postive eigenvector sequence $\{x_k{\}}_{k=1}^{\mathrm{\infty }}$를 정의한다. 이때 $x_k$는 ${\ell }_1$-norm으로 normalize 되었다고 생각할 것이다. (즉, $||x_k|{|}_1=1$.)

여기서 실해석학에서 유명한 것으로 추정되는 Bolzano–Weierstrass theorem(위키피디아)을 사용할 것이다. 이 정리가 말하는 바는 bounded sequence는 convergent subsequence를 가진다는 것이다. 즉, $\{a_k{\}}_{k=1}^{\mathrm{\infty }}$의 subsequence 중에 어떤 값 $a^{\prime }$으로 수렴하는 subsequence $\{a_{k_i}{\}}_{i=1}^{\mathrm{\infty }}$가 있고, 마찬가지로 $\{x_k{\}}_{k=1}^{\mathrm{\infty }}$의 subsequence 중에 어떤 vector $z$로 수렴하는 subsequence $\{x_{k_i}{\}}_{i=1}^{\mathrm{\infty }}$가 있다는 것이다. Positive sequence의 subsequence이므로 $a^{\prime }\ge 0$이랑 $z\ge \mathbf{0}$이 보장이 된다. 이때 모든 $x_{k_i}$의 ${\ell }_1$-norm이 1이라는 것을 통해 $z\ne \mathbf{0}$임이 보장할 수 있다. 우리가 $z,a^{\prime }$를 설정한 방식으로부터 다음의 수식이 성립함을 알 수 있다.

$$Az=\underset{i\to \mathrm{\infty }}{lim}{A}_{k_i}{x}_{k_i}=\underset{i\to \mathrm{\infty }}{lim}{a}_{k_i}{x}_{k_i}=a^{\prime }z$$

$a^{\prime }$는 $A$의 eigenvalu이므로 $a=\rho (A)\ge |a^{\prime }|=a^{\prime }$가 성립한다. 그리고 $\{A_k{\}}_{k=1}^{\mathrm{\infty }}$가 decreasing하기 때문에 $\{A_{k_i}{\}}_{k=1}^{\mathrm{\infty }}$도 decreasing하고 따라서 이전의 lemma에 의해 $\{a_{k_i}{\}}_{i=1}^{\mathrm{\infty }}$도 nonincreasing하다. 따라서 $a^{\prime }\ge a$를 만족하고 앞의 사실과 함께 $a^{\prime }=a$가 성립한다.

 

최종적으로 $\rho (A)$가 nonnegative함을 보였고 그것에 해당하는 nonnegative eigenvector가 존재함도 보였다. ■

 

 

---

이번 글에선 finite Markov chain의 stationary distribution의 existence만 보였다. 다음 글에선 Fundamental Theorem of Markov Chains의 증명을 마무리 하고자 한다. 

 

 

Reference - Lecture Notes Stochastic Processes (Spring 2022), Lecturer: Chihao Zhang

link: http://chihaozhang.com/teaching/SP2022spring/ (lecture 2)

 

comment. 어차피 증명에 등장하는 Cayley-Hamilton 정리나, Gelfand's formula나, Bolzano-Weierstrass 정리들은 건너 뛸 것이었으면 왜 Perron-Frobenius 정리는 열심히 증명했을까... 그나저나 다음 글도 이렇게 길 것같은 느낌이 든다.