[LA] Markov Chain

Markov Chain은 Markov Property를 가지고 있는 dicrete-time stochastic process (또는 discrete-time random process)를 의미함.

달리 애기하면, 다양한 random experiment들의 trial들에 대한 확률 모델로 "현재의 state만 고려하여 다음 state가 확률적으로 결정되는 discrete-time stochastic process"임.

주로 많은 수의 trial이 이루어지는 먼 미래의 state를 예측(초기상태에 상관없이)하거나 순차적으로 발생하는 확률변수에 대한 값을 예측할 때 이용됨.

2022.10.14 - [.../Math] - [Math] Definition : Random Process

[Math] Definition : Random Process

Markov Property

다음 상태의 확률 분포가 오직 현재 상태에 의존하여 결정된다는 특성.

• 내일 날씨를 예측할 때, 일정한 확률론적 규칙(=transition matrix로 표현됨)에 오늘의 날씨만을 고려하여 결정하는 경우가 대표적인 예임. (어제와 그제 날씨는 고려하지 않음.)
• 실제로 날씨는 다양한 요소를 고려해야하나, 해당 다양한 요소가 현재 날씨에 반영되었다고 단순화시킨 형태.
• independet trails model을 따르는 동전던지기처럼 오늘 날씨에 독립적으로 내일 날씨가 결정되는 모델보다는 보다 높은 성능을 보일 수 있음.

아래 나오는 [수학적 정의](#%EC%--%--%ED%--%--%EC%A-%--%--%EC%A-%--%EC%-D%--%---Markov%--chain%--and%--Markov%--property-)를 참고할 것.

Chain vs. Process : Random Process

보통, discrete한 parameter로 index된 random variable의 집합 (random process의 정의 참고)으로 Markov Chain은 표현됨.

• index로 사용된 parameter가 discrete인 경우, Markov Chain이라 불림.
• index로 사용된 parameter가 continuous인 경우, Markov Process라고 불림.

Markov Chain은 
Markov Property를 가진(→Markov) Discrete한 index를 사용하는 Random Process( →Chain)라고 생각하면 쉽다.

Independent Trials Model과 비교 

random experiment들의 trial들에 대한 확률 모델의 관점에서 가장 단순한 모델이 바로 "independent trials model"이라고 할 수 있으며 이를 보다 확장하여, 현재의 상태에 의존(dependent)하여 다음 상태가 결정되는 것을 반영한 것이 Markov Chain이다.

흥미롭게도 Independent trials model에서 the law of large numbers가 성립하는 것처럼, Markvo Chain은 dependent한 확률에서도 the law of large numbers가 성립하게 된다.

Markov Chain은 현재의 상태에 고정된 transition matrix(확률 규칙, 모델)을 적용하여 다음 상태를 얻어내는 dependent한 경우이나, 충분히 큰 횟수을 trial을 수행할 경우 각각의 상태의 발생 횟수가 고정된 확률에 수렴하게 된다. 날씨의 예를 든다면, Markov chain에서 내일의 날씨를 오늘에 날씨에 기반하여(종속시켜) 결정하였다해도 충분히 많은 일수의 날씨(일일 날씨가 하나의 확률변수에 해당하고 확정된 상태를 가지게 됨)를 살펴보면 각 날씨의 발생 확률이 각각의 확률로 수렴함을 확인할 수 있음 (아래 Fundamental Limit Theorem 참고).

수학적 정의 (Markov chain and Markov property)

Let $\{X_n : n \ge 0\}$ be a sequence of random variables with values in a finite or countably infinite set $S$. Furthermore, assume
$$ P(X_{n+1}=y|X_0=x_1, X_1=x_1, \dots, X_{n-1}=x_{n-1},X_n=x)\\=P(X_n+1=y|X_n=x)\\=p(x,y) \tag{1} $$
for all $n \ge 0$ and all states $x, y, x_0, x_1, . . . , x_{n−1}$ in $S$.
Then $\{X_n | n\ge 0\}$ is called a Markov chain with state space $S$ and transition matrix $P=[p(x,y)]^T$. The equation (1) is called the Markov property.

• 현재상태 $x$에서 다음상태 $y$가 발생할 확률이 $p(x,y)$이고, 현재 상태가 되기까지 어떤 상태들을 거쳐왔는지는 다음 상태를 결정하는데 영향을 주지 않음을 확인할 수 있음.
• 즉, 현재의 상태만이 다음 상태를 결정하는데 영향을 주며, 이것이 Markov Property임.
• 때문에 Memoryless Model이라고도 불람.
• 참고로, 다음상태를 결정하는데 현재를 포함 k개의 최근 상태에 영향을 받는 경우를 k-memory Markov Chain이라고 부름.

Transition Matrix : 도시와 교외 인구 이동 의 예로 살펴보기

도시와 교외 인구의 분포를 column vector로 나타내는데 1행을 도시인구, 2행을 교외인구로 표현한다고 하자. 예를 들어 $i$번째 년도의 도시인구가 400,000명이고, 교외인구가 600,000이라면, 이를 나타내는 column vector $\textbf{x}$는 다음과 같음.

$$\textbf{x}_i = \begin{bmatrix}400,000 \\600,000 \end{bmatrix}$$

위의 column vector가 Markov chain에서 state vector라고도 불림.

엄밀하게 애기하면, state vector들은 보통 probability vector들로 사용된다. probability vector는 column vector의 각 entry들이 해당 상태일 확률로서 전체 entry를 다 더한 경우 1이 된다. $\textbf{x}$가 probability vector라면, $|textbf{x}|=1$이 된다.

 

해당 지역에서 매년 도시 인구의 95%는 도시에 머무는 반면 나머지 5%는 교외로 이사하고, 교외 인구의 97%는 교외에 그대로 머물지만, 나머지 3%는 도시로 이주한다고 하자. 이는 일종의 확률론적 규칙이며, Markov Chain에서는 transition matrix로 표현한다.

$$P=\begin{bmatrix}.95 & .03 \\ .05 & .97 \end{bmatrix}$$

이 transition matrix는 도시와 교외의 이주 확률을 나타내는 column vector를 column으로 가진며, 때문에 column sum=1이 된다. 

위의 trasition matrix로부터 $i+1$번째 해의 인구 분포를 구하려면 다음과 같이 transition matrix와 state vector를 곱하면 된다.

$$\textbf{x}_{i+1}\begin{bmatrix}.95 & .03 \\ .05 & .97 \end{bmatrix}\begin{bmatrix}400,000 \\600,000 \end{bmatrix}= \begin{bmatrix}398000 \\602000 \end{bmatrix}$$

import numpy as np
P = np.array([
    [0.95,0.03],
    [0.05,0.97]
])
x_0 = np.array([
    [400000],
    [600000]
])
x_1 = np.dot(P,x_0)

 

만약 $i+2$번째 해의 인구분포를 얻으려면 $\textbf{x}_{i+1}$에 다시 $P$를 곱하면 됨.

200년정도 후와 300년정도 후를 구하면 재밌게도 똑같은 인구분포를 보임 (이를 steady-state라고 부름).

$$\textbf{x}_{i+200}= \begin{bmatrix}375000 \\625000 \end{bmatrix},\textbf{x}_{i+300}= \begin{bmatrix}375,000 \\625,000 \end{bmatrix}$$,

P_200 = np.linalg.matrix_power(P, 200)
x_200 = np.round(np.dot(P_200,x_0))
print(x_200)
P_300 = np.linalg.matrix_power(P, 300)
x_300 = np.round(np.dot(P_300,x_0))
print(x_300)

 

더 흥미로운건 steady-state에 도달하는 경우, initial state를 무엇으로 했느냐는 중요하지 않다는 점임.

Markov chain이 steady-state에 도달한다면, 다양한 초기 상태를 사용해도 결국 동일한 steady-state에 도달하게 된다.

위에서 사용된 $P$를 transition matrix 또는 stochastic matrix라고 부르는 것을 잊지 말자.

즉, $P$가 Markov chain의 동작특성과 결과 등을 결정하며, 초기 상태는 충분히 큰 수의 시행을 거치고 난 이후에는 의미가 없다 ($P$가 regular transition matrix인 경우).

 

 

모든 Markov Chain은 Steady-State에 도달하나?

Steady-state의 확률분포 (= stationary distribution of chain)를 column vector $textbf{q}$라 하면 다음이 성립하는 경우임.

$$\underset{n\to \infty}{\lim}P^n\textbf{x}_0=\textbf{q}$$

steady-state vector의 경우 다음도 성립함.

$$P\textbf{q}=\textbf{q}$$

 

이를 수학적으로 정리한 theorem을 Fundamental Limit Theorem이라고 부르는데, 간단히 살펴보면 다음과 같음.

• 모든 Markov chain이 steady-state에 도달하는 건 아님.
• Markov chain이 "irreducible하면서 aperiodic인 transition matrix"(=regular)를 가질 경우에는 steady state에 도달함. (regular=irreducible + aperiodic)

참고로 steady state에서의 state vector를 probability vector로 표현할 경우,  transition matrix의 모든 column vector와 일치하게 된다. 즉, Markov chain의 $n \times n$ square transition matrix $P$를 충분히 큰 수로 거듭제곱할 경우, 모든 column vector가 동일해지게 된다. 

위에서 보인 도시와 교외인구 예에서의 transition matrix를 충분히 큰 수로 거듭제곱할 경우 다음과 같음.

$$\underset{n\to\infty}{\lim}P^n=\begin{bmatrix}.375 &  .375\\ .625 & .625 \end{bmatrix}$$

 

이를 수학적인 proposition으로 표현하면 다음과 같음.

$$P \text{is a regular transition matrix} \Rightarrow \underset{n\to\infty}{\lim}P^n \text{ is exists and rank }1.$$

 

관련된 정의는 다음과 같음.

Ergodic or Irreducible Markov Chain
Markov chain에서 모든 각각의 상태로부터 출발하여 다른 모든 상태로 도달할 확률(단, 여러 단계를 거치더라도 상관없음)이 0이 아닌 경우, 해당 Markov chain을 ergodic하다고 부름.

Regular Markov Chain
Markov chain이 유한한 state space를 가지고 있으면서, 자신의 transition  matrix를 여러차례 거듭제곱한 결과 matrix의 entry값들이 모두 양수(strictly positive)인 경우, 해당 Markov chain을 regular하다고 부름.

참고로 ergodic인 경우의 subset이 바로 regular이므로, regular인 경우 ergodic을 만족함.

 

예 : Ergodic but not Regular

다음과 같은 Transition matrix를 생각해보자. (2개의 state를 가질 수 있는 Markov chain의 경우임)

$$P=\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}.$$

이들에 대해서 power를 수행하면 다음과 같음.

$$P^2=P^4=P^6=\begin{bmatrix}1 & 0 \\ 0 & 1\end{bmatrix},P=P^3=P^5=\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$$

횟수가 even이냐 odd냐에 따라, 주기적으로 transition matrix가 변하기 때문에 steady-state가 없음.

 

관련된 다음의 두 theorem도 명심하자.

Theorem 1
Let $P$ be the transition matrix for an ergodic Markov chain. Then there is a unique probability vector $\textbf{w}$ such that $\textbf{w}=P\textbf{w}$.

 

Theorem 2 : Weak Law of Large Numbers of Markov Chains
Let $\textbf{w}$ be the stationary initial distribution of an ergodic Markov chain.
For $m = 0, 1, 2, . . . ,$ let $Y_m = 1$ if the $m$-th step is in state $j$ and zero otherwise. (~$j$상태가 일어날 때 1). Let
$$ H^n_j = (Y_0+\cdots+Y_n)/(n+1) $$
$H^n_j$ is the average number of times in state $j$ in the first $n+1$ steps. Then, for every $\epsilon >0$
$$ \underset{n \to \infty}{\lim}P(|H^n_j-\textbf{w}_j|>\epsilon) = 0, $$
independent of the starting distribution.