[Markov Chains] Basic Concepts (마르코프 체인 개념)

Markov Chains

Introduction

어떤 process가 각 시간마다 값을 가진다고 하자. \( X_n \)을 시간 \( n \)에서의 값이라고 할 때, 연속적인 값 \( X_0, X_1, X_2, \dots \)에 대한 확률 모델을 만들어보자.

아주 간단한 모델로, \( X_n \)이 독립적인 확률변수라고 가정할 수 있지만, 이런 가정은 확실히 부적절하다.

 

예를 들어, \( X_n \)이 어떤 증권(구글 주식 등)의 \( n \) 추가 거래일 종료시점의 가격이라 하자.

그런데 \( X_{n+1} \)가 \( X_0, X_1, \dots, X_n \)과 독립이라고 가정하는것은 타당하지 않을 것이다.

만약 주식의 종가가 이전 종가에만 의존한다고 가정하는 것은 합리적일 수 있다.

즉, \( X_{n+1} \)의 조건부 분포가 과거의 모든 \( X_0, X_1, \dots, X_n \)에 의존하는 것이 아니라, \( X_n \)에만 의존한다고 가정할 수 있다.

 

이러한 가정은 Markov Chain을 정의히며, 확률 과정의 한 유형이다.

 

Markov Chains and Notation

\( \{X_n, n=0, 1, 2, \dots \} \)을 유한하거나 셀 수 있는 개수의 가능한 값들을 가지는 확률과정이라고 하자.

별도의 언급이 없는 한, 가능한 값들은 음이 아닌 정수들의 집합 \( \{ 0, 1, 2, \dots \} \)이라 하자.

만약 \( X_n = i \)라 하면, 시간 \( n \)에서 이 과정이 상태 \( i \)에 있다고 한다.

 

상태 \( i \)에 있을 때, 고정된 확률 \( P_{ij} \)로 다음 상태가 \( j \)가 된다고 하자. 즉

\[ P_{ij} = P(X_{n+1} = j \mid X_n = i,\ X_{n-1}=i_{n-1},\ \dots, X_1 = i_1, X_0 = i_0) \]

모든 상태 \( i_0, i_1, \dots, i_{n-1}, i, j \)와 \( n \ge 0 \) 에서 성립한다고 가정하자.

이러한 확률 과정을 Markov Chain(마르코프 체인, 마코프 연쇄)이라고 한다.

책에 따라 \( P_{ij} \)를  \( P(i, j) = P(X_{n+1} = j \mid X_n = i) \)로 나타낼 수 있다. 

위 식은 다음 의미를 갖는다.

• 마르코프 체인에서 조건부 분포 \( X_{n+1} \) (미래 상태)는 \( X_0, X_1, \dots, X_{n-1} \) (과거 상태) 와 \( X_n \) (현재 상태)에 따라 결정된다.
• 하지만 이 분포는 과거 상태와 독립이고, 오직 현재 상태 \( X_n \)에만 의존한다.

확률 \( P_{ij} \)는 상태 \( i \)에서 상태 \( j \)로 전이(transition)할 확률이다.

확률의 성질과 확률과정의 정의에 따라 다음이 성립한다.

• \( P_{ij} \ge 0 \)
• \( \sum_{j=0}^{\infty} P_{ij} = 1 \)

\( \mathbf{P} \) 또는 \( P \) 는 전이확률 \( P_{ij} \)를 원소로 하는 행렬이고, 1단계 전이 확률 행렬(one-step transition probability matrix), 또는 간단히 전이확률행렬, 전이행렬(transition matrix)이라 한다.

\[
P =
\begin{bmatrix}
P_{00} & P_{01} & P_{02} & \cdots \\
P_{10} & P_{11} & P_{12} & \cdots \\
\vdots & \vdots & \vdots & \ddots \\
P_{i0} & P_{i1} & P_{i2} & \cdots \\
\vdots & \vdots & \vdots & \ddots \\
\end{bmatrix}
\]

 

※ 전이행렬 \( P \)의 각 행의 합은 \( 1 \)이어야 한다.

※ 경우에 따라 전이행렬을 \( T \)로 표기할 수 있다.

Example: Weather

어떤 지역의 날씨는 rainy와 not rainy 두 개의 상태만 존재한다고 하자.

오늘 비가 왔을 때, 내일도 비가 올일 확률이 \( \alpha \)라 하자. 

그리고 오늘 비가 오지 않았을 때, 내일도 비가 오지 않을 확률을 \( \beta \)라 하자.

비가 오는 상태와 비가 오지 않는 상태를 각각 0과 1로 표기하자.

이때의 전이확률은 

\[ P = \begin{bmatrix} \alpha & 1 - \alpha \\ \beta & 1 - \beta \\ \end{bmatrix} \]

이다.

 

Example: Process into Markov Chain

오늘 비가 오는지 여부가 지난 두 날의 조건에 따라 결정된다고 가정하자.

• 지난 이틀 동안 비가 왔다면, 내일 비가 올 확률은 0.7이다
• 오늘 비가 오고 어제는 오지 않았다면, 내일 비가 올 확률은 0.5이다
• 어제 비가 왔지만 오늘 비가 오지 않았다면, 내일 비가 올 확률은 0.4이다
• 지난 이틀 동안 비가 오지 않았다면, 내일 비가 올 확률은 0.2이다.

시간 \( n \)에서의 상태를 \( n \)에 비가 오는지 여부만으로 정의하면 위 모델은 마르코프 체인이 될 수 없다.

그러나 하루와 그 전날의 날씨 조건에 따라 시간 \( n \)의 상태를 정의하면, 마르코프 체인으로 바꿀 수 있다.

• 상태 0: 어제와 오늘 모두 비가 왔음
• 상태 1: 어제는 비가 오지 않고, 오늘 비가 왔음
• 상태 2: 어제 비가 왔지만, 오늘 비가 오지 않음
• 상태 3: 어제와 오늘 모두 비가 오지 않음

이렇게 상태를 정의하면, 전이확률행렬은 다음과 같다.

\[ P = \begin{bmatrix} 0.7 & 0 & 0.3 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.4 & 0 & 0.6 \\ 0 & 0.2 & 0 & 0.8 \\ \end{bmatrix} \]

 

Example: Random Walk Model

마르코프 체인의 상태공간이 정수 \( i = 0, \pm 1, \pm 2, \dots \)로 주어지고, \( 0 < p < 1 \)인 어떤 \( p \)에 대하여

\[ p = P_{i, i + 1} = 1 - P_{i, i - 1} \] 

이면 랜덤워크(Random Walk)라고 한다.

한 직선 위에서 움직이는 점이 확률 \( p \)로 오른쪽으로 이동하거나, 확률 \( 1 - p \)로 왼쪽으로 이동하는 모델링이다.

 

Example: Gambling Model

도박사가 매 도박게임마다 \( p \)의 확률로 1원을 얻고, \( 1 - p \)의 확률로 1원을 잃는다고 하자.

도박사가 전재산을 잃거나 또는 재산이 N원에 도달하면 게임을 그만둔다고 한다.

이때의 도박사의 재산은 다음과 같은 전이확률을 가지는 마르코프 체인이 된다.

\[ P_{i, i+1} = 1 - P_{i, i-1} = p \ (i = 1, 2, \dots, N-1), \quad P_{00} = P_{NN} = 1 \]

여기서 상태 0과  N은 흡수 상태(absorbing state)라고 하고, 한번 이 상태에 들어가면 절대 벗어날 수 없다.(상태를 바꿀 수 없다)

위 모델은 흡수 장벽(absorbing barrier)를 가지는 유한 상태 랜덤 워크(finite state random walk)의 한 예시이다.