6.1b Markov 행렬

Markov 행렬은 러시아의 수학자 Andrey Markov의 이름을 딴 행렬로 확률행렬(stochastic matrix)이라고도 불립니다. 이 행렬은 여러 분야에서 광범위하게 이용되고 있어 알아두면 도움이 될 것입니다.

 

Markov 행렬은 다양한 응용성을 가진 중요한 주제입니다. 이 때문인지 Gilbert Strang의 교과서에서는 이 행렬을 10장에서 다시 자세하게 다룹니다. 이번 포스팅에서는 Markov 행렬의 기본적인 내용들을 알아보겠습니다. 심화 내용과 구체적인 응용사례는 나중에 10장을 공부할 때 보도록 하겠습니다.

Markov 행렬의 특징

Markov 행렬은 다음 특징들을 갖는 행렬을 말합니다.
1) 행렬의 모든 성분이 0보다 크다. 
2) 각 열의 합이 1이다.

이 특징들을 보면 왜 Markov 행렬이 확률행렬이라고 하는지 알 수 있습니다. 각 성분은 어떤 확률을 의미하기 때문에 0보다 크고, 합이 1인 것은 100%를 의미합니다.

그러면 다음 예를 보겠습니다.
   
$A$ = $\begin{pmatrix} \begin{array}{rr} .8 & .3 \\ .2 & .7 \end{array} \end{pmatrix}$

$A$의 고유값을 구하기 위한 행렬식은

det($A\:-\:{\lambda}I$) = $\begin{pmatrix} \begin{array}{cc} .8 - {\lambda} & .3 \\ .2 & .7 - {\lambda} \end{array} \end{pmatrix}$ 

= ${\lambda}^{2}\:-\:\frac{3}{2}{\lambda}\:+\:{\frac{1}{2}}$ = (${\lambda}\:-\:1$)(${\lambda}\:-\:{\frac{1}{2}}$).

위 식에 의하면 $\lambda$ = 1 또는 $\lambda$ = $\frac{1}{2}$ 일때 det($A\:-\:{\lambda}I$) = 0. 
즉, 1과 $\frac{1}{2}$ 은 $A$의 고유값입니다.

그리고 고유벡터는 $Ax$ = ${\lambda}x$에 각 고유값을 대입하여 풀면 얻을 수 있습니다.

$\lambda$ = 1일 때 고유벡터는 $\begin{pmatrix} \begin{array}{r} .6 \\ .4 \end{array} \end{pmatrix}$.

$\lambda$ = $\frac{1}{2}$일 때 고유벡터는 $\begin{pmatrix} \begin{array}{r} 1 \\ -1 \end{array} \end{pmatrix}$.

*고유벡터의 상수배 역시 고유벡터가 됩니다.

$\lambda$ = 1일 때 $\begin{pmatrix} \begin{array}{r} 3 \\ 2 \end{array} \end{pmatrix}$도 고유벡터입니다.

 
$\begin{pmatrix} \begin{array}{r} .6 \\ .4 \end{array} \end{pmatrix}$는 Markov 행렬의 특성을 따라 구한 고유벡터입니다.

정상 상태(steady state)

위의 예에서 봤듯이 Markov 행렬은 고유값 1을 갖습니다. 고유값이 1이면 $Ax$ = $x$과 같이 $A$를 곱해도 고유벡터 $x$에는 변화가 없습니다. 이것은 $A^{100}$과 같은 거듭제곱을 곱해도 마찬가지입니다. 즉, $A^{100}x$ = $x$.

일반적으로 $A$의 거듭제곱을 곱할 경우
$A^{2}x$ = $A{\lambda}x$ = ${\lambda}Ax$ = ${\lambda}^{2}x$
$A^{3}x$ = ${\lambda}^{2}Ax$ = ${\lambda}^{3}x$
와 같이 고유벡터는 그대로지만 고유값은 마찬가지로 거듭제곱이 됩니다.

위 Markov 행렬의 예에서 두 고유벡터와 $A$의 거듭제곱을 그림으로 그리면 아래와 같습니다. 그림에서 $x_{1}$은 고유값이 1인 고유벡터이고 $A$의 거듭제곱을 아무리 곱해도 변화가 없습니다. 이에 반하여 $x_{2}$은 고유값이 $\frac{1}{2}$인 고유벡터이고 $A$를 곱할 때마다 크기가 반으로 줄어 $A^{100}$일 때는 크기가 거의 0이 됩니다. 

그림 1. Markov 행렬의 고유벡터와 행렬의 거듭제곱

 

확률 벡터

$A$ = $\begin{pmatrix} \begin{array}{rr} .8 & .3 \\ .2 & .7 \end{array} \end{pmatrix}$

위 Markov 행렬 $A$의 열 벡터들은 성분이 모두 음수가 아니고 합이 1입니다.

 

예를 들면

$\begin{pmatrix} \begin{array}{r} .8 \\ .2 \end{array} \end{pmatrix}$의 성분의 합은 0.8 + 0.2 = 1입니다.

여기서 1은 확률적으로 100%를 의미합니다.

위와 같이 모든 성분들이 0 이상이고 합이 1인 벡터를 ‘확률벡터’라고 합니다.

확률벡터 $u$에 Markov 행렬 $A$를 곱하면 $Au$ 역시 확률벡터입니다.

증명) 먼저 $Au$의 성분들은 모두 0 이상의 수들의 곱의 합이므로 역시 0 이상의 수입니다. 그러면 $Au$의 성분들의 합이 1임을 보이면 됩니다. 
$A$의 $i$번째 열을 $a_{i}$라고 하면 $A$ = [$a_{1}$ $a_{2}$ $\cdots$ $a_{n}$]과 같이 열 벡터로 나누어 쓸 수 있습니다. $u$ 역시 $i$번째 성분을 $u_{i}$로 쓰면 $Au$는 다음과 같이 벡터들의 선형 결합으로 쓸 수 있습니다.
$Au$ = $u_{1}a_{1}$ + $u_{2}a_{2}$ + $\cdots$ + $u_{n}a_{n}$.
열 벡터 $a_{i}$의 모든 성분의 합은 1이므로 
$Au$의 모든 성분의 합은 $u_{1}$ + $u_{2}$ + $\cdots$ + $u_{n}$.
이것은 확률벡터 $u$의 성분들의 합과 같으므로 1입니다.
따라서 $Au$의 성분들의 합은 1입니다.

사실 Markov 행렬은 확률벡터들로 만들어진 행렬입니다. 
그래서 $Au$가 여전히 확률벡터라는 것은 $A$의 거듭제곱 역시 Markov 행렬이라는 의미입니다. 

Markov 행렬의 고유값의 조건

Markov 행렬은 고유값으로 1을 꼭 가지고, 다른 고유값들은 1보다 절대값이 작아야 합니다.

이를 보이기 위해 확률벡터가 다음과 같이 고유벡터들의 선형 결합으로 쓸 수 있는 것에서 시작하겠습니다.

 

$\begin{pmatrix} \begin{array}{r} .8 \\ .2 \end{array} \end{pmatrix}$ = $\begin{pmatrix} \begin{array}{r} .6 \\ .4 \end{array} \end{pmatrix}$ + $0.2\begin{pmatrix} \begin{array}{r} 1 \\ -1 \end{array} \end{pmatrix}$

 

우변의 첫 번째 벡터는 고유값이 1, 두 번째 벡터는 고유값이 $\frac{1}{2}$ 입니다. 
그래서 우변에 A를 곱해줄 때마다 두 번째 벡터는 $\frac{1}{2}$ 배가 되어 작아지게 됩니다. (그림 1 참조)

 

따라서 $A^{n}\begin{pmatrix} \begin{array}{r} .8 \\ .2 \end{array} \end{pmatrix}$은 $n$이 클 수록 $\begin{pmatrix} \begin{array}{r} .6 \\ .4 \end{array} \end{pmatrix}$에 수렴합니다.

만약 고유값 중에 절대값이 1보다 큰 수가 있다면 $A$를 곱할수록 벡터는 커지고 발산하게 됩니다. 따라서 $A$의 고유값의 절대값은 1보다 클 수 없습니다. (고유값은 음수도 될 수 있습니다)

*그러면 Markov 행렬 $A$가 1을 고유값으로 가져야 하는 이유를 설명하겠습니다.

고유값을 계산하기 위한 특성방정식 det($A\:-\:{\lambda}I$) = 0에서 $\lambda$ = 1인 det($A\:-\:I$) = 0이 항상 성립함을 보이면 됩니다.

여기서 $I$는 단위행렬로 각 열에는 하나의 ‘1’인 성분이 있고 나머지 성분들은 모두 0입니다. 

따라서 $A\:-\:I$의 각 열의 성분들의 합은 언제나 0이 되어야 합니다. (Markov 행렬의 각 열은 성분들의 합이 1이라고 하였습니다.)

이것은 $A\:-\:I$의 모든 행을 더하면 모든 성분이 0인 행이 된다는 것을 의미합니다. 즉, $A\:-\:I$의 행 벡터들은 선형 종속이고 $A\:-\:I$는 비가역 행렬이어야 합니다. 그래서 det($A\:-\:I$) 은 항상 0이어야 합니다. 

(5.1b 행렬식의 규칙에서 규칙 8 참조)