마코프 체인이란?
- 마코프과정의 일종.
- 시점 t: 이산형 / 상태공간: 이산형
- 여기서는 정상성을 만족하는 마코프 체인을 다룬다.
앞서 확률과정을 정의할 때, 우리는 독립이 아닌 다변량 확률을 다음과 같이 정의했다.
\begin{align*}
P(&X_1=x_1,~X_2=x_2,
~\cdots,~X_n=x_n)
\\[15pt]
=~&~ P(X_1=x_1) ~\times~
\cdots ~\times~
P(X_n=x_n|X_1=x_1, \cdots,
X_{n-1}=x_{n-1})
\\[15pt]
&\text{(if. markov process \& stationary)}\\[15pt]
=~&~ P(X_1 = x_1) ~\times~ \cdots
\times~P(X_n=x_n|X_{n-1}=x_{n-1})
\end{align*}
마코프체인에서는 이 식을 다음과 같이 다시 쓸 수 있다.
\phi(X_1) \times p(x_1, x_2) \times p(x_2, x_3) \times~ \cdots ~\times p(x_{n-1}, x_{n})
- \phi(x)를 초기확률함수라고 한다.
- 조건부확률 p(a, b)를 전이확률(또는 추이확률)함수이라고 한다.
초기확률함수
initial probability function
\phi(a) = P(X_0 = a)
- X_0 일때의 확률분포를 의미한다.
- 이걸 정해줘야 마코프 체인의 값을 구할 수 있다.
추이확률함수
transient probability function
P(a, b) = P(X_{t+1}=a ~|~ X_{t}=b)
- 전이확률함수라고도 한다.
- 역시 확률함수인 만큼 다음과 같은 규칙이 존재한다.
- P(a, b) 는 1보다 작아야 한다.
- a, b는 상태공간 S의 원소이다.
- a를 고정하고, b를 이동시키며 P(a, b)를 다 더하면 0보다 크다.
- b를 고정하고, a를 이동시키며 P(a, b)를 다 더 하면 1이다.
P(a,b) \le 1 \kern{10pt}
a, b \in S \\[10pt]
\sum_a~P(a,b) \ge 0 \\[10pt]
\sum_b~P(a,b) = 1
마코프 체인의 표현
마코프 체인은 크게 3가지; 함수, 그림, 행렬로 표현할 수 있다.
함수는 위의 식과 같고, 그림과 행렬 표현을 보자.
추이도식
마코프 체인을 그림으로 표현한 것을 추이도식이라고 한다.
그래프 구조 또는 상태 전이도라고도 한다.
추이도식의 특징
-
동그라미를 노드 또는 시점이라고 하고, 화살표를 간선이라고 한다.
-
화살표(간선)이 곧 추이확률함수라고 할 수 있다.
-
한 시점에서 나가는 화살표의 합은 반드시 1이 나온다.
이는 추이확률함수의 조건 3과 같다.
\begin{align*}
\sum_{b \in S}~p(a,b)
&= p(1,~1) + P(1,~2) +
p(1,~3) + p(1,~4) \\[5pt]
&= 0.1 + 0.2 + 0.3 + 0.4 \\[5pt]
&= 1
\end{align*}
추이도식 그리기
손으로 그려도 되고, 그리는 도구도 있다.
중요한 것은 이걸 보고 어떻게 식이 세워질 수 있는지 파악하는 것!
- 컴퓨터로는 mermaid라는 자바스크립트 기반 라이브러리를 이용해 그릴 수 있다.
추이행렬
마코프 체인을 행렬로 표현한 것을 추이행렬이라고 한다.
왜, 그리고 어떻게 쓰는지 앞서서 한 가지 질문을 던져보자.
Limiting probability
- 시작 상태 및 과정과 상관없이, 특정 상태 = 특정 숫자일 확률은 얼마일까?
- 이를 Limiting probability라고 한다.
예를 들어, X_1이 0이 될 확률은 얼마일까? 추이도식은 아래 그림과 같다.
mermaidgraph TD
Mermaid --> Diagram
\begin{align*}
&P(X_1 = 0) = \sum_{x_0 = 0}^2
P(X_0 = x_0,~X_1 = 0) \kern{15pt}
S=\{0,1,2\} \\[15pt]
&= \sum_{x_0 = 0}^2
P(X_0 = x_0)~P(X_1 = 0~|~X_0=x_0)
\\[15pt]
&= \sum_{x_0 = 0}^2
\phi(X_0)~P(X_0=0)
\end{align*}
P(X_0이 되는 모든 것) + P(X_1이 되는 모든 것)을 다 더해야 한다.
\small
\begin{align*}
&P(X_2 = 0) = \sum_{x_0 = 0}^2
P(X_0 = x_0,~X_2 = 0) \kern{15pt}
S=\{0,1,2\} \\[15pt]
&= \sum_{x_0 = 0}^2
P(X_0 = x_0)~P(X_1 = 0~|~X_0=x_0)~P(X_2=x_2~|~X_1=x_1)
\\[15pt]
&= \sum_{x_0 = 0}^2
\phi(X_0)~\sum_{x_1}
~p(x_0, x_1)~p(x_1, x_2)
\\[15pt]
&= \sum_{x_0 = 0}^2
\phi(X_0)~\sum_{x_1}
~p(x_0, x_1)~p(x_1, 0)
\end{align*}
그럼 X_{1000}이 0이 될 확률은 얼마인가?
P(X_0이 되는 모든 것)부터 P(X_{999}가 될 모든 것)을 다 더해야 한다.
식이 너무 복잡해지기 때문에, 행렬을 사용한다.
추이행렬의 특징
Limiting probability를 계산하기 앞서, 추이행렬이 어떻게 생겼는지 보자.
다음과 같이 생겼으며, 특징은 아래와 같다.
\begin{pmatrix}
0.1 & 0.2 & 0.3 \\
0.1 & 0.2 & 0.3 \\
0.1 & 0.2 & 0.3 \\
\end{pmatrix}
-
행렬의 각 원소는 조건부확률이라고 할 수 있다.
예를 들어, 상태 1(X_1) → 상태 1(X_1)이 될 확률은 0.1이다.
-
행렬의 각 행의 합은 반드시 1이 나온다. (추이확률함수의 조건 3)
그래서 그 고유값은 1이 된다.
\begin{pmatrix}
0.1 & 0.2 & 0.3 \\
0.1 & 0.2 & 0.3 \\
0.1 & 0.2 & 0.3 \\
\end{pmatrix}
\begin{pmatrix}
1 \\ 1 \\ 1 \\
\end{pmatrix} =
\begin{pmatrix}
1 \\ 1 \\ 1 \\
\end{pmatrix}
= \bold1
추이행렬로 계산 (1)
이를 이용해 limiting probability를 계산해보자.
예를 들어, X_1이 0이 될 확률은 얼마일까? 추이도식은 아래 그림과 같다.
mermaidgraph TD
X_1 -->|0.4| X_1; X_1 -->|0.1| X_2; X_1 -->|0.5| X_3;
X_2 -->|0.3| X_1; X_2 -->|0.4| X_2; X_2 -->|0.3| X_3;
X_3 -->|0.1| X_1; X_3 -->|0.2| X_2; X_3 -->|0.7| X_3;
\begin{pmatrix}
0.4 & 0.1 & 0.5 \\
0.3 & 0.4 & 0.3 \\
0.1 & 0.2 & 0.7 \\
\end{pmatrix}
\begin{pmatrix}
0.2 \\ 0.3 \\ 0.5 \\
\end{pmatrix} =
\begin{pmatrix}
0.36 \\ 0.33 \\ 0.43 \\
\end{pmatrix}
- 앞 행렬 : 추이확률행렬. 각 원소 하나하나가 추이확률함수.
- 뒤 벡터 : 초기확률벡터. 각 원소 하나하나가 초기확률함수.
이 행렬-벡터 곱셈을 보통은 아래처럼 작성한다.
\begin{bmatrix}
P(0,0) & P(0,1) & P(0,2) \\
P(1,0) & P(1,1) & P(1,2) \\
P(1,2) & P(2,1) & P(2,2)
\end{bmatrix}^n
\begin{bmatrix}
P(X_0 = 0) \\
P(X_0 = 1) \\
P(X_0 = 2)
\end{bmatrix}
=
\begin{bmatrix}
P(X_n = 0) \\
P(X_n = 1) \\
P(X_n = 2)
\end{bmatrix}
\begin{bmatrix}
p(0,0) & p(0,1) & p(0,2) \\
p(1,0) & p(1,1) & p(1,2) \\
p(2,0) & p(2,1) & p(2,2) \\
\end{bmatrix}
\begin{bmatrix}
\phi(0) \\ \phi(1) \\ \phi(2) \\
\end{bmatrix}
=
\begin{bmatrix}
\pi(0) \\ \pi(1) \\ \pi(2) \\
\end{bmatrix}
좀 더 간결한 기호로 쓰면 다음과 같다.
\mathbf{{\phi_0}^T~P} ={\Pi_1}^T
우리가 원했던 X_1이 0이 될 확률은 결국 0.33임을 알 수 있다.
추이행렬로 계산 (2)
이번에는 X_n이 무한대로 갈 때 0일 확률을 찾아보자.
\mathbf{{\phi_0}^T~P^n} ={\Pi_n}^T
예를 들어 상태공간 S = {0, 1, 2}인 경우 다음과 같다.
\begin{bmatrix}
P(0,0) & P(0,1) & P(0,2) \\
P(1,0) & P(1,1) & P(1,2) \\
P(1,2) & P(2,1) & P(2,2)
\end{bmatrix}^n
\begin{bmatrix}
P(X_0 = 0) \\
P(X_0 = 1) \\
P(X_0 = 2)
\end{bmatrix}
=
\begin{bmatrix}
P(X_n = 0) \\
P(X_n = 1) \\
P(X_n = 2)
\end{bmatrix}
추이행렬 P의 n승을 구해야 할 때는 고유값 분해를 이용한다.
- 고유값을 찾는다.
- 고유벡터를 찾는다.
- 고유벡터를 모아 행렬 U를 만든다.
- 행렬 U의 역행렬 V를 구한다.
- 고유값을 모아 행렬 D를 구한다.
- P = U \cdot V \cdot D
또 이를 이용해서 마코프체인의 극한을 계산 할 수 있다.
\lim_{x \to \infty}~
\mathbf{{\phi_0}^T~P}^x =
\lim_{x \to \infty}~
{\Pi_x}^T