[선형대수학] 마코프 행렬(Markov matrix)의 특징

딥러닝에 대한 논문이나 자료를 찾다보면 Markov chain (MC), Markov decision process (MLP) 등의 용어들을 종종 만나게 된다. 뭔가 이름이 어려워보여 그 부분부터 막히곤 했다. 그것들의 기초가 되는 것이 Markov matrix다. 

▶ Markov matrix의 특성

Markov matrix는 모든 요소가 0보다 크거나 같고, 각 열 벡터들의 요소들을 더하면 1이 되는 행렬이다. Markov matrix인 A의 특성을 아래에 나열해봤다.

(1) 첫번째 고유값은 항상 1이다.

(2) 첫번째 고유벡터는 음이 아니고,이므로 steady state이다.

(3) 다른 고유값들의 절대값은 1보다 작거나 같다.  

(4) 의 해는 의 배수에 근사한다. 

하나의 예를 통해 이 특성들을 확인해보자. 아래와 같은 상황이 있다:

"매년 서울의 인구 중 10%는 부산으로 이동하고, 부산 인구의 20%가 서울로 이동한다. 현재 서울의 인구가 1000만, 부산의 인구가 400만이라고 하면 100년 후의 두 도시의 인구는 어떻게 될 것인가? (단, 서울, 부산에서 다른 도시로 인구의 이동은 없고, 다른 도시들에서 서울, 부산으로 인구의 이동도 없다.)"

이를 식으로 아래와 같이 나타낼 수 있다.

여기서 S0는 현재의 서울 인구, B0는 현재의 부산 인구, S1은 1년 후의 서울 인구, B1은 1년 후의 부산 인구를 나타낸다. 행렬을 이용하면, 아래와 같이 정리된다.

여기서 행렬 

는 Markov matrix이다. 모든 요소가 0보다 크거나 같고, 각 열의 요소를 더했을 때 1이 되기 때문이다. 

라고 하면, 로 즉, 의 차분방정식(difference equation)이 된다. 우리가 구해야하는 것은 100년 후의 두 도시의 인구임으로 이다. 만약 행렬 A가 대각화가 가능하다면, 행렬의 대각화를 이용해서 이 차분방정식을 풀 수 있다. 대각화 가능의 조건은 행렬 A가 서로 독립인 n개의 고유벡터들을 갖는 것이다. 그럼 먼저 행렬 A의 고유값들과 고유벡터들을 구해보자. 고유값과 고유벡터를 구하는 방법은 여기를 참고하자. (http://blueskyvision.tistory.com/59)

고유값들과 고유벡터들을 구해보면, 

이 된다. 구한 고유값들을 보니 하나는 1이고 하나는 1보다 작다(특성1과 특성3). 또한 첫번째 고유벡터는 음이 아니고 steady state다(특성2). 아래와 같이  이기 때문이다. 

두 고유 벡터가 서로 선형 독립이므로, 우리는 행렬의 대각화를 이용해서 위의 차분방정식을 풀 수 있다. 

여기서 

로 나타내면, 

이 된다. 차분방정식을 행렬의 대각화를 이용해서 푸는 자세한 방법은 아래를 참고하자. (http://bskyvision.com/156) 

0.7의 100승은 거의 0에 가까우므로 두 항에서 첫번째 항만 남게 되었다. 여기서 이 에 근사함을 확인할 수 있다(특성4). 최종적으로 100년 후의 서울의 인구는 약 933만명이 되고, 부산의 인구는 약 466만명이 된다. 서울의 인구는 감소했고, 서울의 인구가 감소한 만큼 부산의 인구는 증가했다. 

<참고 자료>

[1] Gilbert Strang, Linear algebra and its applications, 4판, p. 257-259

[2] Gilbert Strang 교수님의 markov matrix에 대한 동영상 강의 

=> http://videolectures.net/mit1806s05_strang_lec24/