대각화의 활용

학교 앞 대여소 A와 지하철역 대여소 B에 공유 자전거 100대가 있다. 하루 동안 A에 있던 자전거의 80%는 A로 돌아오고 20%는 B로 가며, B에 있던 자전거의 30%는 A로, 70%는 B에 남는다. 첫날 아침 100대가 모두 A에 있었다면, 며칠 뒤 두 대여소의 자전거 수는 어떻게 될까? 처음에 B에 모두 있었다면 결과가 달라질까? 운영 회사는 대여소마다 거치대를 몇 개씩 두어야 할까?

3.6.1전이행렬과 그 거듭제곱

대여소 A, B의 자전거 수를 벡터 \(\vec x_n = (a_n, b_n)\)으로 쓰면, 다음 날의 수는 \(a_{n+1} = 0.8a_n + 0.3b_n\), \(b_{n+1} = 0.2a_n + 0.7b_n\)이다. 이것은 행렬 \(M = \begin{pmatrix}0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}\)을 곱하는 일이어서 \(\vec x_n = M^n\vec x_0\)이다. 각 열의 합이 1인 이런 행렬을 전이행렬이라 하며, 다음 상태가 현재 상태에만 달려 있는 변화를 마르코프 연쇄라 한다. 며칠 뒤의 상태를 알려면 \(M^n\)을 구해야 하고, 대각화가 그 계산을 간단하게 만든다.

\(M\)의 고윳값은 대각합 1.5와 행렬식 \(0.56 - 0.06 = 0.5\)에서 1과 0.5이다. 고윳값 1의 고유벡터는 \((M - I)\vec v = \vec 0\), 곧 \(-0.2a + 0.3b = 0\)에서 \((3, 2)\)이고, 0.5의 고유벡터는 \((1, -1)\)이다. 처음 상태를 두 고유벡터로 나누면, 고윳값 1의 부분은 그대로 남고 0.5의 부분은 하루마다 절반으로 줄어든다. 그래서 결국 \((3, 2)\) 방향, 곧 A와 B가 \(3 : 2\)인 상태만 남는다. 처음 상태는 0.5의 부분의 크기만 바꿀 뿐이어서, 어디서 시작해도 같은 상태로 모인다.¹

3.6.2개체군의 앞날도 같은 방법으로

멸종 위기종의 개체 수를 어린 개체와 어른 개체로 나누고, 해마다 어린 개체가 어른이 되는 비율과 어른이 낳는 새끼 수로 행렬을 만들면 같은 방법으로 앞날을 예측한다. 이 행렬의 가장 큰 고윳값이 1보다 크면 개체 수가 늘고, 작으면 줄어 멸종에 다가간다. 그래서 어떤 생존율을 높여야 가장 큰 고윳값이 1을 넘는지 계산해 보호 정책을 정한다. 고유벡터는 오랜 시간이 지난 뒤 어린 개체와 어른 개체의 비율을 알려 준다.

3.6.3예제 풀이

\((100, 0) = 20(3, 2) + 40(1, -1)\)이므로 \(\vec x_n = 20(3, 2) + 40\times0.5^n(1, -1)\)이고, \(a_n = 60 + 40\times0.5^n\)이다. \(n = 3\)이면 65, \(n = 5\)이면 61.25로 그림 1과 같다.

\(40\times0.5^n < 1\)이려면 \(2^n > 40\), 곧 \(n \ge 6\)이다. 그래서 엿새째부터는 A에 거의 60대, B에 40대가 있다. 정상 상태에 날마다 오가는 흔들림을 고려해, A에 60대보다 조금 많게, B에 40대보다 조금 많게 거치대를 두면 된다. 즉 다음 상태가 행렬 곱으로 정해지는 변화는 전이행렬을 대각화해 고윳값의 거듭제곱으로 계산하고, 고윳값 1의 고유벡터가 오랜 뒤의 정상 상태를, 나머지 고윳값이 그 상태로 다가가는 빠르기를 알려 준다.

아래 탐구 카드에서 공유 자전거의 이동을 전이행렬로 계산해 정상 상태를 찾고, 멸종 위기종의 개체군 행렬에서 어느 생존율을 높여야 하는지 알아보자.

1. 마르코프 연쇄는 1906년 러시아의 마르코프가 소설 속 모음과 자음이 이어지는 규칙을 분석하며 처음 연구했다. 오늘날에는 날씨 예측, 웹 검색 순위, 스마트폰 자판의 다음 단어 추천에도 같은 생각이 쓰인다.