고정 헤더 영역
상세 컨텐츠
본문
이 글에선 Fundamental Theorem of Markov Chains의 증명을 마루리 하고자 한다.
지난글: https://cultivated-algorist.tistory.com/entry/Fundamental-Theorem-of-Markov-Chains-1
이전 글에서 Finite Markov chain은 항상 stationary distribution이 존재함을 보였다. 과연 stationary distribution은 unique할까? 그리고 임의의 시작 분포에서 시작하더라도 stationary distribution으로 수렴할까? 이 두 질문에 답하기 위해 두가지 개념을 생각하고자 한다.
Irreducibility
Markov chain을 directed graph라고 생각하자. 이때 그래프가 여러 component로 나뉘었다고 생각해보자. 즉, 한 component에서 다른 component로 가는 (directed) path가 존재하지 않는 것이다. 우리는 각 component를 개별적인 Markov chain으로 생각해도 된다. 이전 글에서 보인 stationary distribution의 존재성에 따라 각 component는 stationary distribution을 가질 것이다. 그러면 전체 그래프에 해당하는 Markov chain의 stationary distribution은 각 component의 stationary distribution의 convex combination이면 될 것이다. 다시 말해서, $i$번째 component의 stationary distribution을 $\pi_i$라고 하면 $\pi=\sum_i{c_i \pi_i}, \text{ where } \sum_i {c_i}=1$인 $\pi$가 stationary distribution이 될 수 있다는 뜻이다.
Stationary distribution의 uniqueness는 irreducibility에서 포착된다.
Definition. Irreducibility
만약 finite Markov chain의 transition graph가 strongly connected component면, 해당 Markov chain을 irreducible하다고 부른다.
즉, 모든 state $i,j$에 대해, $P^t_{ij}>0$을 만족하는 시점 $t$가 존재하면 ireeducible하다.
(Strongly connected면 어떤 두 vertex를 고르더라도 그 사이를 잇는 (directed) walk가 있어야 하고, 그 walk의 길이가 $t$일 때 $P^t_{ij}>0$이어야 한다. Walk의 길이는 그것이 지나는 edge의 수로 정의된다.)
Aperiodicity
설령 Markov chain이 irreducible하면 stationary distribution이 unique하다는 것이 보장이 되더라도, $\mu_0$에 따라 stationary distribution $\pi$에 수렴하지 않을 수 있다. 예를 들어 어떤 state가 (1보다 큰) 어떤 주기로 "동일한 영향"을 받는다면 수렴하지 않고 진동할 수도 있다.
Stationary distribution으로의 수렴은 aperiodicity에서 포착된다.
Definition. Aperiodicity
Vertex $v$에서 시작하고 $v$에서 끝나는 모든 closed directed walk의 길이의 $\text{gcd}$(최대공약수)를 $v$의 period라고 하자. 만약 finite Markov chain의 transition graph에서 모든 vertex가 1의 period를 가진다면, 해당 Markov chain을 aperiodic하다고 부른다.
즉, 모든 state $i$에 대해 $\text{gcd}\{t\ge1: P^t_{ii}>0\}=1$이면 aperiodic하다.
($P^t_{ii}>0$이면 $i$에서 길이가 $t$인 closed directed walk가 있다는 뜻이다.)
Example
다음의 간단한 Markov chain을 살펴보도록 하겠다.
해당 Markov chain의 transition matrix는 다음과 같다. $$P=\left[\begin{matrix} 1-p & p \\ q & 1-q \end{matrix}\right]$$ 이때 stationary distribution은 다음과 같다. $$\pi=\left(\begin{matrix} \frac{q}{p+q} \\ \frac{p}{p+q} \end{matrix}\right)$$ 만약 $p=q=0$이었다고 해보자. 그러면 $P$는 identity matrix가 되기 때문에 어떤 분포를 가져 오더라도 stationary distribution이다. $p=q=1$이었다고 해보자. 그러면 $(1/2,1/2)$는 unique stationry distribution이지만 초기 분포가 $(1,0)$이면 $(1,0)$과 $(0,1)$를 반복적으로 진동한다.
Fundamental Theorem of Markov Chains
Theorem. Finite, irreducible, and aperiodic Markov chain은 unique stationary distribution $\pi$를 갖고, 임의의 $\mu$에 대해서 $\displaystyle\lim_{t\rightarrow \infty}{\mu^TP^t}=\pi$를 만족한다.
증명을 한마디로 요약하자면 다음과 같다. "적당한" 시간이 흐르면 만족하는 $P$의 "성질"때문에, 임의의 $\mu$와 stationary distribution $\pi$와의 거리가 그렇게 "크지 않고", 따라서 시간이 계속 흐르면 거리가 0으로 수렴한다. "적당한 시점" 이후부터 $P$가 어떤 "성질"을 만족함을 것을 보일 때 irreducibility와 aperiodicity가 사용되고, 둘 사이의 거리가 "크지 않다"는 것을 bound할 때 coupling 기법이 사용된다.
cf) Coupling 기법은 FTMC를 보일때만 사용되는 것이 아니라 여러 증명에서 두 distribution이 시간이 흐르면 비슷해 진다는 것을 보일 때 사용되기 때문에 기억할만 하다. 기회가 된다면 나중에 coupling을 이용해 분석을 하는 문제들을 다뤄보도록 하겠다.
Part 1
우리가 사용할 적당한 시점 $\tau$는 모든 state $i,j$에 대해서 $P^\tau_{i,j}>0$이면서 $\tau$ 이후부터는 모든 시점에서 $P^t>0$이 성립한다는 것이다. 즉, 특정 시점 이후부터는 한 state에서 다른 state로 갈 확률이 $0$보다 크다는 것이다. 우리는 irreducible, aperiodic한 finite Markov chaine에 그러한 $\tau$가 항상 존재함을 보일 것이다.
Claim. There exists $\tau$ such that $P^t>0$ for all $t \ge \tau$.
proof. Transition graph에서 아무 vertex $i$를 고르자. $i$에서 $i$가 아닌 임의의 vertex에 도달하기 위해 최소로 지나야 하는 edge 수를 $t'$라고 하자. (즉, unweighted directed graph에서 $i$와 가장 멀리 떨어져 있는 vertex 사이의 거리가 $t'$인 것이다.) 이때 그래프의 vertex 수가 $n$이기 때문에 $t'\le n$임을 알 수 있다. 이번에는 $i$에서 시작해서 $i$로 돌아오는 closed walk들의 집합 $W_{i}$를 생각해보자. (이 집합은 무한 집합일 것이다.) 이때 만약 어떤 값 $t_i$가 있어서 $t_i$ 이상인 모든 $t$에 대해 길이 $t$짜리 closed walk가 $W_{i}$에 존재한다고 생각해보자. 그러면 $\tau_i:=t_i + n$ 이상인 모든 $t$에 대해, 어떤 $j$를 가져오더라도 $i$에서 $j$로 가는 길이 $t$짜리 walk가 존재함을 알 수 있다. (여기서 "어떤 $j$"가 $i$였다면 자명하고, $i$가 아니었다면 irreducibility에 의해 $i$에서 $t'(\le n)$이하의 edge만 거쳐서 도달할 수 있기 때문이다.) 즉, 모든 $j$에 대해서, 그리고 $\tau_i$ 이상의 모든 $t$에 대해서 $P^t_{ij}>0$인 것이다.
$\tau := \max_i {\tau_i}$라고 해보자. 우리는 모든 $t \ge \tau$에 대해, $P^t > 0$임을 알 수 있다. 따라서 우리는 모든 $i$에 대해 $\tau_i$가 존재함을 보이면 충분하다. 이를 증명을 하기 전에 아래 예시를 보도록 하겠다.
$W_i(\ell)$을 $W_{i}$ 중에서 길이가 $\ell$인 walk들의 set이라고 해보자. 그러면 각 $\ell=1,2, ...$에 대해서 $W_i(\ell)$을 다음과 같이 적어줄 수 있다. (Walk는 edge들의 set이긴 하지만 편의상 다음과 같이 적도록 하겠다.)
$W_i(1)=W_i(2)=\emptyset$
$W_i(3)=\{ i\text{–}j\text{–}k\text{–}i \}$
$W_i(4)=\{ i\text{–}f\text{–}g\text{–}h\text{–}i \}$
$W_i(5)=\emptyset$
$W_i(6)=\{i\text{–}j\text{–}k\text{–}i\text{–}j\text{–}k\text{–}i \}$
$W_i(7)=\{i\text{–}j\text{–}k\text{–}i\text{–}f\text{–}g\text{–}h\text{–}i, i\text{–}f\text{–}g\text{–}h\text{–}i\text{–}j\text{–}k\text{–}i \}$
$\cdots$
이를 일반적으로 이야기 하자면 $W_i(\ell)$이 공집합인지 아닌지는 길이가 $\ell$ 이하의 walk의 조합으로 길이 $\ell$ 짜리 walk를 만들 수 있는지와 동일하다. 그리고 이때 길이가 $\ell$ 이하인 walk들 중에서 길이가 $3$, $4$인 walk에 대해서만 생각해도 충분함을 확인할 수 있다. 즉, 길이가 $\ell$인 walk가 있는지 확인하는 것은 $3x_1+4x_2=\ell$을 만족하는 음이 아닌 정수해 $x_1,y_1$가 있는지 확인하는 것과 똑같다는 것이다. 그러면 $\ell$이 어느 정도 커야지 그러한 해가 항상 존재할까?
애초에 이것이 성립하지 않았다고 가정해보자. 어떤 $\ell$에 대해 $3x_1+4x_2=\ell$가 음의 정수인 해만 있다면 $\ell$은 $3+4=7$의 배수는 아닐 것이다. 즉, 그러한 $\ell$은 음이 아닌 정수 $q$와, $0$부터 $6$사이의 자연수 $r$에 대해 $7q+r$로 표현될 것이다.
논의를 진행하기 위해 $\text{gcd}$(최대공약수)를 구하는 알고리즘인 유클리드 호제법을 소개하고자 한다. 이 알고리즘은 두 자연수 $a,b$ $(a>b)$가 주어졌을 때 $\text{gcd}(a,b)=\text{gcd}(b, a\text{ mod }b)$를 재귀적으로 적용하는 것이다. 알고리즘의 종료는 $b$가 $0$이 될때 그때의 $a$를 출력한다. 예를 들어 $(1071,1029)$가 주어졌을 때,
$(1071,1029) \text{ } 1071= 1 \cdot 1029 + 42$
$(1029, 42) \text{ } 1029 = 24 \cdot 42 + 21$
$(42,21) \text{ } 42 = 2 \cdot 21 + 0$
$(21,0)$
의 과정으로 $\text{gcd}(1071,1029)=21$임을 알 수 있다. 우리는 이 과정을 역으로 다시 진행할 것이다.
$21 = 1029 - 24 \cdot 42$
$21 = 1029 - 24 \cdot (1071- 1\cdot 1029) \Rightarrow 21 = - 24 \cdot 1071 + 25 \cdot 1029$
즉, 어떤 정수 $y_1,y_2$에 대해서 $\text{gcd}(1071,1029)=1071y_1+1029y_2$로 표현할 수 있다. 이를 일반화 하자면 우리는 자연수 $a,b$가 주어졌을 때 $\text{gcd}(a,b)=ay_1+by_2$를 만족하는 정수 $y_1,y_2$가 존재한다고 할 수 있다.
우리의 경우로 다시 돌아오자. $3x_1+4x_2=7q+r$를 만족하는 $x_1,x_2$는 음의 정수밖에 없을까? $3$과 $4$의 최대공약수는 $1$이니 $3y_1+4y_2=1$을 만족하는 정수해 $y_1,y_2$가 존재함을 이용해보자. 만족하는 $y_1,y_2$를 하나 고정하자. $$ 7q+r = (3+4)q+1\cdot r = (3+4)q + (3y_1+4y_2)r$$$$=3(q+ry_1)+4(q+ry_2)$$ 이때 앞서 고정한 $y_1,y_2$에 대해, $|y_1|$과 $|y_2|$ 중 더 큰 값을 $y^*$라고 하자. $(y^*:=\max\{|y_1|,|y_2|\})$. 여기서 $q$가 $7y^*$ 이상의 어떤 값으로 설정되었다고 생각해보자. 그리고 $(x_1,x_2)$를 $(q+ry_1,q+ry_2)$로 설정했을 때 $x_1,x_2$는 이 방정식의 해이면서 모두 자연수이다.
우리는 음의 정수만 해로 갖는 것을 가정하고 시작했지만 $\ell$이 적당히 크다는 조건 하에 음이 아닌 정수해를 하나 찾았으므로, 해당 조건에서는 가정이 모순임을 결론지었다. 우리의 목표는 적당힌 큰 $\tau_i$에 대해 $\tau_i$이상인 모든 $t$에 대해서 $W_i(t)\neq \emptyset$을 보이는 것임을 기억하자. 이제 위의 간단한 예시 말고 이 과정을 일반적으로 적용해보자. $i$에서 시작해서 $i$로 돌아오는 closed walk는 무한히 많지만 우리는 관심있는 walk를 finite하게 한정할 수 있고 그것들의 길이만 보면 된다. 그 길이들을 $a_1, ... a_k$라고 해보자. 우리는 유클리드 호제법을 통해 얻은 수식을 일반화 해서 다음과 같이 적을 수 있다. (Bézout's identity 라고도 불린다.)
$$\text{gcd}(a_1,...,a_k)=a_1y_1+\cdots + a_ky_k$$
Aperiodicity때문에 $\text{gcd}(a_1,...,a_k)=1$을 만족한다. 따라서 $\tau_i := (\sum_{1\le s \le k}{a_s})^2 \cdot \max_{1\le s \le k}{|y_s|}$ 이상의 $\ell$에 대해서 $a_1x_1+\cdots+a_kx_k=\ell$에 자연수 해 $x_1,...,x_k$가 존재한다. 따라서 모든 $t \ge \tau$에 대해, $P^t > 0$이다. ■
$\tau:=n^2-2n-2$로 충분하다는 것이 알려져 있다고 한다.
Part 2. Coupling Lemma
우리는 임의의 distribution과 stationary distribution의 거리에 대해 다루는 것이 목표임을 기억하자. 거리는 다음과 같이 정의된다.
Definition. Total Variation Distance
Finite (or countably infinite) state space $\Omega$의 두 distribution $\mu, \nu$의 total variation distance는 다음과 같다. $$ D_{TV}(\mu,\nu) = \frac{1}{2}\sum_{x \in \Omega}{|\mu(x)-\nu(x)|}$$
어떤 distribution $\eta$에 대해서 $\eta(A):= \sum_{x \in A}{\eta(x)}$라고 정의하자. 그러면 다음은 위와 동일한 정의이다.
(Another) Definition.
$$ D_{TV}(\mu,\nu) = \max_{A \subseteq \Omega} |\mu(A)-\nu(A)| $$
우변을 maximize하는 subset $A$를 $\mu(x) \ge \nu(x)$인 $x$를 모두 모아둔 set으로 생각하자. 위 식이 성립하는 이유는 $\mu$와 $\nu$가 distribution이기 때문에 $A$에서 $\mu$가 큰 만큼 $A$가 아닌 나머지 $A^c$에서는 $\nu$가 커야 하기 때문이다. (수식으로 적어보면 성립함을 쉽게 알 수 있다.)
이제 두 distribution의 coupling을 정의하도록 하겠다.
Definition. Coupling
$\mu,~\nu$는 $\Omega$의 distribution이고 $\omega$는 $\Omega \times \Omega$의 distribution이다. 만약 $(X,Y)\sim \omega$가 $X\sim \mu$와 $Y\sim \nu$를 만족한다면, $\omega$는 $\mu$와 $\nu$의 coupling이다.
즉, $\omega$의 두 marginal이 각각 $\mu,~\nu$이면 $\omega$는 $\mu$와 $\nu$의 coupling이라는 것이다. 간단한 예시를 들어 설명해보겠다. State space가 $\Omega=\{H,T\}$인 동전 던지기를 생각해보도록 하겠다. $\mu(H)=1/2$이고 $\nu(H)=1/3$이라고 해보겠다. 만약 $\omega_1,~\omega_2$가
$$ \omega_1(H,H)=1/3,~\omega_1(H,T)=1/6,~\omega_1(T,H)=0,~\omega_1(T,T)=1/2 $$
$$ \omega_2(H,H)=1/6,~\omega_2(H,T)=1/3,~\omega_2(T,H)=1/6,~\omega_2(T,T)=1/3 $$
라면 이 두 distribution은 모두 $\mu$와 $\nu$의 coupling이다.
이제 coupling 기법이 total variation distance를 upper bound하는 데에 사용될 수 있다는 lemma를 소개하고자 한다.
Coupling Lemma.
$\mu,~\nu$의 모든 coupling $\omega$는 $$D_{TV}(\mu,\nu) \le \Pr_{(X,Y)\sim \omega}[X\neq Y]$$ 을 만족한다. 또한 이를 등식으로 만족하는 coupling $\omega^*$가 존재한다.
proof. Coupling distribution $\omega$를 하나 fix하자. 그럼 다음이 성립한다.
$$ \Pr[X=Y] = \sum_{t \in \Omega}\Pr[X=Y=t] $$
$$\le \sum_{t \in \Omega} {\min\{\Pr[X=t],\Pr[Y=t]}\} = \sum_{t \in \Omega} {\min\{\mu(t),\nu(t)}\}$$
이를 이용해 $\Pr[X\neq Y]$를 bound할 것이다.
$$1-\Pr[X=Y] \ge 1-\sum_{t \in \Omega} {\min\{\mu(t),\nu(t)\}}$$
$$= \sum_{t \in \Omega} {\left(\mu(t)-\min\{\mu(t),\nu(t)\}\right)}$$
$$= \max_{A \subseteq \Omega} |\mu(A)-\nu(A)| = D_{TV}(\mu,\nu)$$
이제 $\omega^*$이 존재함을 보이자.
$$\omega^*(t_1,t_2):=\begin{cases} \min\{\mu(t_1),\nu(t_1)\}, &\text{ if $t_1=t_2$,} \\ \\ \\ \frac{\left(\mu(t_1)-\nu(t_1)\right)^+\left(\nu(t_2)-\mu(t_2)\right)^+}{D_{TV}(\mu-\nu)}, &\text{ o/w.} \end{cases}$$
(여기서 $z^+$는 $\max\{z,0\}$을 뜻한다.) 이것이 $\mu$와 $\nu$의 coupling이라는 것을 보여야 한다. $\mu\ge \nu$가 성립하는 set $A$와 나머지 $A^c$에 대해서 계산했을 때 marginal이 각각 $X$에 대해서는 $\mu$가, $Y$에 대해서는 $\nu$가 됨을 확인할 수 있다. (계산은 생략하도록 하겠다.)
그리고 이 $\omega^*$는 수식을 등식으로 성립하는 것도 확인할 수 있다. ■
이제 coupling 기술을 이용하여 임의의 distribution $\mu_0$에서 시작하더라도 $D_{TV}(\mu_t,\pi)\rightarrow 0$임을 보이도록 하겠다. ($\pi$가 stationary distribution임을 기억하자.)
What To Show: For any $\mu_0$, $$\lim_{t\rightarrow \infty}{D_{TV}(\mu_t,\pi)}=0.$$
proof. $\mu_0$를 하나 고정하자. 그리고 state space가 $\Omega$인 Markov chain $\mathcal{X}$에서 동작하는 두 process $\{X_t\}_{t\ge0},~\{Y_t\}_{t\ge0}$을 정의하겠다. 이 둘의 시작 distribution이 각각 $\mu_0,~ \pi$이다.
이제 state space가 $\Omega \times \Omega$인 Markov chain을 하나 생각할 것이다. 이것의 transition matrix를 $\mathcal{P}$라고 하자. $$\mathcal{P}_{(i,i')(j,j')}:= \begin{cases} P_{ij}P_{i'j'}, & \text{ if $i\neq i'$,} \\ \\ P_{ij}, & \text{ if $i=i'$ and $j=j'$,} \\ \\ 0, & \text{ if $i=i'$ and $j \neq j'$.} \end{cases}$$ 이는 다음과 같이 해석할 수 있다. $\mathcal{X}$ 상에서 $i$와 $i'$가 다른 state라면 $(i,i')$에서 $(j,j')$으로 갈 확률은 $\mathcal{X}$ 상에서 $i$에서 $j$로 갈 확률, $i'$에서 $j'$으로 갈 확률을 독립적으로 구하고 곱한 것과 같다. 만약 $i$와 $i'$가 $\mathcal{X}$ 상에서 같은 state였다면 "coupled" 상태로 무조건 같은 state $j=j'$으로 이동한다.
$\omega_0$을 다음과 같이 정의하자. 모든 $i,j\in \Omega$에 대해, $$\omega_0(i,j):= \mu(i)\nu(j)$$ 그리고 새롭게 정의한 Markov chain에서 시작 distribution이 $\omega_0$인 process $\{W_t\}_{t\ge0}$를 생각해보자. 우리는 모든 $t$에 대해서 $\omega_t$가 $\mu_t$와 $\pi$의 coupling임을 확인할 수 있다. (수식으로 쉽게 보일 수 있다.)
우리는 $\{W_t\}$를 다음처럼 생각할 것이다. 이 process에는 $\{X'_t\}$와 $\{Y'_t\}$가 들어가 있는데 이 둘은 $\mathcal{X}$에서 같은 state에 도착하기 전까지는 서로 독립적인 process이지만, 같은 state에 위치하는 순간부터는 coupled 상태로 똑같이 동작한다. 그렇다면 $$\Pr_{(X'_\tau,Y'_\tau)\sim \omega_\tau}[X'_\tau\neq Y'_\tau]$$를 어떻게 계산할 수 있을까? 위에서 irreducibility와 aperiodicity를 통해 $P^\tau > 0$를 만족하는 $\tau$가 존재함을 보였음을 기억하자. $P^\tau \ge \alpha$를 만족하는 양수 $\alpha$ 하나를 고정하자. ($P^\tau$의 entry 중에서 minimum 값을 고르면 된다.) 만약 $\{W_\tau\}$ 속의 $\{X'_\tau\},~\{Y'_\tau\}$가 서로 independent했으면, 각각을 $X_\tau$와 $Y_\tau$로 생각하고 임의의 state $i$에 대해 $\Pr[X_\tau=i]\Pr[Y_\tau=i] \ge \alpha^2$로 lower bound할 수 있다. 하지만 이 둘은 independent하지 않고 correlate되어 있다. 즉, 어떤 시점에서 같은 state에 있으면 그 이후에도 같은 state에 있다는 것이다. 이 Correlation을 고려해서 계산한 $\Pr[X'_\tau=Y'_\tau]$는 independence를 가정해서 고려한 계산보다 더 클 것이다. 따라서 우리는 안전하게 다음과 같이 적을 수 있다. $$\Pr_{(X'_\tau,Y'_\tau)\sim \omega_\tau}[X'_\tau= Y'_\tau]\ge \Pr_{X_\tau\sim \mu_\tau}[X_\tau=i] \Pr_{Y_\tau\sim \pi}[Y_\tau=i]\ge \alpha^2$$$$\Rightarrow \Pr_{(X'_\tau,Y'_\tau)\sim \omega_\tau}[X'_\tau\neq Y'_\tau] \le 1-\alpha^2 $$
사실 우리는 $\tau$에 대해서만이 아니라 $t$가 커지면 $$D_{TV}(\mu_t,\pi) \le \Pr_{(X'_t,Y'_t)\sim \omega_t}[X'_t\neq Y'_t]$$ 가 $0$으로 수렴하는 것을 보이고 싶은 것이다. 분명한 것은 $t$가 커지면 위 값이 감소한다는 것이다. 그러면 $\tau$ 시점에서 $\tau$만큼 더 흐른 $2\tau$ 시점에서 bound가 어떻게 되는지 생각해보자. Coupling을 한 방식 때문에 $\tau$ 시점에서 $X'_\tau$와 $Y'_\tau$의 state가 같았다면 $2\tau$시점에서 $X'_{2\tau}\neq Y'_{2\tau}$일 수는 없다는 것을 기억하자. $$\Pr[X'_{2\tau}\neq Y'_{2\tau}]=\Pr[X'_{2\tau}\neq Y'_{2\tau}|X'_{\tau}\neq Y'_{\tau}]\cdot\Pr[X'_{\tau}\neq Y'_{\tau}]$$$$\le \Pr[X'_{2\tau}\neq Y'_{2\tau}|X'_{\tau}\neq Y'_{\tau}]\cdot(1-\alpha^2) \le (1-\alpha^2)^2$$ 첫 부등식은 Markov chain의 성질 때문에 성립한다. 즉, $\tau$시점에서 state가 다르다는 조건 하에 $\tau$만큼 더 흘렀을 때 달랐을 확률은, 시작 시점에서 다르다는 조건 하에 $\tau$만큼 더 흘렀을 때 다를 확률과 같다. 따라서 이 과정을 계속 적용하면 $$\Pr[X'_{k\tau}\neq Y'_{k\tau}] \le (1-\alpha^2)^k$$로 적을 수 있다.
증명이 완료가 되었다. $\Pr_{(X'_t,Y'_t)\sim \omega_t}[X'_t\neq Y'_t]$는 $t$가 커짐에 따라 줄어드는데 $\tau$ 시점에는 최대 $1-\alpha^2$이고 그 이후부터 매 $\tau$만큼 흐르면 그 상한이 $1-\alpha^2$배는 줄어든다. $\alpha$가 골라진 방식을 고려하면 임의의 distribution이 stationary distribution으로 수렴함을 알 수 있다. ■
Part 3
길고 긴 증명들의 연속에 지쳐서, 이제 끝났다고 생각할 수 있지만 아직 stationary distribution이 unique하다는 주장은 없었다. 하지만 이것은 imply되어 있다. 이를 보기 위해 Part 2의 증명을 다른 방식으로 보도록 하겠다.
$P':=P^\tau$라고 하고 $\alpha$는 예전처럼 $P'$에서 가장 작은 entry 값이라고 하자. 우리는 임의의 두 distribution $\mu,~\nu$에 대해 다음이 성립함을 알 수 있다. $$D_{TV}(\mu P',\nu P') \le (1-\alpha)D_{TV}(\mu,\nu)$$ 이를 다시 쓰면 다음과도 같다.
Claim. $$||\mu P'-\nu P'||_1 \le (1-\alpha) ||\mu-\nu||_1$$
proof. 증명은 간단하다. 임의의 column을 정해 그 column의 entry의 값을 $\alpha$만큼 뺀 matrix를 $Q$라고 하자. 그 임의의 column을 $j^*$이라 하자. $$||\mu P'-\nu P'||_1 =\sum_j { | \sum_i {\mu(i) P'_{ij}} - \sum_i {\nu(i) P'_{ij}} |}$$ $$=| \sum_i {\mu(i) (\alpha+Q_{ij})} - \sum_i {\nu(i) (\alpha+Q_{ij})} |+\sum_{j\neq j^*}{ | \sum_i {\mu(i) Q_{ij}} - \sum_i {\nu(i) Q_{ij}} |}$$ $\mu$와 $\nu$는 distribution이므로 $\sum_i{(\mu(i)-\nu(i))}=0$이다. 이것과 $Q \ge 0$임을 이용해서 수식을 정리하면 $$\sum_{j}{ | \sum_i {\mu(i) Q_{ij}} - \sum_i {\nu(i) Q_{ij}} |}=\sum_{j}{ \sum_i {|\mu(i)-\nu(i)| Q_{ij}} }$$$$=\sum_{i}{\left(|\mu(i)-\nu(i)|\sum_j {Q_{ij}} \right)}=(1-\alpha)||\mu-\nu||_1$$ ■
일반적으로 말하자면 $$||\mu P'^k-\nu P'^k||_1 \le (1-\alpha)^k ||\mu-\nu||_1$$ 이고 이로부터 convergence를 보일 수 있다.
이제 unique함을 보이기 위해 사용할 contraction fixed point theorem을 소개하고자 한다.
Definition. Contraction mapping
Let $(\mathcal{S},d)$ be a complete metric space. Then a map $T:\mathcal{S}\to \mathcal{S}$ is called a contraction mapping on $\mathcal{S}$ if there exists $q\in [0,1)$ such that $d(T(s_1),T(s_2)\leq qd(s_1,s_2)$ for all $x,~y\in \mathcal{S}$.
$\mathcal{S}$를 $n$ 차원의 distribution vector space $(\Bbb{R}^n)$, distance function $d$를 $D_{TV}(\cdot,\cdot)$ 혹은 $\ell_1$-norm으로 생각한다면 위의 claim에 따라 $P'$가 contraction mapping임을 볼 수 있다.
Theorem. Contraction Fixed Point Theorem (Banach Fixed Point Theorem).
즉 임의의 distribution이 수렴하는 distribution은 unique하다.
Reference
- Lecture Notes of Stochastic Processes (Spring 2022), Lecturer: Chihao Zhang (link, lecture 3)
- $\tau$ 존재 참고 (link, page 9)
- $\tau = n^2$ enough, uniqueness of $\pi$ 참고 (link, page 3)
- coupling lemma 증명 참고 (link, page 3)
comment. Fundamental Theorem of Markov chain을 이해하고 싶었는데 뭘 보든 그것만으론 한번에 이해하기 어려워서 정리를 해보았다... 꽤나 복잡하지만 증명들은 예쁘다.
'Stochastic Process' 카테고리의 다른 글
| Fundamental Theorem of Markov Chains (1) (0) | 2022.08.02 |
|---|
댓글 영역