[선형대수] 마코프체인(Markov chain)

마코프체인(Markov chain)

마코프체인은 과거의 상태와 현재 상태가 주어질 때, 미래 상태의 조건부 분포는 과거 상태에는 독립이고 오직 현재 상태에만 종속한다.

예를 들어보자,

1. 날씨 예측

 내일 비가 올 가능성은 오직 오늘 비가 오는지 안 오는지에만 종속하고 과거의 날씨에는 종속하지 않는다고 가정한다. 또한, 오늘 비가 올 때 내일 비가 올 확률은 a이고 오늘 비가 오지 않을 때 내일 비가 올 확률은 b라고 가정하자.

비가 올 때는 상태를 0이라고 하고 비가 오지 않을 때는 상태를 1이라고 하면, 이 과정은 다음의 전이확률을 갖는 2-상태 마코프체인이 된다.

2. 확률 과정을 마코프체인으로 변환하기

오늘 비가 올지의 여부가 과거 날씨 중 최근 이틀의 날씨에만 영향을 받는다고 가정하자. 

1. 지난 이틀 동안 비가 왔으면 내일도 비가 올 확률은 0.7이다.

2. 어제는 비가 오지 않고 오늘 비가 왔다면 내일 비가 올 확률은 0.5이다.

3. 어제는 비가 왔지만 오늘은 오지 않았다면 내일 비가 올 확률은 0.4이다.

4. 지난 이틀 간 비가 오지 않았다면 내일 비가 올 확률은 0.2이다. 

상태 0 : 오늘과 어제 모두 비가 옴

상태 1 : 오늘 비가 오고 어제는 안 옴

상태 2 : 어제 비가 오고 오늘은 안 옴

상태 3 : 어제와 오늘 모두 비가 안 옴

위 상태는 다음과 같은 전이확률 행렬을 갖는 4-상태 마코프체인을 나타낼 것이다.

3. 랜덤보행 모형

상태공간이 정수로 주어진 마코프체인이 어떤 상수 0<p<1에 대해 다음 관계를 만족하면 랜덤보행(random walk)라고 말한다.

이 마코프체인이 랜덤보행이라고 불리는 이유는, 직선 위를 걷고 있는 사람이 각 시점마다 확률 p로 오른쪽으로 한걸음 가든 1-p의 확률로 왼쪽으로 한걸음 가는 것에 대한 모형으로 볼 수 있기 때문이다. (무한도전에서 위에서 공 떨어뜨리면 중간에 막대에 맞고 아래로 내려가는 복불복 게임이랑 비슷한 것 같다. 사진은 못 찾음 ㅎㅎ)

4. 인구이동 모델

2007년에 미국의 도시에 살고 있는 사람의 수는 8천2백만이고 주변 교외에 살고 있는 사람의 수는 1억6천3백만으로 추정된다. 이 정보를 행렬 로 나타내자. 

2007년 인구 흐름은 도시에 그대로 머물 확률은 0.96이었고 교외로 이사 갈 확률은 0.04였다. 거꾸로 교외에서 도시로 이주할 확률은 0.01이었고 교외에 남아 있을 확률은 0.99였다. 이 확률을 원소로 하여 확률행렬 P를 다음과 같이 쓸 수 있다.

       도시 교외(에서)  (로)

   

2008년도의 인구는 행렬 곱으로 얻을 수 있다.

행렬 P로 표현된 인구흐름이 매년 변하지 않는다고 가정하면, n년 후의 인구 분포는,

로 나타낼 수 있다. 즉, 

 이고 은 n-단계 전이행렬로 불린다.

사실 인구 인구이동의 확률행렬 P는 매년 같다고 하기 어려운 점이 있다. 그래서 인구 이동 보다는 유전 법칙이 마코프체인을 적용하기에 적절하다고 생각한다.