# 마르코프 행렬 (Markov Matrix)

#### 마르코프 행렬의 정의

마르코프 행렬(Markov Matrix)은 확률론에서 중요한 역할을 하는 개념으로, 확률 전이 행렬(Transition Matrix)이라고도 불린다. 마르코프 행렬은 주어진 상태에서 다른 상태로의 전이 확률을 나타내는 행렬로, 모든 원소가 0 이상이고, 각 행의 원소 합이 1이 되는 조건을 만족한다.

이러한 마르코프 행렬은 주로 마르코프 연쇄(Markov Chain)의 전이 확률을 표현하는 데 사용되며, 시간에 따라 변하지 않는 전이 확률을 가지는 마르코프 연쇄의 경우 고정된 마르코프 행렬이 주어진다.

#### 마르코프 행렬의 수학적 성질

**확률 보존의 특성**

마르코프 행렬 $ P $는 각 상태에서 다른 상태로 전이할 확률을 표현한다. 이를 수학적으로 표현하면, $ P $의 각 원소 $ P\_{ij} $는 상태 $ i $에서 상태 $ j $로 전이할 확률을 의미하며, 다음과 같은 조건을 만족한다:

$$
P\_{ij} \geq 0, \quad \forall i,j
$$

$$
\sum\_{j} P\_{ij} = 1, \quad \forall i
$$

첫 번째 조건은 모든 전이 확률이 음수가 아니어야 한다는 것이며, 두 번째 조건은 각 상태에서 모든 가능한 전이 확률의 합이 1임을 나타낸다. 이러한 특성은 확률 보존의 법칙을 따르는 것이다.

**스펙트럼 분석과 고유 벡터**

마르코프 행렬 $ P $는 특성 방정식 (Characteristic Equation) $ |\lambda I - P| = 0 $의 근으로 고유값을 갖는다. 특히, 1은 항상 $ P $의 고유값 중 하나이며, 그에 대응하는 고유 벡터는 정상 상태(Stationary Distribution)를 나타낸다.

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

$$
\pi P = \pi
$$

이 벡터는 상태가 시간에 따라 변하지 않는 확률 분포를 나타내며, 마르코프 연쇄가 충분히 오래 지속되었을 때 도달하는 상태를 의미한다. 고유값 $ \lambda = 1 $에 대응하는 고유 벡터 $ \pi $는 항상 존재하며, 추가적인 고유값들은 $ |\lambda| \leq 1 $을 만족한다.

**비가역적 마르코프 행렬**

마르코프 행렬은 대개 가역적(Reversible)이라고 가정되지만, 모든 마르코프 행렬이 가역적인 것은 아니다. 가역적인 마르코프 행렬은 Detailed Balance Condition을 만족하는데, 이는 다음과 같이 표현된다:

$$
\pi\_i P\_{ij} = \pi\_j P\_{ji}
$$

하지만, 비가역적인 마르코프 행렬도 존재하며, 이러한 행렬에서는 시간에 따른 상태 전이의 비대칭성이 발생한다. 이러한 경우, 일반적으로 $ P $의 고유값 분포는 더 복잡해지며, 정상 상태에 도달하는 과정에서 특수한 행태를 보일 수 있다.

#### 마르코프 행렬의 계산과 활용

**행렬의 거듭제곱과 시간에 따른 전이 확률**

마르코프 행렬 $ P $의 $ n $제곱 $ P^n $은 $ n $번의 전이 후의 상태 분포를 나타낸다. 즉, 초기 상태 분포 벡터 $ \mathbf{x}\_0 $가 주어졌을 때, $ n $ 단계 후의 상태 분포는 다음과 같이 계산된다:

$$
\mathbf{x}\_n = \mathbf{x}\_0 P^n
$$

이 계산을 통해 시간에 따라 상태가 어떻게 변하는지를 추적할 수 있으며, 이는 마르코프 연쇄의 장기 거동을 이해하는 데 매우 중요한 역할을 한다.

**마르코프 행렬의 수치적 계산**

마르코프 행렬의 고유값 및 고유 벡터는 일반적으로 수치적 방법으로 계산된다. 이러한 계산에는 QR 알고리즘, 멀티그리드 방법, 또는 파워 반복(Power Iteration)과 같은 방법이 사용될 수 있다. 특히, 큰 규모의 마르코프 행렬에 대해선 수렴 속도와 계산 복잡도를 고려한 효율적인 알고리즘이 필요하다.

또한, 마르코프 행렬의 일부 구조적 특성을 활용하여 계산 효율성을 높일 수 있다. 예를 들어, 희소 행렬(Sparse Matrix)의 경우, 대부분의 원소가 0이므로 비희소 원소만을 저장하고 계산하는 방법으로 메모리와 시간 복잡도를 줄일 수 있다.

#### 마르코프 행렬의 안정성과 수렴 특성

**에르고딕성과 비에르고딕성**

마르코프 행렬의 에르고딕성(Ergodicity)은 연쇄가 결국 모든 상태를 방문할 수 있는지를 나타내는 중요한 특성이다. 에르고딕 마르코프 행렬은 장기적으로 특정 상태에 수렴하는 경향이 있으며, 그 결과 고유값 $ 1 $에 대응하는 고유 벡터로 수렴하게 된다.

반면, 비에르고딕(non-ergodic) 행렬은 모든 상태를 방문하지 못하거나, 일부 상태에 갇혀버리는 성질을 갖는다. 이러한 행렬은 복수의 고유값 $ 1 $을 가질 수 있으며, 여러 개의 고유 벡터로 수렴하게 된다.

**수렴 속도와 혼합 시간**

마르코프 연쇄의 수렴 속도는 고유값의 크기와 밀접한 관련이 있다. 고유값 $ \lambda\_2 $가 $ 1 $에서 멀어질수록 수렴 속도가 빠르게 된다. 수렴 속도를 측정하는 지표로는 혼합 시간(Mixing Time)이 사용되며, 이는 초기 상태에서 정상 상태에 도달하기까지 필요한 시간의 척도이다.

혼합 시간은 주로 $ \lambda\_2 $의 크기에 따라 결정되며, $ \lambda\_2 $가 $ 1 $에 가까울수록 혼합 시간은 길어지게 된다. 이를 통해, 마르코프 행렬의 설계와 분석 시 연쇄의 수렴 속도를 조절하거나 예측할 수 있다.

***

관련 자료:

* Norris, J. R. (1998). *Markov Chains*. Cambridge University Press.
* Levin, D. A., Peres, Y., & Wilmer, E. L. (2009). *Markov Chains and Mixing Times*. American Mathematical Society.
* Meyn, S. P., & Tweedie, R. L. (2009). *Markov Chains and Stochastic Stability*. Cambridge University Press.