[Linear algebra] 행렬의 극한과 마르코프 연쇄 (2)
이전 글에서는 Markov process 를 논하기 위해 행렬의 극한이 존재한다면 어디로 수렴하는지, 행렬 극한의 수렴 조건은 무엇이었는지를 살펴보았다. 또, 이로부터 한 가지 예시로 마르코프 과정이 현재 상태에서 다음 상태를 연이어 계산하고, 이를 극한으로 하여 계산한 A^np 를 계산해낼 때 앞서 논의한 행렬의 수렴에 관한 정리를 쓸 수 있었다.
Transition matrix 는 현재 상태에서 다음 상태가 어떻게 변할 지 작성해둔 Table 과 같은 것으로 기본적으로 확률을 entries 로 하기 때문에 1) 모든 요소가 nonnegative 이고, 2) 각 열의 합이 1이었다. 이번 포스팅에서는 이 transition matrix 의 핵심적인 특징 몇가지를 알아보도록 하자.
1. definition: regular, row sum (column sum) of A
어떤 transition matrix A가 regular 하다라고 하는 것은, 그 행렬 A를 거듭제곱하여 오직 양수인 entries 만 포함할 경우를 뜻한다.
- 위의 그림에서 위 행렬은 regular 하고, 아래 행렬은 regular 하지 않다.
행렬이 regular 한 지 판단은 그 행렬만 보고서는 알 수가 없다. (만약 어떤 n에 대해서 nxn 짜리 Identity matrix 가 행렬 A 안에 들어가있다면 regular 하지 않다, 고 확정할 수는 있지만) 따라서 아래의 계산은 M 에 0 entry 가 있음에도 이에 대한 거듭제곱은 regular 할 수 있음을 보여준다.
어떤 행렬 A의 row sum (column sum)은 그 행렬 A의 각 row sum (column sum) 중 가장 큰 것을 가리킨다.
아래의 에시를 보자. a+bi 로 표현된 복소수의 크기는 이를 실수축과 허수축으로 만든 복소평면에 표현할 때를 생각해 sqrt(a^2 + b^2) 처럼 계산할 수 있다고 하였다. 이를 감안하여 row sum 과 column sum 을 각각 계산해낼 수 있다.
2. Gershgorin Disk, Gershgorin Circile Theorem
위의 정의를 활용해 Gershgorin Disk 원에 대한 정리 하나를 보자. 갑자기 디스크가 왜 튀어나오는지 할 수 있지만, 행렬이 주어질 때 eigenvalue 의 범위(근사)에 대한 중요한 힌트를 주는 정리가 될 수 있다.
Gershgorin disk (게르시고린 원)은 아래와 같이 저의한다.
- i번째 게르시고린 원은, Aii 성분을 원의 중심으로 하고, 그 i행의 row sum 에서 Aii 절댓값만큼을 뺀 것을 반지름으로 하는 원을 뜻한다.
게르시고린 원 정리란, 모든 eigenvalue of A가 이 gershgorin disk 내부에 포함되어 있다는 것이다. 따라서 게르시고린 원 정리를 써서 얻을 수 있는 이점은, eigenvalue 를 직접 구하지 않아도, 또 복잡한 행렬 연산을 거치지 않아도 단순히 그 행렬 자체만 보고 eigenvalue 값을 근사해낼 수 있다는 것이다.
위의 예시의 경우, C1 은 (1+2i) 즉 (1, 2) 를 중심으로, 반지름 1인 원 안에 eigenvalue 하나와, C2 원 (-3, 0) 을 중심으로 반지름 2인 원 안에 eigenvalue 또다른 하나가 살 것임을 보여준다.
(Gershgorin Disk Theorem 증명)
보조정리
게르시고린 원의 정리에 대한 보조정리 몇가지를 보자.
- eigenvalue 의 크기는 A 행렬에 대한 row sum 보다 크지 않다. (같거나 작다)
- eigenvalue 의 크기는 A 행렬의 row sum, column sum 의 최솟값보다 크지 않다 (같거나 작다).
- 만약 A가 transition matrix 라면, eigenvalue 는 확정적으로 1보다 같거나 작다. (transition matrix 의 성질 1)
(보조정리에 대한 증명)
게르시고린 정리의 보조정리에 대한 증명은 정의로부터 시작하면 어렵지 않다.
- eigenvalue 가 Aii 를 중심으로 하고 반지름 r로 하는 원 내부에 있다고 했는데, 이때 r 자체가 = row sum - |Aii| 이었으므로, 이를 정리하면 행렬 A의 모든 i에 대해 row sum 보다 eigenvalue 가 작거나 같음을 알 수 있다.
- eigenvalue 의 크기가 row sum 보다 작거나 같다는 것이 위에서 보였던 것이고, 이를 각 행과 열을 transpose 한 A^t 에 대해서도 eigenvalue 값은 유지된다. 따라서, 이 값은 모든 i에 대해 column sum 보다 작다.
- transition matrix 는 column sum 이 모두 1이다. 따라서, eigenvalue 는 적어도 1보다는 같거나 작다.
(예시)
일반적인 행렬 거듭제곱의 수렴에 대해 다음을 이야기할 수 있다.
이전 포스팅에서 다룬 내용에 따르면, 이런 행렬이 있을 때 수렴 판단은 먼저 eigenvalue 를 구한 후 -> 그 값이 -1과 1 사이인지, 또는 1인지를 판단하면 되었지만.. 이제 직접 eigenvalue 를 구할 필요도 없다는 것! 보조정리에 따르면 eigenvalue 는 row sum, column sum 의 최솟값보다 같거나 작다. 여기서는 row sum = column sum = 0.8 이기에 eigenvalue 도 0.8보다 같거나 작고, 따라서 이 행렬의 극한은 수렴한다.
3. Transition matrix 의 다른 성질
이제까지 다룬 내용을 바탕으로 transition matrix 에 대해 다뤘던 성질은, 모든 column sum 이 1이므로 eigenvalue 는 이보다 같거나 작은 범위에 들어올 것이라는 것. 아래 이어지는 정리는 transition matrix 의 또다른 성질들을 보여준다.
- 모든 transition matrix 는 1을 eigenvalue 로 가진다.
A가 transition matrix 라면, A^transpose 한 것과 1의 열벡터를 곱하면 1의 열벡터가 그대로 나온다. 이는 transpose 할 때 행으로 가는 것들의 합이 모두 1이기 때문. 따라서 A^t 는 1을 eigenvalue 로 갖는데, A나 A^t 나 그 eigenvalue 는 모두 공유한다고 하였으므로, A 또한 1을 eigenvalue 로 갖는다.
- Matrix A의 모든 entries 가 positive and real numbers 일 때 | eigenvalue| 가 row sum 과 같으면, 그 eigenvalue 는 양수이며, eigenvector (1, 1, ... , 1) 을 가진다.
이에 대한 보조정리는 다음과 같다.
- 만약 A가 transition matrix 이고 eigenvalue 가 1이 아니라면, | eigenvalue| 는 1보다 작다. (eigenspace 의 dimension 은 1이다.)
아래의 이어지는 regular transition matrix 의 성질들을 계속해서 정리하자.
- 1의 algebric multiplicity 와 geom. mult. of 1 는 1로 같다.
- 거듭제곱의 극한이 존재한다.
- AL = LA = L 이다. 어차피 L로 수렴하므로.
- L (수렴하는 행렬) 의 열은 eigenvectors of 1 으르로 모두 동일하다.
Probability vector (stationary vector)
어느 확률벡터 w이든, transition matrix 의 거듭제곱에 곱해져서 극한을 이룰 수 있다. 그런데, 만약 A가 regular transition matrix 라면, 어느 w에서건 이 극한값이 같다.
이렇게 transition matrix 거듭제곱 X w 의 극한값이 v로 같을 때 (이는 eigenvector 1의 열로 채워진다고 하였고), 이 v를 fixed vector 또는 stationary vector 라 한다. 따라서, regular transition matrix A를 모델로 갖는 Markov chain 을 분석, 극한값을 계산하고자 할 땐, eigenvector corresponding to eigenvalue 1 을 계산하면 끝이다!
예시
-
주어진 transition matrix 는, eigenvalue 1을 가질 것이므로, 대각행렬에서 1을 빼고 어떤 것이 0으로 가게 하는지 eigenspace of 1을 구해주면, 그게 fixed vector (probability vector)가 된다.
-
계산결과 (1 1 1) 이 적절한 fixed vector 로 나왔는데, 이때 span{(1,1,1)} 중 합이 1이 되도록 하는 확률 벡터가 필요하므로, (1/3, 1/3, 1/3) 으로 수렴할 것이라 보면 된다.
4. Application to Genetics (Hardy-Weinberg law)
(작성 중)
