이산 마코프 체인

이산 마코프 체인

정의

상태공간가산집합이면서 다음을 만족하는 이산적 확률과정 $\left\{ X_{n} \right\}$ 를 이산 마코프 체인DTMC 혹은 간단히 마코프 체인Markov Chain, MC이라고 한다. $$ p \left( X_{n+1} = j \mid X_{n} = i , X_{n-1} = k , \cdots , X_{0} = l \right) = p \left( X_{n+1} = j \mid X_{n} = i \right) $$

같이보기

설명

$p_{ij}:= p \left( X_{n+1} = j \mid X_{n} = i \right)$ 을 전이 확률Transition Probability이라 하며 현재 상태를 의미하는 $i$ 를 소스 스테이트Source State , 목표 상태를 의미하는 $j$ 를 타겟 스테이트Target State라고 한다. $k$ 스텝 뒤의 전이 확률은 $p_{ij}^{(k)}: = p \left( X_{n+k} = j \mid X_{n} = i \right)$ 과 같이 나타낸다.

마코프 체인이란 이제까지의 역사를 다 알 때 다음 스텝의 확률과 현재만 알고 있을 때 다음 스텝의 확률이 같은 확률 과정을 말한다. 쉽게 말해, 현재 상태만 정확히 알고 있다면 과거가 미래에 영향을 미치지 못하는 확률과정이다. 흔히 이런 성질을 무기억성Memorylessness이라고 부른다. 당연히 이러한 가정이 있다면 계산이든 무엇이든 굉장히 편해진다.

예를들어 강수확률에 대한 모형을 마코프 체인으로 나타낸다고 생각해보자. 어제 비가 왔든 오지 않았든 내일의 강수확률은 오늘 비가 왔는지 오지 않았는지에만 영향을 받는다고 가정해보자. 비가 온 상태를 $0$, 비가 오지 않은 상태를 $1$ 이라 하고 $$\begin{matrix} p_{00} = 0.7 & p_{01} = 0.3 \\ p_{10} = 0.4 & p_{11} = 0.6 \end{matrix}$$ 이라 하자. 이는 오늘 비가 왔다면 내일도 비가 올 확률이 $70 %$ 이고 비가 안 올 확률이 $30 %$, 오늘 비가 안 왔다면 내일도 비가 안 올 확률이 $60 %$ 이고 비가 올 확률이 $40 %$ 라는 뜻이다.

이제 $$P:= \begin{bmatrix} p_{00} & p_{01} \\ p_{10} & p_{11} \end{bmatrix} = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix}$$ 와 같은 행렬을 통해서 이러한 확률계산을 간단하게 해보도록 하자. 이러한 행렬을 전이 확률 행렬이라 부르고, $k$ 스텝 뒤의 전이 확률 행렬을 $P^{(k)}:= \left( p_{ij}^{ ( k ) } \right)$ 와 같이 나타낸다. 전이 확률 행렬의 유용한 성질로써 $P^{(n)} = P^{n}$ 임을 채프만-콜모고로프 방정식을 통해 증명해낼 수 있다.

만약 오늘 비가 왔다면 이틀 뒤의 강수 확률은 $$ \begin{align*} P^{ (2) } =& P^{2} \\ =& \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \\ =& \begin{bmatrix} 0.61 & 0.39 \\ 0.52 & 0.48 \end{bmatrix} \end{align*} $$ 이고 $p_{00}^{(2)} = (0.7)^2 + (0.3) (0.4) = 0.61$ 로 정확하게 일치한다. 보통 우리가 관심이 있는 문제들은 이보다 복잡하고 비교적 먼 미래에 관심이 있으니, 이런 행렬을 다루는 것은 필수적임을 알 수 있다.

전이 확률 행렬의 수식적 정의

참고로 전이확률행렬에서 같은 행의 성분을 모두 더하면 반드시 $1$ 이인데, 당연하지만 다음 스텝의 확률을 모두 더하면 $1$ 이기 때문이다. 수식으로 나타내면 $\displaystyle \sum_{j} p_{ij} = 1$ 과 같다. 확률과정론을 어디서 공부하느냐에 따라 아예 이 성질을 정의로 받아들일 수도 있다.

댓글