Statistics

행렬 응용 : 마코프 체인 (Markov Chain)

sara2601 2022. 5. 1. 12:22

▶Markov Chain 

  • 마코프 체인(Markov Chain)이란, Markov Property(마코프 성질)을 지닌 이산확률과정을 가리킨다. 
  • 임의의 $x_0, x_1, \cdots, x_n$과 집합 $A$에 대하여, 다음의 마코프 성질(Markov Property) $$ P(X_{n+1} \in A | X_0 = x_0, X_1 = x_1, \cdots, X_n = x_n) = P(X_{n+1} \in A | X_n = x_n) $$ 이 성립할 때, 확률과정 $\{X_n, n \geq 0\}$을 마코프 과정(Markov Process)라 부른다.
  • 즉, 마코프 성질이란 $n+1$회의 상태(state)는 단지 $n$회에서의 상태, 혹은 그 이전 일정 기간의 상태에만 영향을 받는 것을 의미한다. 
  • ex. 확률과정 $\{X_n, n \geq 0\}$이 독립과정이면, 마코프 과정이다. $$
    P(X_{n+1} \in A | X_0 = x_0, \cdots, X_n = x_n) = P(X_{n+1} \in A) = P(X_{n+1}\in A | X_n = x_n)
    $$. 따라서 동전던지기는 독립 시행이기 때문에 $n$번째 상태가 앞이던 뒤던 상관없이 $n+1$번째 상태에 영향을 주지 않는다. 
  • ex2. 확률과정 $\{X_n, n \geq 0\}$이 독립과정일 때, $S_n = X_0 + X_1 + \cdots + X_n$으로 주어지는 부분합 과정 $\{S_n, n\geq 0\}$도 마코프 과정이다. $$
    \begin{align*}
    P(S_{n+1} \in A &| S_0 = s_0, S_1 = s_1, \cdots, S_n = s_n) \\ &= P(X_{n+1} + s_n \in A | S_0=s_0, S_1 = s_1, \cdots, S_n = s_n) \\ 
    &=  P(X_{n+1} + s_n \in A ) \\ 
    &= P(X_{n+1} + s_n \in A | S_n = s_n) = P(S_{n+1} \in A | S_n = s_n)
    \end{align*}
    $$

▶ 마코프 모델 (Markov Model)

  • 마코프 모델은 위의 가정 하에 확률적 모델을 만든 것으로써, 가장 먼저 각 상태를 정의함. 
  • 상태(state) : $S= \{s_1, \cdots, s_n\}$로 정의하면, $n$개의 상태가 존재함. 
  • 상태 전이 확률(State Transition Probability) : 각 상태에서 각 상태로 이동할 확률. 
  • 앞으로 상태전이확률을 아래와 같이 표현하도록 한다.
    $$\begin{align*}p_{ij} &= P(X_{n+1} =s_j | X_n = s_i) \\ p_{ij} &\geq 0 \quad and \quad \sum_{j=1}^{n} p_{ij} = 1 \end{align*}$$
  • $p_{ij}$를 원소로 갖는 행렬을 $P$로 나타내고, 이 행렬을 전이확률행렬(또는 추이확률행렬)이라 부른다.
  • 또, 상태와 상태 전이 확률을 정리해 상태 전이도(state transition diagram)으로 표현 가능하다. 

https://sites.google.com/site/machlearnwiki/RBM/markov-chain

  • 만약 날씨를 마코프 체인으로 모델링한다면, 아래와 같다. 각 노드는 상태(state), 엣지는 전이(transition)을 가리킨다. 각 노드 별 전이확률의 합은 1이 된다. (ex. $a_{01} + a_{02} + a_{03} = 1$) 상태에는 일반적 종류의 상태(HOT, COLD, WARM) 이외에 시작(start)와 끝(end)상태도 존재한다. 

https://ratsgo.github.io/machine%20learning/2017/03/18/HMMs/

  • ex) 1차 마코프 가정을 이용해 확률을 계산해보자. 
오늘의 날씨 내일 날씨
Sunny Rain Cloud
Sunny 0.8 0.05 0.15
Rain 0.2 0.6 0.2
Cloud 0.2 0.3 0.5

→ 상태(State) : $S = \{Sunny, Rain, Cloud\}$

→ 오늘 날씨($q_1$) = 'Sunny'일 경우, 내일 날씨($q_2$)가 Sunny가 되고, 모레 날씨($q_3$)가 "Rain"일 확률을 계산해 보자. $$\begin{align*} P(q_2 &= Sunny, q_3 = Rain | q_1 = Sunny) \\ &= P(q_3 = Rain |q_2 = Sunny, q_1 = Sunny) \times P(q_2 = Sunny | q_1 = Sunny) \\ &= P(q_3 = Rain | q_2 = Sunny) \times P(q_2 = Sunny | q_1 = Sunny) \quad \textrm{by Markov Assumption} \\ &= 0.05 \times 0.8 = 0.04 \end{align*}$$ 

 

  • ex2) Gambler's Ruin : 갑과 을이 동전 하나를 계속 던지는 게임을 한다. 동전을 던질때마다 앞면이 나오면 갑이 을로부터 1단위 돈을 받고(갑:+1, 을:-1), 뒷면이 나오면 갑이 을에게 1단위 돈을 준다. (갑:-1, 을:+1) 갑이 최초로 가지고 있는 돈을 $S_0 = k$, 을이 가지고 있는 최초의 금액을 $N-k$라고 하자. 각 게임에서 갑이 얻게 되는 수입을 $X_i$, $n$번 게임 직후의 갑의 보유 금액을 $S_n = S_0 + X_1 + \cdots + X_n$이라 하면, $S_n = 0$ 또는 $S_n = N$이면 게임이 더 이상 진행되지 않는다. 

→ 상태(State) : $S = \{0, 1, \cdots, N\}$

→ 전이행렬 $P$ : $$ p_{ij} = \left\{\begin{matrix} p & S_j = S_i+1, 0 < S_i < N \\ 1 - p & S_j=S_i-1, 0 < S_i < N \\ 
1 & S_i = S_j = 0, \,\, or \,\, S_i=S_j=N, \\ 0 & else  \end{matrix}\right. $$

 

▶ 마코프 체인과 시뮬레이션 

  • ex) Coffee : 커피를 즐기는 어떤 사람이 매일 인근의 북카페 A와 B 두 곳 중 한곳에 들러 커피를 마신다고 하자. 이사람이 두 곳의 북카페를 선택하는 방식은 확률에 의존하며, 전날 들렀던 북카페와 같은 곳에서 1/3의 확률로, 2/3확률로 다른 북카페에 간다고 가정하며, 그 이전에 어떤 북카페에서 커피를 마셨는지는 아무런 영향을 주지 않는다고 가정하자. 

→ 북카페를 선택하는 방식은 마코프 체인을 따르며, 전이확률(transition probability)는 다음과 같다 : 

$$
\begin{align*}
P(X_{n+1} = A | X_n = A) &= 1/3 \\
P(X_{n+1} = B | X_n = A) &= 2/3 \\ 
P(X_{n+1} = A | X_n = B) &= 2/3 \\
P(X_{n+1} = B | X_n = B) &= 1/3 \\
\end{align*}
$$

that is, 

$$
\begin{align*}
\begin{array}{c c} &
\begin{array}{c c } A & B  \\
\end{array}
\\
\begin{array}{c c}
A \\
B \\
\end{array}
&
\left[
\begin{array}{c c}
1/3 & 2/3 \\
2/3 & 1/3 \\
\end{array}
\right]
\end{array}
\end{align*}
$$

→ 위 전이행렬을 이용해서 이 사람이 선택하는 북카페에 대해 모의실험을 수행할 수 있다. 

import numpy as np
import pandas as pd

Pmat = np.array([[1/3, 2/3], [2/3, 1/3]])

def Markovchain_sim(n, Pmat, x0):
	sim = []
	m = Pmat.shape[1]
	sim.append(x0)

	lst = [0, m-1]
	for i in range(1, n):
		nextstate = np.random.choice(lst, 1, p = Pmat[sim[i-1], :]) # sample 
		sim.extend(nextstate)
	return sim

print(Markovchain_sim(12, Pmat, 0))
# [0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]
  • 체프만-콜모고로프 방정식(Chapman-Kolmogorov Equation) : 

→ 이산적 확률과정 하에서, 다음이 성립한다. $$ p_{ij}^{(n+m)} = \sum_k p_{ik}^{(n)}p_{kj}^{(m)}, \quad P^{(n + m)} = P^{(n)} + P^{(m)}$$ 즉, state $i$에서 $j$로 갈 때 까지 걸리는 $n+m$ 스텝을 $n$과 $m$으로 쪼개어 표현할 수 있다는 뜻이다. 

→ 따라서, 상태 $i$에서 출발하여, $m$ 시차에서 $j$에 닿을 확률 $p_{ij}^{(m)}$은 전이확률행렬의 곱으로부터 얻어진다. $$P^{(m)} = P \cdots P = P^m, \quad P^{(m)} = (p_{ij}^{(m)})$$

  • 마코프 체인(마코프 연쇄/사슬)의 상태 $i$에서 출발하여, 2번의 전이 후 $j$에 닿는 경로는 $$ X_t = i \rightarrow X_{t+1} = k(=1, 2, \cdots, s) \rightarrow X_{t+2} = j $$ 로 표현되고, 전이확률 $p_{i,j}^{(2)}$는 다음과 같이 계산된다. $$ p_{i,j}^{(2)} = P\{X_{t+2} = j | X_t = i\} = \sum_{k=1}^s p_{ik}p_{kj}, \quad P^{(2)} = PP = P^2 \therefore P^{(2)} = (p_{ij}^{(2)})$$. 이를 활용해 모의실험 및, 몇일 후 j가 될 확률 등을 계산할 수 있다.
  • 일반적으로, 마코프 체인 $X_0, X_1, \cdots$는 동일한 분포를 가진 확률 변수들이 아니고, $X_n$의 marginal distibution는 $n$단계 전이행렬 $P^n$과 초기 분포 $\boldsymbol{\alpha} = (\alpha_0, \cdots \alpha_N), \alpha_i = P(X_0= i)$에 의존한다. $$ P(X_n = j) = \sum_i P(X_n = j | X_0 = i) P(X_0 = i) = \sum_i p_{ij}^n \alpha_i = \alpha P^n$$.
  • ex2) 파산문제: 갑이 최초 \$3의 돈을 가지고 있고, \$8의 금액을 얻거나 가진 돈을 모두 잃을 때 까지 게임을 한다고 가정해 보자. 매번 게임에서 이길 확률을 0.6, 질 확률을 0.4라 하고 한 번 게임에서 1달러를 얻거나 잃는다고 가정해 보자. 4번의 게임 후 갑이 얻게 되는 기대금액을 계산해보자.
    • 우선, 다음과 같은 전이확률을 갖는 마코프 체인을 구성한다.
      $$
      \begin{align*}
      \begin{array}{c c c c c c c} &
      \begin{array}{c c c c c c c} 0 \,\,\, & 1 \,\,\, & 2 \,\,\, & \cdots \,\,\, & 6 \quad & 7 \quad & 8 
      \end{array}
      \\
      \begin{array}{c c c c c c c}
      0 \\ 1 \\ 2 \\ \vdots \\ 6 \\ 7 \\ 8
      \end{array}
      &
      \left[
      \begin{array}{c c c c c}
      1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
      0.4 & 0 & 0.6 & \cdots & 0 & 0 & 0\\
      0 & 0.4 & 0 & \cdots & 0 & 0 & 0\\
      \\
      0 & 0 & 0 & \cdots & 0 & 0.6 & 0 \\
      0 & 0 & 0 & \cdots & 0.4 & 0 & 0.6 \\
      0 & 0 & 0 & \cdots & 0 & 0 & 1 \\
      \end{array}
      \right]
      \end{array}
      \end{align*}
      $$ 
    • 4번의 게임 후의 기대 금액은 다음과 같이 계산할 수 있다. $$ E(X_4 | X_0 = 3) = \sum_{j=0}^8 jP(X_4 = j|X_0 = 3) = \sum_{j=0}^8 jp_{3, j}^4 $$
# gambler's ruin
p = 0.6; q = 1-p; n = 8
Tpmat = np.zeros((n+1, n+1))
print(Tpmat)

for i in range(1, n):
	Tpmat[i, i-1] = q
	Tpmat[i, i+1] = p

Tpmat[0, 0]= 1
Tpmat[n, n] = 1
print(Tpmat)

Tpmat4 = np.linalg.matrix_power(Tpmat, 4)

lst = list(range(n+1))

print(np.multiply(lst, Tpmat4[3, :]).sum())
# 3.7872
  • 위의 문제를 모의실험을 통해서도 근사적으로 계산할 수 있다.
    $$ E(X_4| X_0=3) \approx \frac{1}{n} \sum_{i=1}^n X_{4, i}, \quad X_{4i} \overset{d}{=} X_4 | X_0 = 3 $$
# simulation : 
M = Tpmat.shape[0]; nsim = 10**5; x = np.zeros(nsim)
x0 = 3; power = 4; 
lst = list(range(0, M))

for j in range(0, nsim):
	temp = x0
	for i in range(0, power):
		temp = np.random.choice(lst, 1, p = Tpmat[temp, : ])[0]
	x[j] = temp

print(x.mean()) # 3.7936

이와 같이 Markov chain을 이용해 simulation으로도, 수식적 계산으로도 initial state로부터 n번째 state 후의 기대값을 알아낼 수 있다.

저작자표시