Markov Process #2. 상태의 분류

마르코프 연쇄는 어떤 시간에 상태 i에 있는 과정이 다른 시간에 상태 j에 있을 확률을 마르코프 성질을 통해 쉽게 파악할 수 있게 해준다. 하나의 상태에서 다른 상태로인동이 가능한지, 이동할 수 있다면, 어떤 특성이 있는지에 따라 마르코프 연쇄의 상태를 분류할 수 있고, 이것은 체계적으로 마르코프 연쇄를 파악하는데 도움을 준다. 여기서는 상태들의 분류와 특성을 알아보자.

* 마르코프 연쇄에서의 특성들

도달 가능(Accessible)

i에서 j로 도달 가능하다는(accessible) 것은, 직접 또는 (다른 상태들을 거쳐서) 상태 i에서 출발한 마르코프 연쇄가 언젠가는 상태 j로 들어갈 수 있다는 뜻이며, 도달할 수 없다는 것은, i에서 출발한 마르코프 연쇄가 영원히 j에 들어가지 못함을 뜻한다. (P=0). 도달 가능성은 i->j로 표기하고, "상태 j는 상태 i로부터 도달 가능하다"고 한다.

교통(Communicate)

두 상태 i와 j가 서로에게 갈 수 있을 때(i->j, j->i), "i와 j가 서로 교통한다"고 하며, i↔j라고 표기한다. 모든 상태는 자기 자신과 교통한다(P=1). 교통하지 않는 경우로 i->j, i<-j (단방향)의 경우와 i와 j가 서로 도달가능하지 않을 경우의 3가지 경우가 있다. 이에 대한 증명은 챕맨-콜모고르프 등식을 통해 가능하다.

집단(Class)

서로 연락하는 두 상태는 같은 집단에 들어 있다고 한다.

교통집단(communicating class)

서로 교통하는 상태들의 집합을 교통집단이라고 한다. 하나의 마르코프체인안에 여러개의 교통집단이 있을 수 있다.

흡수상태(absorbing state), 흡수집단(absorbing group)

한번 들어가면 다시는 빠져나올 수 없는 상태나 집단을 말한다. 일단 흡수상태에 빠지면 마르코프체인이 그 안에서 무한정 전이(점프)한다고 볼 수 있다.

가약(Reducible) / 기약(Irreducible)

흡수상태나 흡수집단을 갖는 마르코프연쇄을 가약마르코프연쇄(reducible markov chain)또는 흡수 마르코프연쇄(absorbing markov chain)이라고 부른다. 더 줄일 수 있는 마르코프 연쇄라는 의미이다. 

흡수상태나 흡수집단이 없는, 하나의 집단으로만 구성되어 있는 마르코프 연쇄를 기약 마르코프 연쇄(irreducible markov chain)라 한다. 더 줄일 수 없는 마르코프연쇄라는 의미이다. 기약마르코프체인의 모든 모든 상태는 서로 교통할 수 있다. 즉, 기약마르코프연쇄는 하나의 교통집단으로 이루어진다. 마르코프연쇄는 기약이든지 가약이든지 둘 중 하나이다.

주기적(Period) / 비주기적(Aperiodic)

상태 i의 주기 d(i)는, 상태 i에서 출발하여, 다시 상태 i로 돌아올 때까지의 주기를 말하며, Pii^n>0을 만족시키는 모든 n>=1의 최대공약수로 정의한다. 예를 들어 i에서 시작하여 6,12,18...의 전이 후에 i에 다시 돌아온다면, 상태 i의 주기는 d(i)=6이다. 4,8,10,12,...의 전이 후에 다시 i에 있을 수 있다면 주기는 d(i)=2일 것이다. 교통하는 상태들의 주기는 집단성격을 띈다. 따라서 기약마르코프연쇄에서 한 상태의 주기가 d이면 모든 상태의 주기가 d이다. 이런 경우 "마르코프연쇄의 주기가 d이다" 라고 말한다. 반면 마르코프연쇄가 주기적이지 않으면 비주기적이라고 부른다. 비주기적이라는 것은 주기가 1(d=1)이라는 것을 의미한다. 

* 상태의 구분

재귀상태(recurrent state)

상태 i를 떠나서 유한시간만에 다시 i로 돌아올 확률을 fi라고 하자. fi=1이면 i를 재귀상태라고 부른다. i<->j이고 i가 재귀상태이면 j도 재귀상태이다. (이와 같이, 교통하는 상태들이 집단적으로 지니는 동일한 성질을 집단성격(class property)이라고 부른다).

상태 i에 들어간 직후부터 다음에 다시 i로 들어갈때까지 걸리는 시간(전이 횟수)을 재귀간격(recurrence interval, recurrence time)이라고 부른다.(이에는 자신에게 돌아와 한번만에 i로 다시 오는 경우도 포함한다). 

재귀 상태는 평균재귀간격의 유한 또는 무한 여부에 따라 둘로 나뉜다. 평균재귀간격이 유한하면 양재귀(positive recurrent), 무한하면 귀무재귀(null-recurrent, recurrent-nonnull)라고 부른다. fi=1임에도 불구하고(즉, i를 떠나 언젠가는 확률 1로 유한시간만에 i로 돌아오더라도) 평균 재귀간격은 무한일 수 있다.

'상태 i가 재귀상태'이면 언젠가는 유한시간만에 반드시 상태 i로 다시 돌아오게되고, 일단 돌아오면 마르코프연쇄가 다시 시작하는 것과 같으므로, 상태 i로 진입하는 모든 시점들은 재생점이 된다. 이러한 마르코프연쇄가 무한시간동안 진행된다면 결국은 '상태 i를 무한 번 방문'하게 된다.

마르코프연쇄가 기약이고 상태의 수가 유한하다면 모든 상태들이 양재귀하다. 일단 흡수상태에 들어가면 영원히 그곳에서만 전이한다 볼 수 있으므로, 흡수상태는 재귀상태의 특별한 경우라고 볼 수 있다,

일시상태(transient state)

상태 i를 떠나서 다시 i로 돌아오지 못할 확률이 조금이라도 존재한다면, 즉, fi<1이면, 상태 i를 일시상태라고 부른다. 이 경우, 처음 유한번은 다시 i로 돌아올 수도 있겠지만, 언젠가는 영원히 못돌아오는 경우가 발생하게 된다. 이 경우 i에서 시작해서 u를 다시 방문하는 횟수는 유한한데 방문횟수가 n일 확률은 (fi)^(n-1)*(1-fi)로서 기하분포를 따른다. 상태의 수가 유한한 마르코프연쇄에서 모든 상태가 일시상태일수는 없다. 일시상태는 집단성격을 갖는다. 즉, i가 일시상태이고 i<->j이면 j도 일시상태이다. 마르코프연쇄의 모든 상태는 재귀상태 또는 일시상태 둘 중 하나이다. (흡수상태는 재귀상태의 특수경우로 본다)

에르고딕(ergodic)

마르코프연쇄가 다음 조건들을 모두 만족하면 에르고딕하다고 한다

1. 기약(irreducible), 2. 양재귀(positive recurrent), 3. 비주기적(aperiodic)

상태 3에서는 어떤 상태에도 갈 수 없으며, 이런 상태를 흡수상태(absorbing state)라 부른다.

여기에서 주기는 1이다. 주기가 1인 이유를 개념적으로 생각해보면, 상태 0에서는 상태 1로 가고, 상태 1에서는 상태 2로 가는데, 상태 2에서는 상태 0과 3으로 가고, 상태 3에서는 상태 0으로 가거나 상태 3에 머무른다. 일단 상태 3에 가면, 얼마든지 상태 3에 머무를 수 있고, 따라서 상태 0으로 돌아오는 것은 언제나 가능하다. 이 때, N=3이라 하면, n >=N인 모든 정수에서 P00이 성립함을 알 수 있다. 이처럼 충분히 큰 주기의 정수배에서는 항상 자기 자신으로 돌아올 수 있다. 여기서 충분히 큰 값을 쓰는 이유는, 앞의 얼마 동안은(비록 주기라고 해도)자기 자신으로 돌아오지 못할 수 있는데, 위에서 그것을 확인할 수 있다. 이는 마르코프 연쇄에서 주기의 정의가 그렇게 되어있기 때문이다. 따라서 마르코프 연쇄의 주기는 '충분히 큰 값'에서 일반적인 주기의 개념과 같아진다.

마지막으로 주기가 1일때를 생각해보면, 이 상태는(충분히 시간이 지난 후에는) 늘 돌아올 수 있기에 주기적이 아니라고 한다(일정한 시간 간격으로 일어나는것을 주기적이라 할때, 이것의 반대 개념이다. 곧, 주기를 찾을 수 없는, 비주기를 뜻하는 것이아니라, 항상 일어나므로 주기적이 아니라고 표현하는 것이다)일반적으로 다루는 마르코프 연쇄는 주기적이 아닌것이 많다.