27차시 · 마르코프 연쇄
같은 전이 규칙을 반복하면 상태분포는 수렴할까?
다음 상태는 현재 상태에만 의존하고, 전이확률 $P$는 매 단계 일정하다고 가정한다.
이 가정에서 $x_{n+1}=Px_n$을 반복하고 정지분포와 수렴을 구분한다.
A 마을
100%
⇄
B 마을
0%
먼저 예상
$x_{n+1}=Px_n$에서 전체 비율 1을 지키려면 무엇이 필요할까?
여기서는 $x$를 열벡터로 쓰며, $P$의 $j$열은 $j$번 상태에서 이동할 확률을 나타낸다.
직접 반복
반복 횟수에 따라 상태분포의 변화량은 어떻게 변할까?
열 = 출발 · 행 = 도착
| A | B | |
|---|---|---|
| A | 0.8 | 0.3 |
| B | 0.2 | 0.7 |
0일
A · 100.0%B · 0.0%
초기분포 $x_0=(1,0)^\mathsf T$
매일 이동률: A→B 20% · B→A 30%
$A_n$$B_n$
규칙의 발견
정지분포는 $P\pi=\pi$를 만족하는 확률벡터
$$P\pi=\pi,\qquad \pi_1+\pi_2=1$$
이 이동 규칙의 정지분포는 $\pi=(0.6,0.4)^\mathsf{T}$이다.
열의 합이 1이므로 전체 확률은 보존된다. 그러나 보존만으로 수렴이 보장되지는 않는다.
조건의 구분
정지분포로의 수렴에는 추가 조건이 필요하다
- 구조 조건 1 · 기약성: 모든 상태 사이의 상호 도달 가능성
- 구조 조건 2 · 비주기성: 상태 복귀 시점의 최대공약수가 1
- 이때의 스펙트럼 표현: 고윳값 1은 단순하고 나머지는 $|\lambda|<1$
수렴하는 예
$\begin{bmatrix}.8&.3\\.2&.7\end{bmatrix}$은 모든 항이 양수이다.
진동하는 예
$\begin{bmatrix}0&1\\1&0\end{bmatrix}$은 두 상태를 번갈아 바꾼다.
PageRank 적용
텔레포테이션 항으로 수렴 조건을 확보한다
$$G=\alpha M+(1-\alpha)ve^\mathsf{T}$$$M$: 보정된 열확률 링크행렬 · $0<\alpha<1$
$v_i\ge0$, $e^\mathsf Tv=\sum_i v_i=1$: 텔레포테이션 확률벡터
$v_i\ge0$, $e^\mathsf Tv=\sum_i v_i=1$: 텔레포테이션 확률벡터
링크 따라가기
확률 α
+
무작위로 이동하기
확률 1−α
$v$의 모든 성분이 양수이면 $G$의 모든 원소도 양수이므로 $G$는 기약이고 비주기적이다.
개념 확인
$P=\begin{bmatrix}0&1\\1&0\end{bmatrix}$, $x_0=(1,0)^\mathsf{T}$. $x_n$의 장기 거동은?
핵심 정리
전이행렬의 반복과 고윳값으로 장기 상태분포를 분석한다.
확률 보존은 수렴을 보장하지 않는다. 기약성과 비주기성을 별도로 확인한다.
전이행렬정지분포기약성·비주기성