(Bayes 학습)(8) 마르코프 연쇄-(3)

이전에 올린 마르코프 연쇄에 관한 글에서 ‘정칙 마르코프 연쇄(regular Markov chains)’에 대해 언급했다. 널리 사용되는 마르코프 연쇄 유형에는 세 가지가 있다. 그 중 하나가 정칙 마르코프 연쇄이고, 다른 두 가지는 ‘에르고딕(ergodic) 마르코프 연쇄’‘흡수(absorbing) 마르코프 연쇄’이다.

알기 쉽게 설명하면, 시간의 흐름에 따라 어떤 객체(물체, 사람, 정신, 기체, 동물, 국가, 기업 등)가 한 상태(state)에서 다른 상태(state)로 이전할 때, 새로운 상태가 바로 직전의 상태에만 의존하면, 우리는 그러한 현상이 마르코프 연쇄의 모형을 따른다고 규정할 수 있다.

그런데 마르코프 연쇄 방식의 상태 이전(state transition)에 대해 흥미 있는 두 가지 가능성을 상상해 볼 수 있다. 하나는 가능한 모든 상태들의 공간(즉, 상태 공간, state space)에서 어느 상태로부터 다른 모든 상태로의 이전이 가능한(단 한 번의 이전에 그렇게 되지는 않더라도) 경우가 있을 것이고, 다른 하나는 일단 어느 상태에 들어가면 그 상태에서 다시는 빠져나오지 못하는 경우가 있을 것이다. 전자가 에르고딕 마르코프 연쇄(ergodic Markov chains)이고, 후자가 흡수 마르코프 연쇄(absorbing Markov chains)이다.

이전 글에서 소개한 정칙 마르코프 연쇄는 에르고딕 마르코프 연쇄의 부분집합이다. 추이행렬(transition matrix)의 거듭제곱이 오직 양의 원소들(positive elements)만 가질 때 그러한 마르코프 연쇄를 정칙 마르코프 연쇄라고 부른다.

상태의 수가 유한할(finite) 때, 다음 두 가지 조건을 충족하면 마르코프 연쇄는 에르고딕(ergodic)하다.

  1. 마르코프 연쇄가 기약적(irreducible)이어야 한다. 마르코프 연쇄가 기약적이려면 상태 공간에 흡수 상태(absorbing state)가 없어야 한다. 흡수 상태란 그 상태에 들어가면 빠져나올 수 없는 상태를 말한다. 흡수 상태가 없으면 더 이상 줄일 수 없다(irreducible)고 표현한다. 한 상태에서 어떤 다른 상태로 언젠가 갈 수 있으며, 그 경우 그 상태들이 하나의 집단을 이루고 있는 것으로 간주될 수 있기 때문이다.  기약적(irreducible) 마르코프 연쇄는 수학 기호를 사용하여 다음과 같이 표현할 수 있을 것이다.

즉, 모든  쌍(pair)에 대하여 마르코프 연쇄가, 초기상태(에서 궁극적으로() 어떤 상태(에 도달할 확률이 양이 되는 경우 이를 기약적(irreducible)이라고 말한다. 상태 공간에 흡수 상태가 하나라도 있으면 당연히 기약적이 될 수 없을 것이다.

  1. 기약적인 마르코프 연쇄(irreducible Markov chain)가 비주기적(aperiodic)이어야 한다. 어느 상태에서 일정한 주기(period)로 그 상태로 돌아가면 주기적(periodic)이라고 부르고, 같은 상태로 돌아오는 모든 시간(주기)들의 최대공약수(gcd)가 1뿐이면 공약수가 없으니 비주기적(aperiodic)이라고 부른다. 이를 아래와 같이 수학적으로 표현할 수 있을 것이다.

즉, 만약 모든 에 대하여, 초기 상태가 일 때 다시 에 도달할 확률이 양수이고, 거기에 해당되는 모든 시간의 최대공약수(gcd)가 1이면(즉, 그 시간들의 배열이 1의 배수, 2의 배수, 3의 배수….중 1의 배수에만 모두 포함되면) , 마르코프 연쇄가 비주기적(aperiodic)이라고 한다.

에르고딕 (마르코프 연쇄) 정리(Ergodic Markov Chains Theorem)는 다음과 같다. 에르고딕 마르코프 연쇄에 대해서 가 성립하는 유일한 확률 벡터 가 존재하며, 는 엄격하게 양수이다(정칙 마르코프 연쇄에서 보았던 정상상태의 공식이다). 를 충족하는 어떤 행 벡터(row vector)도 의 배수이다. 를 충족하는 어느 열 벡터(column vector) 도 상수 벡터(constant vector)이다.

에르고딕성(ergodicity)은 여러 학문 분야에서 분석적 잠재력이 크게 평가되고 있다. 년 전에는 일군의 통계물리학자들이 이 개념을 원용해서 우리나라에서 주요 성씨들의 분포를 에르고딕 분포와 비에르고딕 분포로 분류하기도 했다. 그들은 김해 김씨처럼 전국에 퍼져 있는 성씨는 에르고딕 분포라고 분류하였으며, 학성(울산) 김씨처럼 특정 지역에 집중되어 있는 성씨는 비에르고딕 분포로 분류하였다(참고: Matchmaker, Matchmaker, Make Me a Match, 2014)

흡수 마르코프 연쇄도 에르고딕 마르코프 연쇄 못지 않게 널리 응용된다. 한번 들어가면 빠져 나오지 못하는 상태를 흡수 상태(absorbing state)라고 하며, 마르코프 연쇄가 하나 이상의 흡수 상태를 포함하고, 유한한 수의 단계를 거쳐 비흡수 상태에서 흡수상태로 갈 수 있으면 흡수 마르코프 연쇄(absorbing Markov chains)이다. 마르코프 연쇄의 흡수 상태를 행렬로 표현하면, 그 상태에 대응하는 행이 주대각선(main diagonal)의 값이 1이고, 다른 모든 값이 0이다.

그런데 흡수상태(absorbing state)와 정상상태(stationary state)를 혼동하지 않아야 할 것이다. 흡수상태란 빠져나올 수 없는 상태를 말하는 것이지, 정상상태처럼 추이행렬의 거듭제곱이 극한 행렬(limiting matrix)에 근사함(approach)을 함축하지는 않는다.

그렇다고 흡수 마르코프 연쇄에 극한 행렬이 없는 것은 아니다. 만약 가 흡수 마르코프 연쇄의 추이행렬이고, 가 표준적인 형식을 갖추고 있다면(in standard form), 다음과 같은 조건을 만족하는 극한 행렬  가 존재한다. 수식으로 표현하면,

흡수 마르코프 연쇄의 추이행렬은 다음과 같은 표준형(standard form)으로 표시된다.

standard_form

Abs.는 흡수 상태, NA는 비흡수 상태를 나타낸다. 모든 흡수 상태를 모든 비흡수 상태들보다 앞에 위치시킨다. 행렬을 4분하면, 좌상의 제1사분면이 단위행렬(Identity Matrix)이고 우상의 제2사분면은 모두 0으로 채워지며, 좌하의 제3사분면의 sub-matrix를 R, 우하의 제4사분면의 sub-matrix를 Q로 표시한다.  예컨대,

여기서 좌상의 제1사분면은 단위행렬 이며, 제2사분면은 에서 보듯이 모두 0으로 채워지고, 제3사분면의 은 R, 제4사분면의 은 Q이다.

이 R과 Q가 중요하다. 그것들로부터 극한행렬 을 구할 수 있다. 위에서 보듯이

standard_form

이다. 위의 사례를 가지고 극한행렬을 계산해 보면, 다음과 같이 나올 것이다.

공식을 적용하지 않고도 표준형의 추이행렬

를 거듭제곱해가면, 아마도  혹은  정도에서는 동일한 극한행렬을 얻을 것이다.

1986년 사회연결망 이론가인 John Skvoretz는 Thomas Fararo와 함께 사회연결망에서 지배 위계(dominance hierarchies)의 형성을 모델링했다. (1986년 나는 University of South Carolina 대학원 사회학과에서 Skvoretz 교수로부터 사회이론 수업을 들었다. 그는 저명한 수리사회학자였다.) 그들의 주장은 다음과 같다.

i가 k를 공격했는데, j가 옆에서 그것을 목격했다. 처음에는 세 사람 사이에 지배 관계가 없었다. i가 k를 지배할 확률이 이고, i가 j를 지배할 확률이 이며, j가 k를 지배할 확률도 라면, 장기적으로 세 사람 사이에는 지배적인 관계가 되던지, 아니면 상호 견제하는 관계라는 두 가지의 흡수 상태에 도달하게 될 것이다. 그리고 각각의 흡수 상태에 도달할 확률은 와 에 달려 있다. (자세한 내용은 Fararo, T.J. and J. Skvoretz. 1986. “E-State Structuralism: A Theoretical Method.” American Sociological Review 51: 591-602을 참조).

이제 베이즈 추론에 사용되는 MCMC (Markov Chain Monte Carlo) 시뮬레이션을 이해하는데 필요한 마르코프 연쇄에 관한 기초 지식을 충분히 얻었다고 판단된다. 다음에는 몬테 카를로 방법(Monte Carlo Methods)에 관해 알아봐야겠다.

<참고 문헌>

Grinstead, Charles M. & J. Laurie Snell. 1997. Introduction to Probability, 2nd revised ed. American Mathematical Society. Chapter 11. (마르코프 연쇄에 관해 체계적인 이해를 도와주는 아주 좋은 문헌임. 책 전체가 pdf 파일로 공개되어 있음)

Fararo, T.J. and J. Skvoretz. 1986. “E-State Structuralism: A Theoretical Method.” American Sociological Review 51: 591-602

마르코프 연쇄에 관해 두 사람의 유튜브 강의가 아주 유용했다.

PatrickJMT   Markov Cahins (Part 1~9)

Brandon Foltz의 Finite Math의 마르코프 연쇄에 관한 강의 여러 편. 

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.