흡수 마르코프 연쇄

1. 개요

흡수 마르코프 연쇄 Absorbing Markov Chain
정의	흡수 상태가 있고, 모든 상태에서 흡수 상태로 갈 수 있는 연쇄
표준형	일시 블록 $Q$ + 흡수로 가는 블록 $R$
기본 행렬	$N=(I-Q)^{-1}=\sum_k Q^k$
흡수 시간	$t=N\mathbf 1$
흡수 확률	$B=NR$
정리	케메니·스넬 (1960)

언젠가는 끝난다. 언제 끝나는지, 어디서 끝나는지는 역행렬 하나가 다 안다.

흡수 마르코프 연쇄(absorbing Markov chain)는 한 번 들어가면 다시 나오지 않는 흡수 상태를 하나 이상 가지고, 모든 상태에서 유한 걸음 안에 어떤 흡수 상태로든 도달할 수 있는 유한 상태 마르코프 연쇄다. 흡수 상태가 아닌 나머지를 일시 상태(transient state)라 부른다. 이런 연쇄는 확률 1로 결국 흡수되므로 정상 분포가 아니라 **“얼마나 걸려서, 어느 출구로 나가는가”**가 관심사다.

도박꾼이 파산하느냐 목표액을 따느냐, 단백질이 접힌 상태에 먼저 닿느냐 펴진 상태로 돌아가느냐, 시스템이 고장 상태에 닿기까지의 평균 시간(MTTF), 동전 던지기에서 특정 패턴이 처음 나올 때까지의 횟수가 전부 이 틀 안에 들어간다. 계산은 선형대수 한두 번이다. 연속 확산의 평균 도달 시간과 그 PDE는 평균 첫 통과 시간 문서가 다루고, 거기서는 기본 행렬을 한 단락으로 소개했다. 이 문서는 그 이산판을 본격적으로 다룬다. 흡수 확률, 흡수 시간의 분산과 분포, 그리고 수치 계산의 요령이다.

2. 표준형과 기본 행렬

상태를 일시 상태 $t$ 개, 흡수 상태 $r$ 개 순서로 정렬하면 전이행렬이

$$P=\begin{pmatrix} Q & R\\ 0 & I\end{pmatrix}$$

꼴이 된다. $Q$ 는 일시 상태끼리의 $t\times t$ 블록, $R$ 은 일시→흡수의 $t\times r$ 블록이다. $n$ 걸음 전이는 $P^n$ 의 왼쪽 위 블록이 $Q^n$ 이고, 흡수 가능성 조건 때문에 $Q$ 의 스펙트럼 반지름이 1보다 작아 $Q^n\to 0$ 이다. 따라서 노이만 급수가 수렴하고

$$N=(I-Q)^{-1}=I+Q+Q^2+\cdots$$

를 기본 행렬(fundamental matrix)이라 부른다. 급수의 $k$ 번째 항 $(Q^k)_{ij}$ 가 ”$i$ 에서 출발해 $k$ 걸음째 $j$ 에 있을 확률”이니, 그 합 $N_{ij}$ 는 흡수되기 전까지 $j$ 를 방문하는 평균 횟수다. 나머지 양은 전부 $N$ 에서 나온다.

• 평균 흡수 시간 $t=N\mathbf 1$. 출발 상태별 흡수까지의 평균 걸음 수.
• 흡수 시간의 분산 $v=(2N-I)\,t-t\circ t$ ($\circ$ 는 원소별 곱).
• 흡수 확률 $B=NR$. $B_{ik}$ 는 $i$ 에서 출발해 흡수 상태 $k$ 로 끝날 확률이고, 각 행의 합은 1이다.

$B=NR$ 의 뜻은 직관적이다. 흡수 상태 $k$ 로 끝나려면 마지막 걸음 직전에 어떤 일시 상태 $j$ 에 있다가 $R_{jk}$ 로 넘어가야 하고, $j$ 에 머무는 평균 횟수가 $N_{ij}$ 다. 첫걸음 분석으로 쓰면 $B=QB+R$, 곧 $(I-Q)B=R$ 이다.

흡수 시간 $T$ 의 분포 자체도 닫힌꼴이다. 초기 분포를 $\alpha$ 라 하면 $P(T>n)=\alpha\,Q^n\mathbf 1$ 이고, 이렇게 정의되는 분포를 이산 위상형 분포라 한다. 꼬리는 $Q$ 의 최대 고유값 $\lambda_1$ 에 대해 $\lambda_1^n$ 으로 감쇠하니, $\lambda_1$ 이 1에 가까우면 평균은 유한해도 꼬리가 매우 길다.

3. 예제 1 — 도박꾼의 파산

0원이면 파산, 5원이면 목표 달성으로 끝나는 게임에서 매 판 1원을 걸고 확률 $p$ 로 딴다. 일시 상태는 1~4원, 흡수 상태는 0원과 5원이다. $Q$ 는 대각 바로 위가 $p$, 바로 아래가 $1-p$ 인 삼중대각 행렬이다. 이 문서를 쓰며 $N$ 을 직접 계산했다.

시작 금액	1	2	3	4
$p=0.5$: 평균 판 수	4	6	6	4
$p=0.5$: 분산	20	22	22	20
$p=0.5$: 목표 달성 확률	0.20	0.40	0.60	0.80
$p=0.4$: 평균 판 수	3.10	5.26	6.00	4.60
$p=0.4$: 목표 달성 확률	0.076	0.190	0.360	0.616

공정한 게임이면 평균 판 수가 $k(N-k)$, 달성 확률이 $k/N$ 이라는 교과서 공식과 맞다. 불공정한 게임의 달성 확률도 닫힌꼴 $\bigl(1-(q/p)^k\bigr)/\bigl(1-(q/p)^N\bigr)$ ($q=1-p$)과 소수점 끝까지 일치했다. 눈여겨볼 것은 분산이다. 2원에서 시작하면 평균 6판인데 표준편차가 $\sqrt{22}\approx 4.7$ 판이라, “평균 6판”이라는 말이 개별 게임에 대해 거의 아무것도 약속하지 않는다.

4. 예제 2 — 동전 패턴 대기 시간

공정한 동전을 던져 특정 패턴이 처음 나올 때까지의 횟수도 흡수 연쇄다. 상태는 “현재까지 맞춘 패턴의 접두사 길이”이고, 틀렸을 때는 지금까지 나온 열의 접미사 중 패턴의 접두사와 일치하는 가장 긴 것으로 돌아간다(문자열 탐색의 KMP 실패 함수와 같은 구성이다).

패턴	평균	분산
HT	4	4
HH	6	22
HHT	8	24
HTH	10	58
HHH	14	142

길이가 같은 HT와 HH의 평균이 다르다. HH는 H 다음에 T가 나오면 처음부터 다시 시작해야 하지만, HT는 H 다음에 H가 나와도 “H까지 맞춘 상태”에 머문다. 패턴이 자기 자신과 겹칠수록(HH, HTH, HHH) 대기 시간이 길다. 리(1980)는 이 평균을 마팅게일로 닫힌꼴로 구했다 — 공정한 동전이면 패턴 길이 $L$ 에 대해 “접두사=접미사”가 되는 길이 $\ell$ 마다 $2^\ell$ 을 더한 값이다(HHH: $2+4+8=14$).

두 패턴을 경주시키면 흡수 상태가 둘이 되고 $B=NR$ 이 승률을 준다. HHT와 HTH를 붙이면 상태 4개(빈 열, H, HH, HT)짜리 연쇄가 나오고, 계산하면 HHT가 먼저 나올 확률이 2/3 이다. 단독 평균 대기 시간(8 대 10)만 봐서는 이 비율이 안 나온다.¹

5. 수치적으로 푸는 법

• 역행렬을 만들지 마라. 필요한 것이 $t$ 나 $B$ 라면 $(I-Q)t=\mathbf 1$, $(I-Q)B=R$ 을 푼다. $Q$ 가 희소해도 $N$ 은 보통 꽉 찬 행렬이다. $I-Q$ 는 대각 우세에 가까운 M-행렬이라 희소행렬 직접 솔버도, 가우스-자이델 같은 반복법도 얌전하다.
• 흡수가 느린 연쇄는 조건이 나쁘다. $Q$ 의 최대 고유값이 $1-\varepsilon$ 이면 $\lVert N\rVert\sim 1/\varepsilon$ 이고 $I-Q$ 의 조건수도 그만큼 커진다. 행 합이 1에 가까운 상태에서 $1-\sum_j Q_{ij}$ 를 그대로 빼면 상쇄 오차가 나므로, 흡수로 새는 확률 $\sum_k R_{ik}$ 를 따로 들고 다니며 대각을 $\sum_{j\ne i}Q_{ij}+\sum_k R_{ik}$ 로 조립하는 편이 안전하다(정상 분포 계산의 GTH 알고리즘과 같은 발상이다).
• 몬테카를로와 비교. 표본 경로를 $M$ 개 굴려 평균을 내면 오차가 $\sqrt{v/M}$ 이다. 위 도박꾼 예처럼 분산이 평균의 몇 배면 수만 경로를 굴려야 소수 둘째 자리가 맞는다. 상태 수가 감당되는 한 선형계 한 번이 훨씬 싸고 정확하다. 흡수 확률이 $10^{-9}$ 처럼 작으면 단순 몬테카를로 방법은 사실상 0만 보고하니, 상태 공간이 너무 커서 선형계가 안 될 때는 희귀 사건 샘플링으로 간다.

6. 어디에 나오나

• 분자 시뮬레이션 — 커미터. 마르코프 상태 모형에서 반응물 집합 $A$ 와 생성물 집합 $B$ 를 흡수 상태로 바꾸면, 각 상태의 $B$ 흡수 확률이 커미터(committor) $q^+$ 다. $q^+=1/2$ 인 상태들이 전이 상태 앙상블이고, 전이 경로 이론의 반응 유속이 여기서 계산된다. 평균 접힘 시간은 같은 연쇄의 $t$ 다.
• 신뢰성 공학. 부품 고장·수리 상태를 마르코프 연쇄로 두고 시스템 고장 상태를 흡수로 바꾸면 $t$ 가 MTTF, $B$ 가 고장 모드별 확률이다. 연속 시간이면 $Q$ 대신 생성자 행렬의 일시 블록을 쓰고 $t=(-Q_{\text{gen}})^{-1}\mathbf 1$ 이 된다.
• 집단유전학. 개체 수 $N$ 인 중립 모란 모형에서 돌연변이 대립유전자 $i$ 개가 고정될 확률은 $i/N$ 으로 도박꾼 공식과 같다. 선택이 있으면 불공정 게임 공식이 된다.
• 강화학습과 게임. 종료 상태가 있는 마르코프 결정 과정에 정책을 고정하면 흡수 연쇄가 되고, 정책 평가가 $(I-\gamma Q)V=r$ 꼴의 같은 선형계다. 뱀과 사다리 같은 보드 게임의 평균 턴 수도 이 계산의 단골 예제다.²

7. 관련 문서

• 평균 첫 통과 시간 · 마르코프 결정 과정 · 마르코프 연쇄 몬테카를로 · 은닉 마르코프 모형
• M-행렬 · 노이만 급수 · 스펙트럼 반지름 · 조건수 · 반복법
• 몬테카를로 방법 · 희귀 사건 샘플링 · 마르코프 상태 모형 · 도박꾼의 파산

8. Footnotes

1. 이게 페니의 게임(Penney’s game)이다. 길이 3 패턴 경주에서는 상대가 무엇을 고르든 그보다 유리한 패턴이 항상 존재해서, 승률 관계가 가위바위보처럼 순환한다. 상대에게 먼저 고르게 하는 것이 필승 전략이다. 술자리 내기로 쓰면 친구를 잃는다. ↩

2. 뱀과 사다리는 플레이어 선택이 전혀 없는 순수한 흡수 마르코프 연쇄라서, “게임”이라기보다 주사위로 구동되는 선형대수 시연에 가깝다. 아이들은 모르는 게 낫다. ↩