Markov Chains (Discrete, Continuous)

DTMC와 CTMC 상세 정리 (Markov Chain Detailed Summary)

마르코프 연쇄(Markov Chain)는 확률적 과정(Stochastic Process)의 일종으로, 마르코프 속성(Markov Property)을 만족하는 것을 특징으로 합니다.

구분	DTMC (Discrete Time Markov Chain)	CTMC (Continuous Time Markov Chain)
시간 유형	시간이 이산적($n = 0, 1, 2, ...$)으로 진행됨.	시간이 연속적($t \ge 0$)으로 진행됨.
마르코프 속성	다음 상태 $X_{n+1}$는 오직 현재 상태 $X_n$에만 의존하며, 과거 이력($X_0, ..., X_{n-1}$)에는 독립적임.	연속 시간에서 마르코프 속성을 만족함.
상태 전이 방식	특정 시점($n$ 단계)에서 전이가 발생함.	전이까지 걸리는 시간이 확률적으로 결정됨.
전이 시간 분포	(별도 명시 없음. 다음 단계($n+1$)까지의 시간이 1단위로 고정됨).	전이(Transition)가 발생할 때까지 걸리는 시간이 지수 분포(Exponential Distribution)를 따름.

---

I. DTMC (Discrete Time Markov Chain)의 핵심 요소

1. 전이 확률 행렬 및 동적 특성

• 전이 확률 ($p_{ij}$): 상태 $i$에서 다음 단계($n+1$)에 상태 $j$로 이동할 확률을 나타내며, $p_{ij} = P(X_{n+1}=j | X_n=i)$로 정의됩니다.
• 전이 확률 행렬 ($P$): 전이 확률 $p_{ij}$의 집합이며, 모든 행의 합이 1인 확률 행렬 (Stochastic Matrix)입니다.
• $n$-단계 전이 확률: 초기 분포 $\mathbf{a}_0$가 주어졌을 때, $n$단계 후의 상태 분포 $\mathbf{a}_n$은 다음 공식을 통해 계산됩니다:
  $\mathbf{a}_n = \mathbf{a}_0 P^n$
• $n$-단계 전이 행렬: $n$ 단계 후 상태 $i$에서 $j$로의 전이 확률은 행렬 $P$의 $n$제곱, 즉 $P^n_{ij}$로 나타납니다.
• 채프먼-콜모고로프 방정식 (Chapman-Kolmogrov Equation): $(m+n)$ 단계 전이 확률은 $m$ 단계 전이와 $n$ 단계 전이의 조합으로 나타낼 수 있습니다:
  $P^{n+m}_{ij} = \sum_{k \in S} P^n_{ik} P^m_{kj}$

2. 정상 분포 및 수렴 특성

• 정상 분포 ($\pi$, Stationary Distribution): 시간이 지나도 분포가 변하지 않는 상태를 의미하며, 다음 조건을 만족해야 합니다:
  1. $\pi_i \ge 0$ 이고 $\sum \pi_i = 1$.
  2. $\mathbf{\pi = \pi P}$ (흐름 균형 방정식, Flow Balance Equation).
• 극한 확률 (Limiting Probability):
  • 유한 상태 DTMC가 비주기적(Aperiodic)이고 기약적(Irreducible)인 경우, 극한 확률 $lim_{n\to\infty} P^n_{ij} = \pi_j$가 존재하며, 이 극한값은 유일한 정상 분포와 같습니다.
  • 극한 확률이 존재하면, 장기적으로 초기 상태에 관계없이 상태 분포가 $\pi$로 수렴합니다.
• 특수 상황 (주기적/Reducible):
  • 주기적 (Periodic) DTMC: 극한 확률이 존재하지 않으나, 주기($d$)를 사용하여 행렬의 평균($\frac{1}{d}\sum_{k=n+1}^{n+d} P^k$)을 구하면 정상 분포로 수렴합니다.
  • 기약 불가 (Irreducible): 모든 상태가 서로 소통(communicate)할 때 기약적이라고 합니다. 기약적이지 않으면 Reducible하며, 이 경우 정상 분포는 유일하지 않고 무한히 많을 수 있습니다.

---

II. CTMC (Continuous Time Markov Chain)의 핵심 요소

CTMC는 도착(Arrival)이나 서비스 완료(Service Completion)와 같은 사건이 발생할 때마다 상태 전이가 일어나는 큐잉 시스템을 모델링하는 데 유용합니다.

1. 레이트 행렬 (Rate Matrix) 및 전이 확률

• 레이트 행렬 ($G$, Generator Matrix): CTMC의 상태 전이율을 나타내는 행렬입니다.
  • 비대각 원소 $g_{ij}$ ($i \ne j$)는 상태 $i$에서 $j$로의 전이율이며, 이는 사건 발생률(e.g., 도착률 $\lambda$, 서비스율 $\mu$)에 해당합니다.
  • 각 행의 모든 원소의 합은 0입니다.
• CTMC 전이 행렬 ($P(t)$): 시간 $t$ 동안의 전이 확률 행렬이며, 레이트 행렬을 사용하여 계산됩니다:
  $\mathbf{P}(t) = e^{tG}$
  (이는 행렬 지수 함수로 계산되며, $t$가 0에 가까울 때 테일러 1차 근사 $P(t) \approx I + tG$를 통해 근사될 수 있습니다).
• 채프먼-콜모고로프 속성: $P(s+t) = P(s)P(t)$를 만족합니다.

2. 정상 분포 및 안정성

• 정상 분포 ($\pi$): CTMC의 정상 분포는 다음 두 조건을 해(solve)하여 구합니다:
  1. $\sum \pi_i = 1$
  2. $\mathbf{\pi G = 0}$ (이는 흐름 균형 방정식(Flow Balance Equation)과 동등합니다).
• CTMC의 안정성 및 $\pi$의 존재:
  • 유한 상태 CTMC는 일반적으로 유일한 정상 분포를 가집니다 (DTMC와 달리 주기성 문제는 CTMC에서 고려되지 않습니다).
  • 무한 상태 CTMC는 안정적일 때(stable)에만 유일한 정상 분포를 가집니다. 정상 분포를 계산할 수 있다면 그 시스템은 안정적이라고 간주할 수 있습니다.
• 큐잉 이론과의 연결: 도착 및 서비스 시간이 지수 분포를 따르는 $M/M/\cdot/\cdot$ 큐잉 모델은 CTMC로 모델링될 수 있으며, 시스템 내 고객 수를 상태로 정의하여 분석합니다.

마르코프 연쇄 모델링의 주요 장점은 시스템의 미래 진화가 오직 가장 최근의 정보에만 의존한다는 강력한 가정을 통해 확률적 진화를 수학적으로 다룰 수 있게 한다는 점입니다. 만약 미래가 더 과거의 정보에 의존하는 것처럼 보이는 경우에도, 상태 공간을 확장하여($Y_n = (X_{n-1}, X_n)$와 같이) 여전히 마르코프 연쇄로 모델링할 수 있어 적용 범위를 넓힐 수 있습니다.