마르코프 체인의 기본 개념
마르코프 체인(Markov Chain)은 확률론적 관점에서 “현재 상태가 주어졌을 때, 미래 상태가 과거의 이력과 무관하게 현재 상태에만 의존한다”는 ‘마르코프성’을 가정하는 확률적 과정이다. 즉, 상태가 불연속적인 시점에 따라 순차적으로 변해가며, 각 시점의 상태가 단 하나의 이전 상태에만 의존한다는 기억 없음(memoryless) 성질을 갖는다.
보다 구체적으로, 유한 상태공간 \(\{1,\,2,\,\dots,\,n\}\)이 있고, 시점 \(t\in\{0,\,1,\,2,\,\dots\}\)에서 마르코프 체인의 상태가 \(X_t\)라고 하자. 그러면 마르코프 체인은 다음 성질을 만족한다.
\[ \Pr(X_{t+1} = j \mid X_t = i,\ X_{t-1} = x_{t-1}, \dots, X_0 = x_0) = \Pr(X_{t+1} = j \mid X_t = i). \]
즉, “현재 상태가 \(i\)”인 순간에는 이전 이력(\(X_{t-1},\) \(X_{t-2},\) \(\dots\))과는 무관하게, 오직 현재 상태 \(i\)에 의해서만 다음 상태 \(j\)로 전이될 확률이 결정된다. 이를 마르코프성질이라고 부른다.
이 마르코프성 덕분에, 전체 체인의 거동을 전이확률 행렬(transition probability matrix) 하나로 대표할 수 있고, 이를 통해 선형대수적인 해석(행렬곱, 고윳값·고유벡터 분석 등)으로 체인의 장기적 움직임(안정상태)을 파악할 수 있다.
전이확률 행렬
마르코프 체인의 상태 전이는, 각 시점에서 “현재 상태가 \(i\)”일 때 “다음 상태가 \(j\)”가 될 확률을 정리한 전이확률 행렬(transition probability matrix)로 표현할 수 있다. 전이확률 행렬을 보통 \(P\)라고 표기하며, \(P\)는 다음과 같은 성질을 갖는 \(n\times n\) 행렬이다.
- 원소가 모두 0 이상: 임의의 \(i,\) \(j\)에 대하여 \(p_{ij}\ge 0\).
- 행(또는 열)의 합이 1: 마르코프 체인을 정의할 때, “현재 상태 \(i\)에서 다음 상태가 될 수 있는” 모든 상태 \(j\)의 확률을 합하면 1이 되어야 한다.
주로 “행의 합을 1”로 정하는 방법과 “열의 합을 1”로 정하는 방법이 있는데, 글에서는 한 가지 방식을 선택해 놓고 진행한다. 예컨데, 만약 행의 합을 기준으로 하는 방식을 취한다면, \[ \sum_{j=1}^n p_{ij} = 1 \quad (\forall i) \] 가 성립한다.
정의상, 전이확률 행렬 \(P\)의 \(i\)번째 행, \(j\)번째 열 원소 \(p_{ij}\)는 \[ p_{ij} = \Pr\bigl(X_{t+1} = j \,\big|\; X_t = i\bigr) \] 이다. 즉, 상태 \(i\)에 있을 때 다음에 상태 \(j\)로 이동할 확률이다. 이러한 행렬 \(P\)에 대해, 선형대수학적으로는 다음 단계 상태분포를 \(\mathbf{p}(t+1)\)로, 현재 상태분포를 \(\mathbf{p}(t)\)로 두면 \[ \mathbf{p}(t+1) = P\,\mathbf{p}(t) \] 가 된다. 이에 따라, 다단계 전이(\(k\)단계 후의 분포)는 \(P^k\)라는 행렬 거듭제곱을 통해 표현된다. 이는 마르코프 체인의 안정상태(steady state) 분석에도 핵심적인 역할을 한다.
전이확률 행렬 \(P\)는 마르코프 체인의 “상태 전이 규칙”을 완벽히 요약한 수단이며, \(\mathbf{p}(t+1)=P\,\mathbf{p}(t)\) 꼴의 선형연산 형태로 마르코프 체인을 해석하게 해준다. 이후 고윳값·고유벡터 분석으로부터 체인의 안정상태와 장기거동을 결정하는 것이 가능하다.
고윳값·고유벡터를 통한 안정상태(Steady State)
마르코프 체인의 전이확률 행렬 \(P\)가 주어졌을 때, 체인의 안정상태 여부를 결정하는 핵심은 “\(\mathbf{p}(t+1) = P\,\mathbf{p}(t)\)”가 반복 적용될 때, \(\mathbf{p}(t)\)가 어떤 벡터로 수렴(또는 주기적/복잡하게 변동)하는가를 파악하는 것이다. 이때 선형대수의 관점에서, \(P\)의 고윳값(eigenvalue)과 고유벡터(eigenvector)가 체인의 장기적인 움직임을 결정한다. 특히, 고윳값이 1에 해당하는 고유벡터는 체인의 안정상태(steady state) 분포로 해석된다.
정리 1. (안정상태와 고윳값 1)
확률 전이행렬 \(P\)에 대해, 만약 벡터 \(\mathbf{p}^*\)가 \[ P\,\mathbf{p}^* = \mathbf{p}^* \] 를 만족한다면(또한 \(\mathbf{p}^*\)가 확률분포 형태, 즉 원소 \(\ge0\)이고 합이 1이라면), \(\mathbf{p}^*\)를 마르코프 체인의 안정상태(steady-state) 분포라고 한다. 이는 선형대수학적으로 고윳값이 1에 해당하는 고유벡터를 의미한다.
즉, \[ P\,\mathbf{p}^* = 1 \cdot \mathbf{p}^*, \] 이므로, 1이 고윳값, \(\mathbf{p}^*\)가 이에 대응하는 고유벡터(확률분포로 정규화)라는 뜻이다. 실제 많은 확률행렬 \(P\)에 대해(관건은 기약성(irreducible)·아퍼리어드성(aperiodic) 등 조건), \[\lim_{n\to\infty}P^n=\mathbf{p}^*(\mathbf{1}^T)\] 형태로, 임의 초기 분포에서 \(\mathbf{p}^*\)로 수렴하는 현상이 발생한다. 이를 마르코프 체인의 장기분포라고 한다.
구체적으로, 안정상태 \(\mathbf{p}^*\)는 다음 조건을 만족한다.
- \(\mathbf{p}^*\)는 확률분포: \(\mathbf{p}^*\ge0\) 그리고 \(\sum_i p^*_i=1.\)
- 고윳값 1 고유벡터: \(P\,\mathbf{p}^*=\mathbf{p}^*\). 이는 \((I-P)\mathbf{p}^*=0\)와 동치다.
보기 1.
다음과 같은 \(3\times 3\) 전이행렬을 살펴보자. \[\displaystyle P=\begin{pmatrix} 0.5 & 0.5 & 0\\ 0.2 & 0.3 & 0.5\\ 0 & 0.4 & 0.6 \end{pmatrix}\] 이때 안정상태 \(\mathbf{p}^*\)를 구하기 위해서는 \[ (I-P)\mathbf{p}^*=0 \] 를 풀고, 해가 확률분포가 되도록 정규화하면 된다. 예컨대 \[ \mathbf{p}^*=(x,y,z)^T,\quad x+y+z=1,\quad P\,\mathbf{p}^*=\mathbf{p}^*. \] 라는 연립방정식을 풀어 보면, 특정한 \((x,y,z)\)가 발견되고, 그것이 체인의 장기분포를 나타낸다.
이처럼, 마르코프 체인의 안정상태 여부를 결정짓는 것은 전이행렬 \(P\)의 고윳값 분석이고, 1에 대응하는 고유벡터(확률분포)가 존재하고 적절한 조건(기약·아퍼리어드 등)을 만족하면, 임의 초기 상태에서 장기적으로 그 고유벡터 방향(안정상태)로 수렴한다는 사실이, 선형대수학과 확률론을 결합한 마르코프 체인의 가장 중요한 결론 중 하나이다.
독특한 예
마르코프 체인의 작동 원리를 살펴보기 위해, 서로 다른 양상의 작은 예시 두 가지를 살펴보자. 첫 번째 예시는 즉시 장기분포로 수렴하는 단순 체인이고, 두 번째 예시는 조금 더 복잡한 구조를 갖는 체인을 소개한다.
보기 2. (2상태 체인: 즉시 고정)
상태공간이 \(\{1,2\}\)인 이중상태 체인을 생각하자. 전이행렬을 다음과 같이 둔다.
\[ P = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}. \]
즉, 상태 1에 있으면 다음에도 반드시 상태 1로, 상태 2에 있으면 다음에도 반드시 상태 2로 전이한다(확률 1). 이는 정지(고착)되는 체인(stationary chain)의 예시이다. 실제로,
- 임의의 초기분포 \(\mathbf{p}(0)=(p_1,\,p_2)\)에 대하여, \(\mathbf{p}(1)=P\,\mathbf{p}(0)=\mathbf{p}(0)\)가 즉시 성립.
- 따라서 모든 시점 \(t\)에서 \(\mathbf{p}(t)=\mathbf{p}(0)\). 곧, 체인의 장기분포는 초기분포에 의해 완전히 결정되고, 전혀 변하지 않는다.
선형대수학적으로 보면, 행렬 \(P\)의 고윳값은 1(중복도 2)이고, 고유벡터가 임의의 (x,y)형태(각 확률로 해석 가능)로 이어져 있다. 초기분포에 따라 곧장 그 상태분포를 유지한다는 뜻이다.
보기 3. (3상태 체인: 유한회전(periodic) 구조)
이번에는 상태공간이 \(\{1,2,3\}\)이며, 전이행렬이 다음과 같이 주어진 체인을 생각해 보자.
\[ P = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}. \]
이는 “상태 1→2, 2→3, 3→1” 순으로 순환하는 체인이다. 구체적으로, \(\Pr(X_{t+1}=2 \mid X_t=1)=1\), \(\Pr(X_{t+1}=3 \mid X_t=2)=1\), \(\Pr(X_{t+1}=1 \mid X_t=3)=1\). 따라서 상태가 순차적으로 1→2→3→1→2→3→… 식으로 돌게 된다.
- 행렬 해석: 임의의 초기분포 \(\mathbf{p}(0)\)가 있으면, \(\mathbf{p}(1)=P\mathbf{p}(0)\), \(\mathbf{p}(2)=P^2\mathbf{p}(0)\), …, \(\mathbf{p}(3)=P^3\mathbf{p}(0)=\mathbf{p}(0)\)로 돌아가는 것을 쉽게 확인할 수 있다.
- 주기성(periodic): 모든 상태가 주기 3을 지니므로, \(\mathbf{p}(t)\)도 3단계마다 반복. 따라서 장기분포라는 것이 하나의 고정분포로 수렴하지 않고, 세 가지 분포를 반복하게 된다.
선형대수학적으로, 행렬 \(P\)의 고윳값은 1, 그리고 \(\exp(\tfrac{2\pi i}{3})\), \(\exp(\tfrac{4\pi i}{3})\)와 같은 복소근들이 등장한다. 이로 인해 실공간 \(\mathbb{R}^3\)에서 분포가 단일 정태 분포로 수렴하지 않고, 순환하는 거동을 보임을 밝힐 수 있다.
이 두 예는, 마르코프 체인이 “고윳값 1에 대응하는 단 하나의 실 고유벡터(확률분포)”로 수렴하는 경우도 있고, “주기(periodic) 체인”처럼 실제 분포가 반복 순환할 수 있음을 보여준다. 실제 응용에서 마르코프 체인은 보통 기약(irreducible), 아퍼리어드(aperiodic) 조건을 만족한다고 가정하여, 하나의 고정된 안정상태로 수렴함을 보장한다. 그러나 본 예시처럼 간단한 예를 통해선 다양한 형태가 가능함을 알 수 있다.
응용 예시
마르코프 체인은 확률과 선형대수가 결합된 구조이므로, 다양한 산업·공학·데이터 분야에서 폭넓게 활용된다. 다음은 대표적인 예시 두 가지를 간단히 살펴본 것이다.
보기 4. (웹 페이지 랭킹: PageRank)
구글의 초기 페이지랭크(PageRank) 알고리즘은 웹페이지 간의 링크 구조를 마르코프 체인으로 해석한다. 웹 전체를 상태공간(각 웹페이지 하나당 한 상태)으로 두고, 한 페이지에서 다른 페이지로 이동할 확률(링크 클릭)에 대응하는 전이확률 행렬 \(P\)를 구성한다. 페이지랭크를 구하고자 할 때, 사실상 그 행렬 \(P\)의 고유벡터(고윳값 1에 대응하는 벡터)를 찾는 문제와 동일해진다.
- 전이 행렬 구성: 각 페이지가 가진 링크를 기준으로, 링크가 있는 곳으로 이동할 확률을 동일하게 분배하거나, ‘랜덤 점프’를 추가로 고려하기도 한다(실제 구현은 텔레포레이션 항등을 섞은 확률행렬).
- 안정상태: \(\mathbf{r}^*\)가 \(\mathbf{r}^* = P\,\mathbf{r}^*\)를 만족하며, 이때 \(\mathbf{r}^*\)의 각 성분이 해당 페이지가 가지는 랭크(중요도)를 나타낸다. 고윳값 1, 고유벡터의 확률 해석이라는 관점이 사용된다.
이처럼 대규모 링크 구조를 \(P\)로 표현하고, \(\mathbf{r}^*\)를 찾는 것은 본질적으로 “마르코프 체인 정상분포”를 구하는 것이며, 선형대수학적 관점에서의 고유값분해(또는 거듭제곱 방법 등)로 해결된다.
보기 5. (재고관리/생산공정에서의 마르코프 체인)
공장 생산라인이나 재고관리 시스템에서, 현재 재고(혹은 상태)가 \(i\)개일 때, 다음 주기에 재고가 \(j\)개가 될 확률을 \(\Pr(X_{t+1}=j \mid X_t=i)\)로 정의한다. 이 확률은 주문, 소비, 보충 등의 확률 규칙에 따라 결정된다. 이렇게 확정된 전이확률 행렬 \(P\)를 기반으로, 장기적으로 재고가 어떤 분포를 갖게 되는지를 마르코프 체인 분석으로 알아볼 수 있다.
- 연립방정식의 해: 안정상태 \(\mathbf{p}^*\)가 존재한다면, \(\mathbf{p}^* = P\,\mathbf{p}^*\) 식을 만족하므로, 특정 재고레벨로 수렴하거나, 혹은 확률적으로 분포가 고정된다는 결론을 얻는다.
- 의사결정: 어떤 생산·보충 전략을 채택했을 때, 마르코프 체인 전이확률이 달라지고, 그에 따른 장기 재고분포(또는 평균 비용 등)를 계산하여 정책을 비교·최적화할 수 있다.
이러한 마르코프 체인 모형은 확률론과 선형대수학을 결합하여, 복잡한 확률적 시스템을 단순한 전이행렬 \(P\)로 표현하고, 그 행렬의 고유분해·거듭제곱으로부터 안정상태 여부를 효율적으로 추론해 낸다.
이처럼, 마르코프 체인은 웹 페이지 순위 결정, 재고관리, 금융 모델(신용등급 전이), 기상 예측(상태 전이) 등 다양한 실제 문제를 다루는 강력한 확률적 도구이며, 선형대수의 고유값·고유벡터 개념이 그 핵심 해법으로 연결된다.
