27차시 · 정의와 표기

확률벡터와 전이행렬

유한한 상태를 \(1,\ldots,d\)라 하자. 상태분포 \(x_n\)은 \(n\)단계에 각 상태에 있을 확률을 담은 열벡터이며 \(x_{n,i}\ge0\), \(\sum_i x_{n,i}=1\)이다.

다음 상태의 조건부 확률이 과거 전체가 아니라 현재 상태만으로 정해지는 모형을 마르코프 연쇄라고 한다. 여기서는 전이행렬 \(P\)가 매 단계 같다고 가정하여 \(x_{n+1}=Px_n\)으로 계산한다. 열은 출발, 행은 도착이다.

27차시 · 계산과 논증

열의 합이 1이라는 조건은 왜 필요한가?

① \(P\)가 전이행렬이고 \(x\)가 확률벡터일 때 \(Px\)도 확률벡터임을 증명하라. ② 행의 합만 1인 다음 행렬에 \(x=(1,0)^T\)를 넣고 문제를 설명하라.

27차시 · 정의와 표기

정지분포와 수렴의 구별

전이행렬 \(P\)에 대해 \(P\pi=\pi\)를 만족하는 확률벡터 \(\pi\)를 정지분포라고 한다. 고윳값 1의 고유벡터 중 성분이 음이 아니고 합이 1인 벡터이다. \(\mathbf1\)은 성분이 모두 1인 열벡터이므로 \(\mathbf1^T\pi\)는 성분의 합이다.

정지분포에서 출발하면 분포가 그대로이다. 모든 초기분포 \(x_0\)에 대해 \(P^nx_0\to\pi\)가 되는지는 다른 질문이다. 다음 계산에서 정지분포를 먼저 찾고 반복의 수렴을 따로 확인한다.

27차시 · 유도와 계산

정지분포를 방정식으로 계산

\(P\pi=\pi\)와 확률의 합 1을 함께 사용합니다.

정지분포는 움직이지 않는 분포입니다. 모든 초기분포가 여기에 수렴하는지는 주기성과 다른 고윳값을 별도로 살펴야 합니다.

27차시 · 정의와 표기

기약성·주기·수렴 조건

어느 상태에서 출발해도 다른 모든 상태에 유한 단계 안에 양의 확률로 갈 수 있으면 기약이라고 한다. 상태 \(i\)의 주기는 돌아올 수 있는 단계 수들의 최대공약수이다.

기약 연쇄에서 이 주기가 1이면 비주기라고 한다. 유한 상태의 기약·비주기 연쇄는 유일한 정지분포를 가지며 모든 초기분포가 그곳으로 수렴한다.

모든 \(P_{ij}>0\)이면 두 조건이 성립한다. 앞의 2상태 예에서는 \(x_{n,A}-.6=.5^n(x_{0,A}-.6)\)이므로 오차가 매번 절반이 된다.

27차시 · 정의와 표기

페이지랭크의 전이 규칙

링크를 따라 이동하는 행렬을 \(M\)이라 한다. 나가는 링크가 없는 페이지의 열은 미리 확률벡터 \(v\)로 채워 모든 열의 합을 1로 만든다. \(\mathbf1\)은 성분이 모두 1인 열벡터이다.

확률 \(\alpha\)로 링크를 따르고 확률 \(1-\alpha\)로 \(v\)에 따라 새 페이지를 선택한다. \(v\mathbf1^T\)의 모든 열은 \(v\)이다. 페이지랭크는 \(G\pi=\pi\)인 정지분포 \(\pi\)의 각 성분이다.

\(G_{ij}\ge(1-\alpha)v_i>0\)이므로 유일한 정지분포로 수렴한다. \(v_i=0\)을 허용하면 이 양수성 근거를 그대로 쓸 수 없다.

27차시 · 계산과 논증

주기적인 왕복에 임의 이동을 섞기

① \(M\)의 정지분포와 \(M^nx_0\)의 거동을 구하라. ② \(\alpha=.8\)인 \(G\)를 구하고, 차이 \(d_n=x_{n,1}-x_{n,2}\)의 점화식으로 수렴을 설명하라.