[Probability] Markov Chains

1. Markov Chain Models

A Markov chain model is specified by identifying:

    (a) the set of states $S = \{1, \cdots, m\}$.

    (b) transition probability matrix $P = \begin{bmatrix} p_{11} & \cdots & p_{1m} \\ \vdots & \ddots & \vdots \\ p_{m1} & \cdots & p_{mm} \end{bmatrix}$

 

transition probabilities $p_{ij}$는 현재 state($X_n$)가 $i$일 때, 다음 state($X_{n+1}$)가 $j$가 될 확률을 의미한다.

이때, 과거 state($X_{<n}$)를 고려하지 않는 이유는 모든 Markov chain 모델이 Markov property를 따르기 때문이다.

 

Markov property

현재 state $i$에 도달하기까지 거친 과거의 어떠한 과정(=$X_{<n}$)도

현재 state $i$에서 다음 state $j$로 가는 확률(=$p_{ij}$)에 영향을 주지 않는다.

이는 "과거의 어떤 과정(=$X_{<n}$)도 state $i$에서 state $j$로 가는 확률(=$p_{ij}$)에 동일한 영향을 준다"로 해석할 수 있다.

이를 수식으로 표현하면 다음과 같다.

$$P(X_{n+1}=j|X_n=i, X_{n-1}=a_{n-1}, \cdots, X_0=a_0) = P(X_{n+1}=j|X_n=i, X_{n-1}=b_{n-1}, \cdots, X_0=b_0) \\ P(X_{n+1}=j|X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) = P(X_{n+1}=j|X_n=i) = p_{ij}, \quad i,j \in S$$

즉, 어떤 $(X_0, \cdots, X_{n-1})$의 조합도 $p_{ij}$에 동일한 영향을 주기 때문에, 생략해도 무방하다.

---

$P(X_{n+1}=j|X_n=i, X_{n-1}=i_{n-1}, \cdots, X_0=i_0) = P(X_{n+1}=j|X_n=i)$을 바라보는 두 가지 관점

 

이 수식은 두 가지 관점으로 해석할 수 있다.

1). 이전 결과($X_{<n}$)는 이후 결과($X_{\ge n}$)에 영향을 전혀 주지 않아 고려하지 않는다.

2). 이전의 어떤 결과($X_{<n}$)도 이후 결과($X_{\ge n}$)에 동일한 영향을 주기 때문에 고려하지 않는다.

 

이때, 놓치지 말아야 할 두 가지가 있다.

첫번째: $X_i$에서 일어날 수 있는 사건(=state)은 $S=\{1, \cdots, m\}$이다. 즉, $S$ 외의 사건은 일어날 수 없다.

두번째: $X_{\ge n}$이 일어나기 전 $X_{<n}$이 반드시 일어나야 한다.

시간 흐름에 따라 $X_{<n}$이 일어나고 $X_{\ge n}$이 일어나는 것이 자연스럽고 당연한 것이기 때문이다.

---

이해를 돕기 위해, 예시를 살펴보겠다.

1. 이전 가위바위보 결과는 이후 가위바위보 결과에 영향을 전혀 주지 않는다. 수식은 다음과 같다.

$P(X_2=$이후 가위바위보 결과$|X_1=$이전 가위바위보 결과$) = P(X_2=$이후 가위바위보 결과$)$

 

위 수식을 보고, "$X_1$ 시간대에 어떤 가위바위보 결과도 이후 가위바위보 결과에 영향을 주지 않는다"

혹은 "$X_1$ 시간대에 어떤 가위바위보 결과도 이후 가위바위보 결과에 동일한 영향을 준다"

라고 해석하는 것이 좋다.

더 나아가, "$X_1$ 시간대에 가위바위보를 안해도 이후 가위바위보 결과에 영향을 주지 않는다"

라고 해석해도 큰 무리는 없다. 왜냐하면, 이전 결과가 이후 결과에 전혀 영향을 주지 않기 때문이다.

하지만, 엄밀히 말하자면 이는 틀린 해석이다.

$X_1$ 시간대에는 가위바위보라는 사건이 발생해야 한다고 가정했기 때문에, 가위바위보를 안한다는 것은 모순이다.

하지만, "$X_1$ 시간대의 $S$(=가위바위보) 이외의 어떠한 사건도 이후 결과에 영향을 주지 않는다"

라고 해석하는 것은 바람직하지 않다.

왜냐하면, 이전 가위바위보 결과가 영향을 안 주는 것이지, 그 외의 사건은 줄 수 있기 때문이다.

 

그럼 의문이 들 수 있다.

어떻게 $P(X_2=$이후 가위바위보 결과$|X_1=$이전 가위바위보 결과$)$를

$P(X_2=$이후 가위바위보 결과$)$로 바꿀 수 있는가?

모든 $X_i$ 시간대에는 가위바위보 외의 사건은 발생하지 않고, 오직 가위바위보 사건이 발생해야 한다고 가정했다.

때문에, $X_1$이 수식에 보이지 않더라도 $X_2$전 $X_1$에는 가위바위보 사건이 무조건 일어난다.

하지만, $X_1$ 사건이 $X_2$에 영향을 전혀 주지 않기 때문에 $X_1$을 생략할 수 있다. 즉, 고려하지 않아도 무방하다.

---

2. 수능 시작 한 시간 전 "국어/수학 요약 노트 공부"는 수능 점수에 영향을 준다.

하지만, 국어/수학 배분 시간을 어떻게 주던 점수에 똑같은 영향을 준다.

$P(X_3=$수능 점수$|X_2=$당일 컨디션, $X_1=$국어/수학 공부 배분 시간$) = P(X_3=$수능 점수$|X_2=$당일 컨디션$)$

 

위 수식을 보고, "어떤 국어/수학 공부 배분 시간으로 공부해도 동일한 수능 점수를 받는다"

라고 해석하는 것이 좋다.

하지만, "어떤 국어/수학 공부 배분 시간으로 공부해도 수능 점수에 영향을 전혀 주지 않는다"

라고 해석하는 것은 바람직하지 않다.

공부는 수능 점수에 영향을 준다고 가정했기 때문이다.

뿐만 아니라, "$X_1$ 시간대에 공부를 안해도 같은 수능 점수를 받는다"

라고 해석하는 것은 바람직하지 않다.

$X_1$ 시간대에는 공부 이외의 사건은 발생하지 않는다고 가정했기에, 공부를 안한다는 것은 모순이다.

 

그럼 의문이 들 수 있다.

어떻게 $P(X_3=$수능 점수$|X_2=$당일 컨디션, $X_1=$국어/수학 공부 배분 시간$)$를

$P(X_3=$수능 점수$|X_2=$당일 컨디션$)$로 바꿀 수 있는가?

$X_1$ 시간대에는 공부 외의 사건은 발생하지 않고, 오직 공부 사건이 발생해야 한다고 가정했다.

때문에, $X_1$이 수식에 보이지 않더라도 $X_{>1}$전 $X_1$에는 공부 사건이 무조건 일어난다.

하지만, 어떤 $X_1$ 사건도 $X_3$에 같은 영향을 주기 때문에 $X_1$을 생략할 수 있다. 즉, 고려하지 않아도 무방하다.

---

위 두 예시를 통해 알 수 있듯이, (관점1)은 (관점2)를 포용할 수 있지만, (관점2)는 (관점1)를 포용할 수 없다.

(영향을 전혀 주지 못한다 = 모든 사건은 0의 영향력을 가지고 있다 = 모든 사건은 동일한 영향을 준다)

다시 말해, (관점1)는 해석 범위가 넓은 반면, (관점2)는 해석 범위가 매우 좁다.

(관점1)은 (관점2)로 해석될 수 있을 뿐만 아니라, "$X_{<n}$에 아무것도 안한 것"으로 해석할 수 있다.

---

2. $n$-Step Transition Probabilities

$n$-step transition probabilities $r_{ij}(n)$은 현재 state($X_0$)가 $i$일 때, $n$번의 action 이후의 state($X_n$)가 $j$일 확률을 의미한다.

즉, $r_{ij}(n) = P(X_n=j|X_0=i)$로 표현할 수 있으며, 다음과 같이 구할 수 있다.

$$r_{ij}(n) = \begin{cases} p_{ij}, & \mbox{if }n=1 \\ \sum_{k=1}^m r_{ik}(n-1)p_{kj}, & \mbox{if }n>1 \end{cases}$$

뿐만 아니라, $n$-step transition probability matrix $\underset{m\times m}P^n$으로, $r_{ij}(n) = \left( \underset{m\times m}P^n\right)_{ij}$을 구할 수 있다.

3. Classification of States

Terminology

State $j$ is accessible from a state $i$, if $r_{ij}(n) > 0$.

$A(i)$ is state set that are accessible from $i$.

State $i$ is recurrent if for every $j$ that is accessible from $i$, $i$ is also accessible from $j$.

that is, for all $j$ that belong to $A(i)$ we have that $i$ belongs to $A(j)$.

State $i$ is transient if it is not recurrent.

 

Markov Chain Decomposition

· A Markov chain can be decomposed into one or more recurrent classes, plus possibly some transient states.

· A recurrent state is accessible from all states in its class,

but is not accessible from recurrent states in other classes.

· A transient state is not accessible from any recurrent state.

· At least one, possibly more, recurrent states are accessible from a given transient state.

 

Periodicity

Recurrent class는 다음과 같이 두 종류(1. periodic, 2. aperiodic)로 나눌 수 있다. 

 

A recurrent class is said to be periodic if its states can be grouped in d > 1 disjoint subsets $S_1, \cdots, S_d$

so that all transitions from one subset lead to the next subset. More precisely,

$$\text{if } i \in S_k \text{ and } p_{ij} > 0, \quad \text{then} \ \begin{cases} j \in S_{k+1}, & \mbox{if } k = 1, \cdots, d-1, \\ j \in S_1, & \mbox{if } k = d. \end{cases}$$

A recurrent class that is not periodic, is said to be aperiodic.

preoidic class

4. Steady-State Behavior

두 예외 상황을 제외하면, $r_{ij}(n)$은 특정 값으로 수렴할 뿐만 아니라, 초기 state(=$i$)가 달라도 같은 수렴값을 갖는다.

예외 상황1. multiple recurrent classes: 특정 값으로 수렴하지만, 초기 state(=$i$)에 따라 수렴값(=극한값)이 달라진다.

예외 상황2. periodic class: 초기 state(=$i$)이 달라도 같은 값을 가지지만, 수렴하지 않고 진동한다.

통상적으로, 수렴값(steady-state value)을 $\pi_j$로 표기하며, "$\pi_j \approx P(X_n=j)$ when $n$ is large"로 표현할 수 있다.

 

Steady-State Convergence Theorem

Consider a Markov chain with a single recurrent class, which is aperiodic. Then, the states $j$ are associated with steady-state probabilities $\pi_j$ that have the following properties.

(a) For each $j$, we have

         $\lim_{n \rightarrow \inf} r_{ij}(n) = \pi_j, \quad \mbox{for all } i$.

(b) The $\pi_j$ are the unique solutionto the system of equations below:

        $\pi_j = \sum_{k=1}^m \pi_k p_{kj}, \quad j = 1, \cdots, m$

        $1 = \sum_{k=1}^m \pi_k$

(c) We have

        $\pi_j=0$, for all transient states $j$,

        $\pi_j>0$, for all recurrent states $j$.