# 마르코프 체인 (Markov Chain)

#### 마르코프 체인의 기본 개념

마르코프 체인(Markov Chain)은 확률론적 모형의 일종으로, 미래 상태가 현재 상태에만 의존하고 그 이전의 상태들에는 독립적이라는 특징을 가진다. 이를 '마르코프 성질'이라고 하며, 이러한 성질을 만족하는 과정은 마르코프 과정(Markov Process)이라고 한다. 마르코프 체인은 이산적인 상태 공간을 가지는 마르코프 과정의 한 형태이다.

마르코프 체인은 주어진 상태 공간에서 확률 전이 행렬(Transition Probability Matrix)에 의해 정의되며, 이 행렬은 각 상태에서 다른 상태로 전이될 확률을 나타낸다. 확률 전이 행렬의 각 행은 해당 상태에서의 전이 확률을 나타내며, 모든 행의 합은 1이 된다.

마르코프 체인의 가장 중요한 특성은 그 전이 확률이 '시간에 독립적'이라는 점이다. 즉, 전이 확률은 시점에 의존하지 않고 상태에만 의존한다.

#### 상태 공간과 전이 행렬

상태 공간(State Space)은 마르코프 체인의 가능한 모든 상태들의 집합으로, 이 공간은 유한하거나 무한할 수 있다. 상태들은 일반적으로 유한한 개수의 이산적 상태들로 구성되며, 이를 $ S = {s\_1, s\_2, \ldots, s\_n} $이라고 표시할 수 있다.

전이 행렬(Transition Matrix)은 상태들 사이의 전이 확률을 나타내는 행렬로, 각 원소 $ P\_{ij} $는 상태 $ s\_i $에서 상태 $ s\_j $로 전이될 확률을 나타낸다. 수학적으로, $ P\_{ij} = \mathbb{P}(X\_{t+1} = s\_j \mid X\_t = s\_i) $로 표현된다. 이 행렬은 다음과 같은 조건을 만족한다.

$$
P\_{ij} \geq 0, \quad \sum\_{j} P\_{ij} = 1 \quad \text{for all } i
$$

이 행렬의 성질 중 하나는 전이 행렬을 $ n $번 거듭 제곱한 것이, $ n $번의 전이를 통해 상태 $ s\_i $에서 상태 $ s\_j $로 전이될 확률을 나타낸다는 점이다.

#### 마르코프 체인의 분류

마르코프 체인은 다양한 속성에 따라 분류될 수 있다.

1. **시간에 따른 마르코프 체인의 분류**\
   마르코프 체인은 시간의 성질에 따라 이산 시간 마르코프 체인(Discrete-time Markov Chain, DTMC)과 연속 시간 마르코프 체인(Continuous-time Markov Chain, CTMC)으로 분류된다. DTMC는 상태 전이가 이산적인 시간 간격에서 발생하며, CTMC는 상태 전이가 연속적인 시간에서 발생한다.
2. **상태 공간의 크기에 따른 분류**\
   상태 공간이 유한한 경우 유한 마르코프 체인(Finite Markov Chain), 무한한 경우 무한 마르코프 체인(Infinite Markov Chain)으로 분류된다.
3. **가역성(Reversibility)**\
   마르코프 체인은 가역적인 마르코프 체인(Reversible Markov Chain)과 비가역적인 마르코프 체인(Irreversible Markov Chain)으로 분류된다. 가역적인 마르코프 체인은 시간 역전의 관점에서 동일한 전이 확률을 가지며, 이는 Detailed Balance 조건을 만족하는 것으로 정의된다.

#### 마르코프 체인의 안정 상태와 수렴

마르코프 체인의 중요한 연구 주제 중 하나는 체인의 장기적인 행동, 즉 시간이 무한히 흐른 후 체계가 어떤 상태에 도달하는가를 이해하는 것이다. 이러한 상태는 일반적으로 '안정 상태(Steady State)' 또는 '정상 상태(Stationary State)'라고 불린다.

안정 상태 벡터 $ \pi $는 다음 조건을 만족하는 벡터로 정의된다.

$$
\pi P = \pi
$$

여기서 $ \pi $는 모든 요소의 합이 1인 확률 벡터이며, $ P $는 전이 행렬이다. 안정 상태는 마르코프 체인이 수렴할 때 도달하는 상태 분포를 나타낸다.

마르코프 체인의 수렴 여부는 상태 공간의 성질, 특히 체인의 불변성(Ergodicity) 여부에 달려 있다. 만약 체인이 불변적이고 재귀적(Recurrent)이라면, 임의의 초기 상태에서 시작하더라도 시간이 충분히 흐른 후에 체인은 안정 상태에 도달하게 된다.

#### 재귀성과 흡수성

마르코프 체인의 상태는 재귀적(Recurrent) 또는 비재귀적(Transient)일 수 있다. 재귀적 상태는 체인이 해당 상태로 다시 돌아올 확률이 1인 상태를 말하며, 비재귀적 상태는 해당 상태로 다시 돌아올 확률이 1보다 작은 상태를 의미한다.

특히 흡수 상태(Absorbing State)는 일단 체인이 해당 상태에 도달하면 다시 다른 상태로 전이하지 않는 상태를 의미한다. 이러한 상태를 포함한 마르코프 체인은 흡수 마르코프 체인(Absorbing Markov Chain)이라고 불린다. 이 경우, 흡수 상태로의 도달 가능성과 기대 시간이 중요한 연구 주제 중 하나이다.

#### 이론적 배경

마르코프 체인의 기초 이론은 수학자 안드레이 마르코프(Andrey Markov)에 의해 1906년에 처음 소개되었다. 마르코프는 이산 상태 공간을 가지는 확률 과정에 대한 연구를 통해 이 이론을 발전시켰다. 이후 마르코프 체인은 확률론, 통계학, 신호 처리, 경제학 등 다양한 분야에서 널리 연구되고 적용되었다.

마르코프 체인의 수학적 이론은 선형대수학과 밀접하게 관련되어 있다. 특히, 전이 행렬의 고유값과 고유벡터 분석은 체인의 장기적 행동을 이해하는 데 필수적인 도구로 사용된다. 추가적으로, 확률론적 방법론을 통해 마르코프 체인의 다양한 성질을 증명하고 분석할 수 있다.

***

관련 자료:

1. Norris, J.R. (1997). *Markov Chains*. Cambridge University Press.
2. Levin, D.A., Peres, Y., & Wilmer, E.L. (2009). *Markov Chains and Mixing Times*. American Mathematical Society.
3. Durrett, R. (2010). *Probability: Theory and Examples*. Cambridge University Press.