이번 포스팅에서는 마코브 행렬(Markov matrix)에 대해 다루도록 하겠다. 마코브 행렬은 이전 강의에서 다루었던 행렬의 대각화 Lecture 22와 관련이 깊기 때문에 앞선 포스팅을 먼저 학습하길 바란다.
1. 마코브 행렬과 마코브 체인
- What is the Markov matrix and Markov chain?
마코브 행렬(Markov matrix)은 1906년에 러시아의 수학자 Andrey Markov에 의해 처음으로 언급된 개념이다. 마코브 행렬은 마코브 체인(Markov chain)을 기술하기 위한 수학적 도구인데, 확률적 방법을 기반으로 하기 때문에 확률 행렬(stochastic matrix or probability matrix)로 불리기도 한다.
여기서 마코브 체인은 확률을 이용하여 어떤 객체 상태를 시간에 따라 어떻게 변화할지를 모델링(modeling)하는 것이다. 말이 약간 어려워 보이지만 쉽게 말하자면 날씨 예측, 인구 이동 예측 등과 같이 어떤 객체(날씨, 인구)의 상태(맑음, 흐림, 10만명, 5만명, ...)가 시간이 지남에 따라 어떻게 변화할지를 확률을 이용하여 예측하는 것이다. 체인(chain)이라는 단어가 의미하듯이 객체의 시간에 따른 서로 다른 상태를 어떻게 연결할지를 기술하는 것이 마코브 체인이며, 이들을 연결시켜주는 매개체 역할을 마코브 행렬이 하는 것이다.
마코브 체인(Markov chain)은 마코브 프로세스(Markov process)와 혼용되기도 하는데, 이 둘을 구분 짓는 정확한 정의는 없다. 다만 일반적으로 객체의 상태 공간이 이산 시간(discrete time)이면 마코브 체인, 연속시간(continuous time)이면 마코브 프로세스로 정의한다.
마코브 행렬은 다른 말로 전이 행렬(transition matrix), 또는 치환 행렬(substitution matrix)이라고도 한다. 마코브 행렬이 왜 이렇게 불리는지 아래의 그림을 통해 알아보자.
Fig. 1 삼성 갤럭시 핸드폰과 애플 아이폰의 시장 점유율 예측에 관한 마코브 체인 상태 전이 다이어그램(Markov chain state transition diagram)
Fig. 1은 삼성 갤럭시 핸드폰과 애플의 아이폰에 대한 시장 점유율을 마코브 체인으로 표현한 것이다. 물론 수치는 임의로 정한 것들이다. Fig. 1과 같은 도표를 마코브 체인 상태 전이 다이어그램(Markov chain state transition diagram)이라고 한다. 마코브 체인은 기본적으로 각 상태들이 다른 상태로의 전이(transition)가 얼마의 확률로 이루어질 것인가를 기술한다.
애플의 아이폰을 사용하는 것을 state 1, 삼성의 갤럭시 핸드폰을 사용하는 것을 state 2로 각각 정의했고, 각 상태가 다른 상태로 전이되는 행위를 화살표로 표시하였다. 상태전이는 자기 자신으로 될 수도 있는데, 아이폰의 경우 상태(state)가 자기 자신으로 전이되는 것은 현재 아이폰을 사용하고 있는 유저가 계속 아이폰을 사용하는 것을 의미하며, 그 확률을 71.4%로 정의하였다. 반면 아이폰을 쓰던 유저가 갤럭시폰으로 갈아탈 확률은 28.6%라고 정의하였다. 이것을 state 1에서 state 2로 상태가 전이 될 확률로 해석할 수 있다.
마찬가지로 삼성의 갤럭시폰을 쓰던 유저가 계속 갤럭시 폰을 사용할 확률은 63.7%, 아이폰으로 갈아탈 확률은 36.3%로 각각 정의하였다. 이것이 마코브 체인 상태 전이 다이어그램이다.
우리가 이와 같이 마코브 체인을 구성한 이유는 앞선 문제의 경우엔 결국 핸드폰 사업에서 두 회사의 앞으로의 시장 점유율을 예측하기 위함이다. 마코브 방법을 이용하여 앞으로의 상태를 예측하기 위해선 먼저 위 그림과 같이 마코브 체인을 정의하고, 현재 시간의 상태와 그 다음 시간의 상태 사이를 연결시켜줄 수 있는 매개체인 마코브 행렬을 구해야한다. 마코브 행렬은 마코브 체인에서 각 상태로 전이될 확률만 나오면 쉽게 구할 수 있다. Fig. 1의 마코브 체인에 대한 마코브 행렬은 아래와 같다.
식 (1)의 좌측의 행렬 M이 바로 마코브 행렬(Markov matrix)이다. 행렬의 각 원소는 어떤 상태에서 자기 자신, 혹은 다른 상태로 전이될 확률값을 가진다.
행렬을 해석할 땐 column의 인덱스를 시작 상태로 보고, row의 인덱스를 전이 되는 상태로 보면 된다. 즉 M의 첫 번째 column인 Apple을 시작 상태로 봤을 때, 다시 Apple이 될 확률을 row 1로 보고 이때의 값은 0.714가 된다. Apple에서 Samsung으로 전이 될 확률은 row 2가 되며, 이때의 값은 0.286이다. 마찬가지로 두 번째 column인 Sam을 시작 상태로 봤을 때, Apple로 상태가 전이 될 확률은 row 1이 되고 그 값은 0.363이 되며, 다시 자기 자신인 Sam으로 될 확률은 row 2이고 값은 0.637이다. 결국 어떤 시작 상태에서 다시 자기 자신이 될 확률은 column과 row가 같은 인덱스를 가질 때이며, 각 column의 인덱스를 시작 상태로 하여 다른 상태로 전이될 확률을 보고 싶으면 각 column에 해당하는 row의 원소들을 보면 된다.
식 (1)의 우측에 있는 u는 Fig. 1에서 Apple과 Samsung의 현재의 시장 점유율을 의미한다. 주어진 마코브 행렬의 우측에 u를 곱한 결과는 다음 시점에서의 시장 점유율의 예측값이 된다.
참고로 필자가 마코브 행렬을 표현한 방식은 column을 기준으로 만든 행렬인데, 어떤 사람들은 row를 기준으로 행렬을 구성하기도 한다. 즉 row인덱스가 시작 상태가 되고 column이 전이될 상태를 의미하는 것이다. 이 경우 마코브 행렬은 column 기준 마코브 행렬이 전치(transpose)된 형태가 되며, 현재 상태인 u도 역시 전치된 row 벡터 형태로써 M의 좌측에 곱해진다. 어떤 방법이 더 옳다고 할 순 없지만, 필자는 column 기준 방식을 선호하기 때문에 이번 강의에서는 column 기준 마코브 행렬을 사용하도록 하겠다.
이제 마코브 체인(Markov chain)과 마코브 행렬(Markov matrix)이 어떤 것을 의미하는지 대략적으로 파악했을 것이다. 자세한 풀이는 이후에 하도록 하고 먼저 마코브 행렬이 가지는 특성에 대해서 알아보도록 하자.
2. 마코브 행렬의 특성
- Properties of Markov matrix
아래 행렬은 임의의 3x3크기의 마코브 행렬을 만든 것이다.
식 (2)에 표현된 마코브 행렬에서 어떤 특징이 보이는가?
마코브 행렬의 첫 번째 특징은 모든 원소의 값이 0보다 크거나 같다는 것이다. 즉 오직 양수만 허용된다. 마코브 행렬은 기본적으로 상태들의 전이 확률(transition probability)을 나타내기 위한 행렬이므로 확률값을 원소로 가진다. 확률 값에는 음수가 있을 수 없기 때문에 마코브 행렬의 원소값들은 반드시 0보다 크거나 같은 양수만 올 수 있다. 또한 마코브 행렬은 시간이 지남에 따라 변화하는 상태를 기술 및 예측하기 위한 행렬이므로 행렬의 거듭제곱이 발생한다. 이때 거듭제곱의 결과값도 모두 양수가 된다.
두 번째 특징은 각 column의 원소의 합은 1이 된다는 것이다. 식 (2)의 column 1의 원소들을 모두 더해보자. 그 결과값은 1이 되고, column 2, column 3도 마찬가지이다. 이 두 번째 특징은 마코브 행렬을 거듭제곱해도 마찬가지로 성립한다. 즉 M2=MxM 이라고 했을 때(M은 마코브 행렬을 의미), M2의 각 column 원소들의 합은 역시 1이 되는 것이다. column의 원소의 합이 1이 되어야 하는 이유는 하나의 column은 어떤 상태에 대한 모든 전이 확률을 나타내기 때문이다. 즉 column 1이 자기 자신이 될 확률(row1), 상태 2(row2)나 상태 3(row3)이 될 확률을 각각 기술하고 있으며, 따라서 하나의 상태에 대한 모든 전이 확률을 나타내는 것이기 때문에 column의 합은 1이 되어야한다.
이 두 가지 특성을 정리하면 아래와 같다.
모든 원소들이 0보다 크거나 같아야 한다. 모든 각 column원소들은 더했을 때 1이 되도록 해야한다. 이것이 마코브 행렬(Markov matrix)이 가지는 기본적인 특성이다.
- Eigenvalues of Markov matrix and steady state
마코브 행렬은 고유값에 대한 한 가지 특성을 가진다. 이 특성을 이해하기 위해선 정상 상태(steady state)에 대해서 먼저 이야기해야 한다. 정상상태는 지난 미분방정식과 선형대수에 대한 강의 Lecture 23-(1)에서 언급된 바 있다. 해당 강의에서 우리는 미분방정식에서 해가 시간이 지남에 따라 크게 세 가지 형태가 될 수 있다고 하였으며, 그 형태는 각각 안정 상태(stability), 정상 상태(steady state), 발산(divergence)이다. 안정 상태가 되려면 행렬의 모든 고유값이 0보다 작아야하고, 정상 상태일때는 하나의 고유값이 0이고 나머지가 0보다 작아야 한다. 그리고 어느 하나의 고유값이라도 0보다 크면 그 해는 발산한다. 미분방정식의 해가 고유값에 따라 세 가지 형태를 띄는 이유는 미분방정식의 일반해(general solution)의 형태를 보면 쉽게 유추할 수 있다. 해당 강의의 일반해에 대한 식을 다시 써보자.
식 (4)은 행렬로 정의된 미분방정식의 일반해에 대한 식을 나타낸다. 보다시피 일반해는 계수값 c1, c2, 지수 함수(exponential function)의 지수부에는 고유값이, 그리고 고유벡터 x1, x2의 선형 조합(linear combination)으로 구성되어 있다. 계수값 c와 고유벡터 x는 상수이기 때문에 고정되고, 변수 t와 곱해지는 고유값이 해(solution)에 영향을 미치게 되는데, 고유값이 0인 경우 지수 함수가 1이 되기 때문에 극한의 시간으로 가도 그 값은 결국 상수 c와 x의 곱으로 유지가 된다. 고유값이 0보다 작을 경우엔 시간이 지날 수록 값이 작아져서 결국엔 0이 된다. 이것이 하나의 고유값이 0이고, 나머지 고유값이 0보다 작을 경우 정상 상태가 되는 이유이다.
이에 대한 자세한 사항은 해당 강의를 참조하자.
여기서 우리가 관심을 가져야 하는 상태는 바로 정상 상태(steady state)이다. 그 이유는 마코브 행렬(Markov matrix)이 정상 상태(steady state)의 특성을 가지기 때문이다. 여기서 "마코브 행렬이 정상 상태의 특성을 가진다고? 그렇다면 마코브 행렬의 고유값 중 하나는 0의 값을 가지겠군!" 라고 생각하는 사람들이 있을 것이다. 그러나 이건 잘못된 생각이다. 미분방정식의 경우엔 일반해에서 고유값의 위치가 지수함수의 지수부이다. 따라서 지수함수를 시간에 상관없이 1로 만들기 위해선 고유값이 반드시 0이어야 한다.
그러나 마코브 행렬의 경우엔 미래의 일을 예측하기 위해서는 행렬을 거듭제곱(power)해야 한다. 행렬을 거듭 제곱 함에 있어서 행렬의 고유값이 0이라면, 그리고 나머지 고유값들의 크기가 1보다 작다면 이 행렬의 거듭제곱의 결과값은 얼마 못가 0이 되고 만다. 행렬의 거듭제곱을 함에 있어 해당 행렬이 정상 상태의 특성을 가지기 위해선 아래의 두 가지 조건을 충족시켜야 한다.
행렬의 거듭제곱에서 정상 상태의 특성을 보이기 위해선 적어도 하나의 고유값은 1이어야 한다. 그리고 다른 모든 고유값들의 크기는 1보다 작아야한다. 마코브 행렬은 이 두 가지 조건을 충족시키는 행렬이고, 결과적으로 행렬의 거듭제곱(power)에 있어서 정상 상태(steady state)의 특성을 갖는다. 조건 (5)에 대한 내용을 MATLAB을 통해 검증해보자.
Fig. 2 고유값에 따른 행렬의 거듭제곱 결과. [Upper left] 고유값=1일 때. [Lower right] 고유값=0일 때
Fig. 2는 고유값에 따라 행렬의 거듭제곱 결과가 어떻게 나오는지를 MATLAB을 통해 검증한 결과이다. 왼쪽 상단(파란색 영역)은 하나의 고유값이 1이고 나머지 고유값의 크기가 1보다 작을 때 행렬을 100번을 거듭제곱 한 결과이다. rst=로 표현된 값이 행렬을 거듭제곱한 결과인데, 어떤 특정 값으로 수렴하는 모습을 보인다. 따라서 조건 (5)를 만족시키는 마코브 행렬은 정상 상태(steady state)의 성질을 가짐을 증명하였다.
행렬의 거듭제곱의 결과값인 rst=로 표시된 값 아래에 LC1=로 표시된 결과가 나오는데, 앞서 계산한 거듭제곱의 결과(rst=)와 그 값이 같은 것을 볼 수 있다. LC1=로 표현된 값은 소스코드의 맨 아래 줄에 의해 계산된 값인데, 어디서 많이 본 기억이 날 것이다. 바로 지난 강의 Lecture 22의 행렬의 대각화에서 배운 내용이다. 행렬의 대각화 강의에서 우리는 계차방정식(difference equation)의 해를 행렬의 대각화를 통해 구했는데, 그때 행렬을 일일이 거듭제곱을 하지 않고서도 행렬의 고유값과 고유벡터, 그리고 계수의 선형조합의 형태로 해를 효율적으로 구하는 방법을 배웠다. 잘 기억나지 않는 분들을 위해 식을 다시 써보면 아래와 같다.
식 (6)과 같이 행렬의 거듭제곱을 일일이 계산할 필요가 없다. 단지 행렬의 고유값과 고유벡터를 알면 훨씬 적은 계산량으로 구할 수 있으며, LC1이 그 결과값이다. 여기서 중요한 포인트는 계수 c1, c2와 고유벡터 x1, x2는 상수이기 때문에 고정된 값이고, 우리가 주목해야 할 값은 고유값이라는 것이다. 즉 고유값이 어떻게 나오느냐에 따라서 해당 행렬이 발산하는지, 정상 상태(특정 값으로 수렴)인지, 0으로 수렴하는지가 결정이 되는데 그 이유는 식 (6)과 같이 나머지는 상수이고 고유값만 k의 거듭제곱으로 표현이 되기 때문이다. Fig. 2에 나온 문제를 예로 들자면 첫 번째 고유값은 1이고, 100제곱을 하던 1000제곱을 하던 그 결과는 항상 1이다. 반면 두 번째 고유값은 그 크기가 1보다 작은 0.351이기 때문에 거듭제곱을 할 수록 그 값은 작아져서 0에 가까워지게 된다.
식 (7)을 통해 말할 수 있는 것은 Fig. 2의 M1 마코브 행렬의 정상 상태가 바로 (7.2)인 c1x1이라는 것이다. 결국 마코브 행렬의 정상 상태(steady state)는 λ=1에 대응되는 고유벡터(eigenvector)라 할 수 있다.
반면 Fig. 2의 오른쪽 하단(붉은색 영역)의 경우를 보면 마코브 행렬 M2가 0인 고유값을 가지는 것을 볼 수 있다. 또한 나머지 고유값의 크기도 1보다 작기 때문에 결과적으로 0행렬의 결과를 보인다. 이를 통해 행렬을 거듭제곱 함에 있어 정상 상태(steady state)의 특성을 보이기 위해선 조건 (5)를 만족시켜야 함을 알 수 있다.
물론 마코브 행렬이면서 위의 조건을 충족시키지 않는 예외 적인 경우도 있는데, 바로 단위 행렬(identity matrix)이 그 경우다. 조건 (3)을 만족시키기 때문에 마코브 행렬이라 할 수 있지만, 정상 상태를 위한 조건 (5)는 만족시키지 않는다. 하지만 거듭 제곱(power)을 해도 발산하거나 0행렬이 되지 않기 때문에 결과적으로는 정상 상태라고 할 수 있다. 예외 적인 경우이니 잘 알아두도록 하자.
- Eigenvalue 1
앞서 우리는 마코브 행렬이 정상 상태의 특성을 가지기 위해선 반드시 하나의 고유값이 1이어야 함을 배웠고, 이를 계차방정식을 이용하여 이를 설명하였다. 하지만 계차방정식 이외에도 고유값이 1이어야 하는 것을 설명할 수 있다. 바로 조건 (3)-2의 각 column의 합은 1이 된다는 조건으로부터 고유값이 1이어야 한다는 것을 설명할 수 있다. column의 합이 1이 된다는 조건과 고유값이 1인 것이 무슨 관계지? 라는 의문이 들 것이다. 하나씩 풀어나가보자. 앞서 만들었던 임의의 마코브 행렬 (2)를 다시 써보자.
식 (2)는 각 원소의 크기가 0보다 크고 각 column의 합이 1이 되는 조건을 충족하는 마코브 행렬이다. 이제 이 행렬의 고유값을 구한다고 생각해보자. 고유값을 구하기 위해선 det(A-λI)를 계산해야 하는데, 우리는 A의 고유값이 λ=1임을 가정했기 때문에 (A-I)를 계산해보도록 하겠다.
식 (8)은 A-I를 계산한 모습을 나타낸다. 원래 행렬 A의 특징 중 하나가 각 column의 합이 1이 되는 것이었는데, 단위 행렬을 빼고 나니 각 column의 합이 0이 되는 특징을 보인다. 이때 이 column의 합이 0이 되는 특성이 의미하는 것은 곧 A-I가 특이 행렬(singular matrix)임을 의미한다. 어째서 그럴까? 바로 0벡터 이외의 null space가 존재하기 때문이다. 이 null space가 존재하는지를 계산해보지도 않고 어떻게 바로 알 수 있을까? 그 힌트는 바로 식 (8)에 이미 나와있다.
식 (8)의 행렬 A-I는 모든 각 column이 더했을 때 0이 된다. 이는 바꿔말하면 A-I 행렬의 row들이 dependent함을 의미한다. 즉 A-I는 transpose를 시켰을 때 null space가 존재한다는 의미다. Lecture 10을 공부했다면 A-I의 transpose의 null space가 Left Null Space라는 것을 알 것이다. 식 (8)의 Left null space를 정리하면 아래와 같다.
식 (9)에 보이는 것 처럼 0벡터 이외의 $(A-I)^T \boldsymbol{x}=0$를 만족시키는 벡터가 존재하므로 (A-I)는 Left null space가 존재한다. Left null space의 값은 column을 다 더했을 때 0이 된다는 사실로부터 쉽게 유추할 수 있는데, 이 상태에서 전치(transpose)를 시켰을 때 모든 column을 그대로 더하면 0벡터가 나옴을 알 수 있고, 따라서 각 column에 계수 1을 곱해주면 된다는 결론이 나온다. 이렇게 되면 Left null space의 값은 식 (9)에서와 같이 $[1 \; 1 \; 1]^T$ 가 되어야만 한다.
한편으로 Left null space가 존재한다는 의미는 곧 (A-I)는 full rank가 아니라는 의미가 되며, (A-I)의 column이 dependent하다는 결론을 내릴 수 있다. 따라서 아래와 같이 (A-I)의 null space도 존재하게 된다.
식 (10)에서 (A-I)의 null space를 계산하였다. 그런데 생각해보면 식 (10)의 null space를 구하는 식은 사실 우리가 가정했던 "마코브 행렬 A는 고유값 λ=1을 가진다"는 사실로부터 출발하였고, (10)에서 구한 고유벡터는 A의 λ=1에 대응되는 고유벡터이다. 이것이 곧 A의 정상 상태(steady state)라고 할 수 있다. 결과적으로 마코브 행렬의 각 column은 더했을 때 그 크기가 1이 된다는 성질로 부터 마코브 행렬의 최소 하나의 고유값은 1이 된다는 사실을 연결지어 설명하였다. 설명이 조금 길어져서 잘 이해가 안될 수 있기 때문에 다시 한 번 정리해보자.
-> 마코브 행렬은 적어도 하나의 고유값이 λ=1이 된다. -> 왜냐하면 마코브 행렬의 각각의 column은 더하면 1이 되기 때문이다. -> 그 이유를 알아보자. 일단 고유값을 λ=1로 가정하고 고유값을 구하면 det(A-I)으로 구할 수 있다. 이때 (A-I)는 각 column을 더하면 0이 된다. 이 사실로 부터 (A-I)는 singular임을 알 수 있다. -> 왜냐하면 (A-I)의 row가 dependent하기 때문이다. -> (A-I)의 row가 dependent한 이유는 (A-I)가 left null space인 [1, 1, 1]T를 가지기 때문이다. -> (A-I)가 left null space를 가진다면, 즉 (A-I)^T가 null space를 가진다면, (A-I)는 full rank가 아니다. -> (A-I)가 full rank가 아니라면 (A-I)의 column도 역시 dependent하다. -> (A-I)의 column이 dependent하다면, (A-I)는 null space를 가진다. -> (A-I)의 null space는 (A-I)x=0을 만족시키는 x값들인데, 이는 애초에 λ=1임을 가정하였다. -> 따라서 (A-I)의 null space는 λ=1에 대응되는 고유벡터 x이며, 이 x가 마코브 행렬의 정상 상태(steady state)이다. |
또 다른 관점에서는 A의 행렬식의 성질로부터 이를 유추할 수 있다. Lecture 18에서 행렬식의 특성 10번으로 부터 A와 A의 transpose는 같은 고유값을 가진다는 것을 알 수 있다. A transpose가 고유값 1을 가질 때, 앞에서와 같이 null space [1, 1, 1]T를 가진다. 즉 A입장에서는 left null space를 가지는 것이다. 그런데 A는 A transpose와 같은 고유값을 가지므로 λ=1을 가질 것이고, 그에 따른 고유벡터도 존재하게 된다. 여기서 고유값 1에 대응되는 고유벡터가 마코브 행렬 A의 정상 상태이다. A와 A transpose는 같은 고유값을 가질 수는 있으나, 같은 고유값에 대응되는 각각의 고유벡터는 다를 수 있음에 유의하자.
3. 마코브 행렬의 응용
- i-Phone vs Galaxy S
이제 앞서 제시했던 문제를 풀어보도록 하자. Fig. 1에서 우리는 애플의 아이폰과 삼성의 갤럭시 핸드폰의 시장 점유율 예측에 대한 가상의 문제를 마코브 체인으로 모델링 하였다. 또한 마코브 체인에 대한 마코브 행렬을 식 (1)에 정리하였다. 일단 이 마코브 행렬을 다시 써보자.
앞서 언급한 것과 같이 식 (1)의 M은 아이폰과 갤럭시폰 유저들의 상태가 전이될 확률을 표현한 마코브 행렬, u는 현재의 상태(시장점유율)를 나타낸다. 만약 상태 전이에 대한 예측 단위가 한 달 단위로 이루어진다고 가정해보자. 올해 1월의 시장 점유율은 아이폰이 49.2%, 갤럭시가 50.8%를 차지하고 있다. 그렇다면 2월의 시장점유율을 예측하려면 어떻게 해야할까? 이미 모델링 해놓은 마코브 행렬을 u의 좌변에 곱해주면 된다. 실제 계산을 해보면 2월의 시장점유율 예측치는 아래와 같이 계산할 수 있다.
Fig. 3 아이폰과 갤럭시폰의 마코브 체인
Fig. 3은 시장점유율의 계산을 위한 마코브 체인을 나타낸다. 1월의 시장점유율 벡터인 [0.492, 0.508]T를 마코브 행렬에 곱해주면 그 결과는 2월의 시장점유율이 되고 값은 [0.535, 0.464]T가 된다. 다시 2월의 시장점유율을 마코브행렬과 곱해주면 3월의 시장점유율에 대한 예측치가 나온다. 아래 식은 계산 과정을 나타낸다.
식 (11)에 표현된 식들을 보고 약간 익숙하게 느끼는 분들이 있을 것이다. 바로 계차방정식 $u_{k+1}=Au_k$ 와 같은 형태이다. 이 말은 마코브 체인을 계차방정식으로 생각할 수 있고, 결국 고유값과 고유벡터의 선형조합의 형태로 표현하여 해를 구할 수 있다는 의미다. 우리는 이미 식 (6)에서 계차방정식의 해에 대한 식을 보았으므로 여기에 필요한 고유값과 고유벡터를 구해보자.
기존에 고유값을 구할 때 행렬식(determinant)을 이용했는데, 식 (12.1)에서는 행렬식을 이용하지 않고 고유값의 합은 행렬의 trace와 같다는 성질을 이용하여 간단히 구했다. 행렬 M이 마코브 행렬임을 이미 알고있기 때문에 첫 번째 고유값은 1임을 미리 알 수 있으며, 나머지는 M의 trace에서 1을 빼주면 간단히 구할 수 있다. 물론 이 trace성질은 2x2행렬에 국한된 것임을 유의하자.
식 (12.2)와 (12.3)에서는 각각 고유벡터를 구한 뒤, 정규화(normalization)를 해주었다. 이제 필요한 값들을 모두 구했으니 해를 구해보자.
식 (13.2)에서는 계수값 c를 계산하였다. 이는 식 (13.1)에서 k=0으로 놓고 계산한 것이다. 식 (13.3)에서는 계수, 고유값, 고유벡터의 실제 값을 대입하여 정리하였다. 이제 이 식을 기반으로 향후 시장 전망을 예측할 수 있다. 물론 몇 step까지는 행렬을 일일이 곱하여 계산할 수도 있다. 하지만 이는 행렬의 크기가 커질 경우 속도가 매우 느리고 비효율적이다. 만약 어떤 마코브 체인 문제에서 마코브 행렬의 크기가 10000 x 10000인데 극한(infinite)에서의 결과값을 알고싶다고 하자. 실제 극한을 구할 수는 없으니 예를 들어 10,000,000 step이후의 상황을 예측한다고 가정해보자. 이 경우 직접 행렬을 곱해서 계산을 한다는 것은 매우 무식한 방법이다. 식 (13.3)과 같이 해를 계산한다면 단지 고유값의 거듭제곱만 계산하면 되기 때문에 훨씬 빠르고 효율적으로 답을 구할 수 있게 된다.
이제 위의 식을 이용하여 아이폰과 갤럭시폰의 한 해 동안의 시장점유율을 예측해보자. 아래 그림은 마코브 체인으로 모델링한 애플과 삼성의 핸드폰 시장점유율 예측 그래프이다.
Fig. 4 마코브 체인을 이용한 애플과 삼성의 휴대폰 시장점유율 예측 그래프
초기 점유율은 삼성이 더 높았지만, 마코브 체인을 통한 시뮬레이션 결과 급격하게 점유율이 역전하면서 약 4월달 정도에는 정상상태(steady state)로 수렴하는 모습을 보인다.
한 가지 알아둬야 할 것은 마코브 체인은 그 한계점이 극명하게 존재한다는 것이다. 위의 문제에선 매달 시장점유율을 예측함에 있어서 그 달의 점유율에 마코브 행렬을 곱하여 다음달의 점유율에 대한 예측을 하였다. 중요한 점은 그 과정에서 마코브 행렬 자체는 한 번도 변하지 않았다는 것이다. 위 문제에서 마코브 행렬은 유저들의 이동변화율을 기술하였다. 그러나 이 변화율은 실제 세계에서는 시시각각 변하고 또한 변수도 너무나도 많다. 따라서 좀 더 정교한 예측을 하기 위해서는 마코브 행렬의 값을 스텝을 거칠 때마다 업데이트를 해야할 것이다. 하지만 마코브 행렬의 지속적인 업데이트가 필요없는 분야, 예를 들면 전자회로에서의 응용 문제 등에는 비교적 잘 들어맞을 때가 많다.
이 외에도 마코브 체인의 단골 손님으로 나오는 문제인 날씨 예측, 인구이동 예측 문제 등이 있으니 직접 문제를 만들어 풀어보기 바란다. 문제 설정 및 풀이를 하는 과정은 애플-삼성 휴대폰 시장 점유율 예측 문제와 다르지않다. 아래는 소스코드이다.
4. 마치며
이번 강의에서는 마코브 체인과 마코브 행렬에 대해 공부하였다. 마코브 행렬은 기본적으로 확률을 기반으로 한 상태 전이 행렬이며, 어떤 상태의 변환 이후에도 상태의 총량은 유지된다는 특성이 있다. 예를 들면 인구이동 문제의 경우 이동에 따른 상태 값의 변화(인구수)는 있겠으나 그 총량은 유지된다. 이는 확률을 기반으로 하며, 각 column의(혹은 row) 합은 1이 된다는 마코브 행렬의 특성에서도 유추해 볼 수 있다. 그 특성의 결과로 항상 하나의 고유값은 1을 가진다는 특성도 공부하였다. 또한 계차방정식과 연결지어 행렬의 거듭제곱 문제를 고유값의 거듭제곱 문제로 바꾸어 보다 빠르고 효율적인 계산방법을 배웠다.
마지막으로 부가적인 설명을 하자면 애플과 삼성의 핸드폰 시장 점유율 예측에 대한 문제를 마코브 행렬로 모델링하고 이를 계산하는 과정에서 알아챈 분들이 있을지 모르겠으나, 이번 강의에서 설명한 마코브 체인은 1차 마코브 체인(first order Markov chain)이다. 이것이 의미하는 것은 상태 전이 과정에서 다른 시점에서의 상태와는 무관하고 오직 바로 이전상태에만 영향을 받는다는 것이다. 예측을 함에 있어 그 전전 상태까지 고려하는 2차 마코브 체인 등도 있지만 1차가 가장 보편적으로 사용된다. 또한 일반적으로 마코브 체인이라 하면 1차 마코브 체인을 의미한다.