선형대수마르코프 체인과 행렬#390

마르코프 체인과 행렬

Markov Chains and Matrices

마르코프 체인과 행렬은 현재 상태만으로 다음 상태의 확률이 정해지는 과정을 열확률 전이행렬과 확률벡터의 곱으로 나타낸다. 두 상태 예에서 두 단계 확률, 정상분포 (3/5, 2/5), 거듭제곱의 극한을 계산한다. 정상분포가 있어도 왕복하며 수렴하지 않는 반례를 구별한다.

주인공 기호
P
읽는 시간
약 7분
선수 개념
대각화와 행렬의 거듭제곱확률의 뜻

직관 — 오늘의 상태별로 내일의 비율을 나누기

직관

두 상태 사이를 오가는 대상을 생각하자. 오늘 어느 상태에 있는지에 따라 내일 옮겨 갈 비율이 정해진다. 각 상태에서 출발하는 몫을 나눠 합하면 내일의 전체 분포를 얻는다.

오가는 두 자리가 상태이고, 옮겨 갈 비율이 전이확률이다. 예를 들어 상태 A를 맑음, B를 비로 읽으면 오늘 날씨만으로 내일 날씨의 확률이 정해지는 모형이 된다. 이 글의 수치는 계산을 위한 가상 값이다.

여기서는 전이 확률이 시간에 따라 바뀌지 않는 유한 상태 모형을 다룬다. 과거 경로를 모두 알아도 현재 상태가 주어졌을 때 다음 상태의 조건부확률은 더 달라지지 않는다는 가정이 마르코프 성질이다. 이것은 각 시점의 상태가 서로 독립이라는 뜻이 아니다.

마르코프 전이행렬은 출발 상태별 다음 상태 확률을 모은다

이 글은 확률을 열벡터로 놓고, PP의 (i,j)(i,j) 성분을 상태 jj에서 상태 ii로 가는 확률로 정한다. 모든 성분은 0 이상이고 각 열의 합은 1이다. 이를 열확률행렬이라고 한다.

pn+1=Ppn,pn=Pnp0(n=0,1,2,…).(1)\mathbf p_{n+1}=P\mathbf p_n,\qquad \mathbf p_n=P^n\mathbf p_0\quad(n=0,1,2,\ldots).\tag{1}
정의
기호이름원어뜻
PP전이행렬transition matrix출발 상태를 열로 모은 정사각행렬
PijP_{ij}전이확률transition probability현재 jj일 때 다음 ii일 확률
pn\mathbf p_n확률벡터probability vector성분이 0 이상이고 합이 1인 열벡터
π\boldsymbol\pi정상분포stationary distributionPπ=πP\boldsymbol\pi=\boldsymbol\pi인 확률벡터
nn시점time step0 이상의 정수

식 (1)의 ii번째 성분은 ∑jPij(pn)j\sum_jP_{ij}(\mathbf p_n)_j다. 현재 상태별 경우를 나누는 확률의 곱셈과 덧셈으로 얻는다. 각 항이 음이 아니고 전체 합은 ∑j(∑iPij)(pn)j=1\sum_j(\sum_iP_{ij})(\mathbf p_n)_j=1이므로 다음 벡터도 확률벡터다. 행의 합이 1인 관례를 쓰는 자료에서는 그 행렬이 이 글 PP의 전치이고, 벡터 방향과 곱셈 순서도 바뀌므로 섞어 쓰지 않는다.

마르코프 체인의 두 시점 뒤 확률은 어떻게 계산하나

현재 상태로 경우를 나누어 경로마다 확률을 곱하고 더한다. 상태 이름을 A,BA,B로 정한 가상 모형에서 AA에서는 다음에도 AA일 확률이 4/54/5, BB에서는 다음에 AA일 확률이 3/103/10이라고 하자.

P=(4/53/101/57/10),p0=(10),p1=(4/51/5),p2=(7/103/10).(2)P=\begin{pmatrix}4/5&3/10\\1/5&7/10\end{pmatrix},\quad \mathbf p_0=\begin{pmatrix}1\\0\end{pmatrix},\quad \mathbf p_1=\begin{pmatrix}4/5\\1/5\end{pmatrix},\quad \mathbf p_2=\begin{pmatrix}7/10\\3/10\end{pmatrix}.\tag{2}

상태 전이도는 상태를 점으로 놓고, 한 시점 뒤에 옮겨 갈 상태마다 그 확률을 적은 화살표를 그린 그림이다. 제자리에 머무는 확률은 자기 자신으로 돌아오는 화살표로 적는다. 그림 1의 상태 전이도에서 AA를 떠나는 두 화살표 4/54/5, 1/51/5가 PP의 첫 열이고, BB를 떠나는 3/103/10, 7/107/10이 둘째 열이다. 각 열의 합이 1인 것은 한 상태에서 나가는 확률을 모두 더했기 때문이다.

두 상태 A,B의 상태 전이도와 같은 정보를 담은 전이행렬 P. 한 상태에서 나가는 화살표의 확률이 그 상태의 열이 되고, 각 열의 합은 1이다.
그림 1 두 상태 A,BA,B의 상태 전이도와 같은 정보를 담은 전이행렬 PP. 한 상태에서 나가는 화살표의 확률이 그 상태의 열이 되고, 각 열의 합은 1이다. figures/transition_diagram.py

두 번째 시점에 AA일 확률은 첫 시점의 상태로 경우를 나눈다. A→A→AA\to A\to A 경로는 (4/5)(4/5)=16/25(4/5)(4/5)=16/25이고, A→B→AA\to B\to A 경로는 (1/5)(3/10)=3/50(1/5)(3/10)=3/50이다. 둘을 더하면 7/107/10이다(그림 2). 모든 출발자가 매번 정확히 이 비율로 나뉜다는 관측 자료가 아니라, 정해 둔 확률 모형의 분포 계산이다.

A에서 출발해 두 시점 뒤의 상태를 나눈 수형도. 가지의 확률을 곱한 네 경로 가운데 A로 끝나는 16/25와 3/50을 더하면 7/10이다.
그림 2 AA에서 출발해 두 시점 뒤의 상태를 나눈 수형도. 가지의 확률을 곱한 네 경로 가운데 AA로 끝나는 16/2516/25와 3/503/50을 더하면 7/107/10이다. figures/two_step_tree.py

출발 상태를 정하지 않고 두 단계 전이확률을 한꺼번에 담은 것이 P2P^2이다.

P2=(7/109/203/1011/20).(3)P^2=\begin{pmatrix}7/10&9/20\\3/10&11/20\end{pmatrix}.\tag{3}

P2P^2의 (i,j)(i,j) 성분은 현재 jj일 때 두 시점 뒤 ii일 확률이다. 첫 열 (7/10,3/10)(7/10,3/10)이 위의 p2\mathbf p_2와 같고, 둘째 열은 BB에서 출발한 경우다. 같은 이유로 PnP^n의 (i,j)(i,j) 성분이 nn단계 전이확률이다.

마르코프 체인의 정상분포는 연립방정식으로 구한다

정상분포는 한 번 더 전이해도 그대로인 확률벡터 π=(πA,πB)T\boldsymbol\pi=(\pi_A,\pi_B)^{\mathsf T}다. Pπ=πP\boldsymbol\pi=\boldsymbol\pi를 (P−I)π=0(P-I)\boldsymbol\pi=\mathbf 0으로 옮기면 두 식이 같은 식이 되므로, 합이 1이라는 조건을 함께 쓴다.

−15πA+310πB=0,πA+πB=1.(4)-\frac15\pi_A+\frac3{10}\pi_B=0,\qquad \pi_A+\pi_B=1.\tag{4}

첫 식에서 2πA=3πB2\pi_A=3\pi_B이므로 πA:πB=3:2\pi_A:\pi_B=3:2이다. 합이 1이 되도록 나누면 π=(3/5,2/5)T\boldsymbol\pi=(3/5,2/5)^{\mathsf T}이다. 검산하면 (4/5)(3/5)+(3/10)(2/5)=12/25+3/25=3/5(4/5)(3/5)+(3/10)(2/5)=12/25+3/25=3/5이다.

두 식이 같아지는 이유는 PP의 각 열의 합이 1이라 P−IP-I의 두 행을 더하면 영벡터가 되기 때문이다. 그래서 (P−I)π=0(P-I)\boldsymbol\pi=\mathbf 0만으로는 비율만 정해지고, 크기는 합 1의 조건이 정한다.

마르코프 체인의 정상분포는 상태가 더 바뀌지 않는다는 뜻인가요?

아니다. 개별 대상이 아니라 분포가 그대로라는 뜻이다. π=(3/5,2/5)\boldsymbol\pi=(3/5,2/5)에서도 한 단계에 AA에서 BB로 가는 확률 흐름 (3/5)(1/5)=3/25(3/5)(1/5)=3/25와 BB에서 AA로 가는 흐름 (2/5)(3/10)=3/25(2/5)(3/10)=3/25가 있다. 두 흐름이 같아 분포가 유지될 뿐이다.

마르코프 전이행렬을 대각화하면 남는 성분과 줄어드는 성분이 나뉜다

det⁡(tI−P)=t2−32t+12=(t−1)(t−1/2)\det(tI-P)=t^2-\frac32t+\frac12=(t-1)(t-1/2)이다. 고윳값 1에는 (3,2)T(3,2)^{\mathsf T}, 고윳값 1/21/2에는 (1,−1)T(1,-1)^{\mathsf T}가 대응한다. 따라서 대각화의 기저행렬과 역행렬은 다음과 같다.

S=(312−1),S−1=15(112−3),P=S(1001/2)S−1.(5)S=\begin{pmatrix}3&1\\2&-1\end{pmatrix},\quad S^{-1}=\frac15\begin{pmatrix}1&1\\2&-3\end{pmatrix},\qquad P=S\begin{pmatrix}1&0\\0&1/2\end{pmatrix}S^{-1}.\tag{5}

초기 벡터는 15(3,2)T+25(1,−1)T\frac15(3,2)^{\mathsf T}+\frac25(1,-1)^{\mathsf T}다. 행렬의 거듭제곱을 취하면 첫 성분은 남고 둘째 성분에만 (1/2)n(1/2)^n이 곱해진다.

pn=(3/52/5)+(12)n(2/5−2/5)⟶π=(3/52/5).(6)\mathbf p_n=\begin{pmatrix}3/5\\2/5\end{pmatrix} +\left(\frac12\right)^n\begin{pmatrix}2/5\\-2/5\end{pmatrix} \longrightarrow\boldsymbol\pi=\begin{pmatrix}3/5\\2/5\end{pmatrix}.\tag{6}

고윳값 1의 고유방향 (3,2)(3,2)를 성분 합이 1이 되도록 나눈 것이 식 (4)의 정상분포와 같다. 두 성분의 합이 1인 확률벡터를 좌표평면의 점으로 찍으면 모두 한 선분 위에 놓인다. 그림 3에서 고유방향 (3,2)(3,2)는 이 선분과 π\boldsymbol\pi에서 만나고, (1,−1)(1,-1)은 선분을 따라가는 방향이다.

두 성분의 합이 1인 확률벡터가 놓이는 선분. (1,0)과 (0,1)에서 출발한 mathbf p_n이 고유방향 (3,2) 위의 boldsymbolπ=(3/5,2/5)로 다가가며, boldsymbolπ까지의 거리가 단계마다 절반이 된다.
그림 3 두 성분의 합이 1인 확률벡터가 놓이는 선분. (1,0)(1,0)과 (0,1)(0,1)에서 출발한 pn\mathbf p_n이 고유방향 (3,2)(3,2) 위의 π=(3/5,2/5)\boldsymbol\pi=(3/5,2/5)로 다가가며, π\boldsymbol\pi까지의 거리가 단계마다 절반이 된다. figures/probability_segment.py

같은 계산을 두 표준기저 벡터에 하면 PnP^n 전체가 나온다. r=(1/2)nr=(1/2)^n으로 쓰면 다음과 같다.

Pn=(35+25r35−35r25−25r25+35r),r=(12)n.(7)P^n=\begin{pmatrix}\frac35+\frac25r&\frac35-\frac35r\\[2pt]\frac25-\frac25r&\frac25+\frac35r\end{pmatrix},\qquad r=\left(\frac12\right)^n.\tag{7}

식 (7)에 n=2n=2를 넣으면 r=1/4r=1/4이고 식 (3)의 P2P^2가 나온다. nn이 커지면 rr이 0에 가까워져 두 열이 모두 π\boldsymbol\pi에 가까워진다. 어느 상태에서 출발했든 오래 지나면 AA일 확률이 3/53/5에 가까워진다는 뜻이다.

모이는 빠르기는 둘째 고윳값 1/21/2이 정한다. AA에서 출발하면 AA일 확률과 3/53/5의 차이가 25(1/2)n\frac25(1/2)^n이라, 이 차이가 0.01보다 작아지는 첫 시점은 n=6n=6이다(0.006250.00625). 같은 규칙을 따르는 1000명이 모두 AA에서 출발하면, 10시점 뒤 AA에 있을 인원의 기댓값은 p10\mathbf p_{10}의 AA 성분에 1000을 곱한 약 600.4명이다.

마르코프 체인은 정상분포가 있어도 수렴하지 않을 수 있다

T=(0110)T=\begin{pmatrix}0&1\\1&0\end{pmatrix}는 (1/2,1/2)T(1/2,1/2)^{\mathsf T}를 그대로 둔다. 그러나 (1,0)T(1,0)^{\mathsf T}로 시작하면 (0,1),(1,0),…(0,1),(1,0),\ldots로 왕복한다. 고윳값 −1-1의 거듭제곱 (−1)n(-1)^n이 사라지지 않기 때문이다. 단위행렬은 모든 확률벡터를 그대로 두므로 시작과 무관한 유일한 정상분포도 없다.

그림 4의 위 패널은 식 (2)의 PP에서 두 초기분포의 AA 확률을 계산한 것이다. 그려진 몇 단계만으로 수렴을 증명하는 것이 아니라 식 (6)의 거듭제곱 극한이 이유다. 아래 패널은 TT의 왕복이다.

위: 식 (2)의 전이에서 두 시작 분포가 A의 확률 3/5로 접근한다. 아래: 두 상태를 반드시 맞바꾸는 전이는 (1,0)에서 시작하면 1과 0을 왕복한다. 선은 이산 시점을 잇는 안내선이다.
그림 4 위: 식 (2)의 전이에서 두 시작 분포가 A의 확률 3/5로 접근한다. 아래: 두 상태를 반드시 맞바꾸는 전이는 (1,0)에서 시작하면 1과 0을 왕복한다. 선은 이산 시점을 잇는 안내선이다. figures/markov_convergence.py

두 상태에서 다음 조건은 모든 초기분포의 수렴을 보장한다. 양방향 이동 확률을 a,ba,b라 하고 0<a<10<a<1, 0<b<10<b<1이라고 하자.

P=(1−aba1−b),π=1a+b(ba).(8)P=\begin{pmatrix}1-a&b\\a&1-b\end{pmatrix},\qquad \boldsymbol\pi=\frac1{a+b}\begin{pmatrix}b\\a\end{pmatrix}.\tag{8}

첫 상태의 확률을 xnx_n이라 하면 xn+1=(1−a−b)xn+bx_{n+1}=(1-a-b)x_n+b다. x∗=b/(a+b)x_*=b/(a+b)를 빼면 xn+1−x∗=(1−a−b)(xn−x∗)x_{n+1}-x_*=(1-a-b)(x_n-x_*)이다. 따라서 xn−x∗=(1−a−b)n(x0−x∗)x_n-x_*=(1-a-b)^n(x_0-x_*)이고 ∣1−a−b∣<1\lvert1-a-b\rvert<1이므로 0으로 간다. 이는 명시한 두 상태 조건에 대한 일반 이유이며, 모든 전이행렬이 대각화되거나 모든 마르코프 체인이 수렴한다는 뜻은 아니다.

핵심

마르코프 체인의 확률분포는 열확률 관례에서 pn=Pnp0\mathbf p_n=P^n\mathbf p_0로 변한다. 정상분포는 고윳값 1의 확률벡터이고, 모든 시작이 그곳으로 모이려면 나머지 고윳값의 거듭제곱이 사라져야 한다.

마르코프 체인은 독립 시행인가요?

일반적으로 아니다. 식 (2)에서는 다음에 AA일 확률이 현재 AA일 때 4/54/5, 현재 BB일 때 3/103/10으로 다르다. 마르코프 성질은 현재를 알면 과거가 더 영향을 주지 않는다는 가정이며, 시점끼리 독립이라는 가정과 다르다.

마르코프 체인의 확률벡터는 합이 1이면 음수 성분도 되나요?

아니다. 확률이므로 음수는 허용되지 않는다. 예를 들어 (2,−1)T(2,-1)^{\mathsf T}는 합이 1이어도 확률벡터가 아니다. 전이행렬도 열 합과 비음수 조건을 함께 검사한다.

마르코프 전이행렬은 행 합이 1인가요, 열 합이 1인가요?

어느 쪽 합이 1인지는 확률벡터를 놓는 약속에 따라 다르다. 이 글처럼 확률을 열벡터로 두고 PpnP\mathbf p_n을 계산하면 열 합이 1이고, 행벡터에 오른쪽에서 행렬을 곱하는 자료는 행 합이 1이다. 두 행렬은 서로의 전치라서, 식 (2)의 PP를 전치하면 행 (4/5,1/5)(4/5,1/5)와 (3/10,7/10)(3/10,7/10)의 합이 각각 1이 된다.

마르코프 체인과 행렬의 흔한 오해

  • 정상분포를 찾으면 어떤 시작도 그곳으로 간다. — 그림 4 아래의 왕복 전이는 정상분포 (1/2,1/2)(1/2,1/2)가 있어도 (1,0)(1,0)에서 시작하면 수렴하지 않는다.
  • 두 단계 전이확률은 한 단계 확률의 제곱이다. — AA에서 두 시점 뒤 AA일 확률은 (4/5)2=16/25(4/5)^2=16/25가 아니라 BB를 거치는 경로 3/503/50을 더한 7/107/10이다. 식 (3)의 성분은 행렬 곱으로 구한다.

직접 해보기

  1. 식 (2)의 PP에 p0=(1/2,1/2)T\mathbf p_0=(1/2,1/2)^{\mathsf T}를 넣어 p1,p2\mathbf p_1,\mathbf p_2를 구하라.
답 1

첫 성분은 2/5+3/20=11/202/5+3/20=11/20이므로 p1=(11/20,9/20)T\mathbf p_1=(11/20,9/20)^{\mathsf T}다. 다시 곱하면 11/25+27/200=23/4011/25+27/200=23/40이므로 p2=(23/40,17/40)T\mathbf p_2=(23/40,17/40)^{\mathsf T}다. 각 합은 1이다.

  1. P∗=(7/101/53/104/5)P_*=\begin{pmatrix}7/10&1/5\\3/10&4/5\end{pmatrix}의 정상분포와 수렴 이유를 구하라.
답 2

식 (8)에서 a=3/10,b=1/5a=3/10,b=1/5다. a+b=1/2a+b=1/2이므로 정상분포는 (2/5,3/5)T(2/5,3/5)^{\mathsf T}다. 첫 성분과 2/52/5의 차이가 매번 1−a−b=1/21-a-b=1/2배가 되므로 모든 초기 확률벡터에서 수렴한다.

  1. 왕복 전이 TT를 (1/2,1/2)T(1/2,1/2)^{\mathsf T}에서 시작하면 수렴하는가? (1,0)T(1,0)^{\mathsf T}의 경우와 비교하라.
답 3

첫 시작은 곱해도 그대로이므로 상수 수열로 수렴한다. 둘째 시작은 두 벡터를 왕복하여 수렴하지 않는다. 같은 전이에서도 초기분포를 지정한 주장과 모든 초기분포에 대한 주장은 다르다.

  1. R=(4/51/53/107/10)R=\begin{pmatrix}4/5&1/5\\3/10&7/10\end{pmatrix}를 이 글의 열확률 전이행렬로 쓸 수 있는가?
답 4

열 합이 11/10,9/1011/10,9/10이므로 쓸 수 없다. 실제로 (1,0)T(1,0)^{\mathsf T}를 곱하면 합이 11/1011/10인 벡터가 나온다. 행 합이 1인 자료의 행벡터 관례를 사용하려면 곱셈 방향을 달리해야 한다.

  1. 세 상태의 전이행렬 P3=(1/21/401/21/21/201/41/2)P_3=\begin{pmatrix}1/2&1/4&0\\1/2&1/2&1/2\\0&1/4&1/2\end{pmatrix}가 열확률행렬인지 확인하고, 첫 상태에서 출발한 p1,p2\mathbf p_1,\mathbf p_2를 구하라. (1/4,1/2,1/4)T(1/4,1/2,1/4)^{\mathsf T}가 정상분포인지도 확인하라.
답 5

세 열의 합이 모두 1이고 성분이 음수가 아니므로 열확률행렬이다. p1=P3(1,0,0)T=(1/2,1/2,0)T\mathbf p_1=P_3(1,0,0)^{\mathsf T}=(1/2,1/2,0)^{\mathsf T}이고, 다시 곱하면 p2=(3/8,1/2,1/8)T\mathbf p_2=(3/8,1/2,1/8)^{\mathsf T}다. P3(1/4,1/2,1/4)TP_3(1/4,1/2,1/4)^{\mathsf T}의 첫 성분은 1/8+1/8=1/41/8+1/8=1/4이고 나머지도 그대로라서 정상분포다.

영상 노트

영상 노트
  • 00:00 출발을 열로 정하는 약속
  • 01:00 그림 1의 상태 전이도와 행렬의 열
  • 02:00 식 (2)와 그림 2의 두 단계 확률, 식 (3)의 두 번 곱한 행렬
  • 03:30 식 (4)로 정상분포 풀기와 확률 흐름
  • 04:40 식 (5)~(7)의 남는 성분과 줄어드는 성분, 그림 3의 선분
  • 06:10 그림 4의 접근과 왕복 대조
  • 07:10 식 (8)의 조건으로 수렴 이유 설명

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 고급 대수, 행렬의 대각화 영역. 성취기준과 해설의 계산 범위를 확인했다.
  • Georgia Tech, Interactive Linear Algebra 5.6절 — 열확률행렬의 정의·총합 보존·정상분포와 양의 전이행렬의 수렴 설명을 읽었다. 본문은 두 상태의 수렴을 직접 유도하며 일반 Perron–Frobenius 정리를 증명했다고 주장하지 않는다.
  • Markov chain — Wikipedia. 행 합이 1인 확률행렬 관례와 유한 상태의 정상분포 절이 있어, '마르코프 전이행렬은 행 합이 1인가요, 열 합이 1인가요?' 질문의 다른 관례를 대조할 수 있다.

지도에서의 위치

이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 상태 전이도와 행렬의 열, 두 단계 확률의 수형도와 두 번 곱한 전이행렬, 정상분포를 연립방정식으로 푸는 절, 거듭제곱의 닫힌 꼴과 확률벡터 선분 그림, 행 합 관례·확률 흐름 질문, 세 상태 연습 추가, 숫자 앞 띄어쓰기 정리 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림
  4. 2026-11-17 · 용어집 정리 — 상태 전이도를 정의하는 문장 추가 (에이전트 수정)