수열을 통해 마코프 체인의 단서를 얻어보자 :)

제가 첨부 파일로 올린 수열은 마코프 체인으로부터 얻어졌습니다. 하지만, 이 수열이 마코프 성질을 가지고 있는지 여부를 미리 알 수 없었다고 가정했을 때, 이 수열이 마코프 성질을 가지고 있다는 (=마코프인지 아닌지) 단서를 얻을 수 있는 방법에 대해 설명해 보겠습니다.

 

먼저 주어진 수열이 마코프 성질을 가지고 있는지 아닌지를 판단하기 위해 마코프 성질에 대해 먼저 언급하려합니다. 마코프 성질의 정의는 이렇습니다.

 

이 말을 조금 더 쉽게 설명하기 위해 베르누이과정(Bernoulli Process)의 예를 들어보겠습니다. 베르누이과정은 독립적으로 수행되며, 오로지 두 결과 값만을 갖는 사건이 연속적으로 발생 하는 확률과정을 말합니다. 베르누이 실험이라는 것은 결과가 ‘랜덤’하게 둘 중 하나만 나오는 실험입니다. 주로 동전던지기의 예로 들어 설명을 하는데, 동전을 던지면 오직 앞 혹을 뒤라는 결과만 랜덤하게 나옵니다. 여기서 마코프 성질을 한 번 더 설명하자면 마르코프 성질이란 n+1회의 상태가 오로지 n회의 상태에만 영향을 받는 것을 의미합니다. 베르누이과정 즉, 결과가 랜덤하게 나오는 동전던지기는 분명 마코프 성질을 따르지 않는다는 것입니다. 현재 나온 결과가 다음에 나올 결과에 전혀 영향을 끼치지 않기 때문입니다.

 

다시 정리하자면, 마코프 체인은 현재 상태만 정확히 알고 있다면 과거가 미래에 영향을 미치지 못하는 확률 과정입니다. 이러한 성질을 무기억성(Memorylessness)이라고 합니다. 쉽게 이해하기 위해 오늘의 저의 기분을 예로 들어보겠습니다. 현재, 오늘의 기분은 과연 어제 혹은 조금 전과 무관한 기분일까요? 당연히 그렇지 않겠죠. 현재 저의 기분은 분명 조금 전 혹은 어제의 영향을 받았을 것입니다. 현재 저의 기분이 과거나 미래와 독립적이지 않다는 말이 될 것입니다. 하지만 독립적이지 않다는 말이 마코프 성질을 지녔다는 말이 되지는 않습니다. 독립적이지 않다는 것은 여러 요인들이 현재의 확률에 영향을 준다는 것인데, 마코프 성질은 직전상태만이 중요하기 때문입니다. 그리고 지금 저의 기분을 예로 든 것 또한 마코프 성질을 지녔다고 단정할 수는 없습니다. 왜냐하면 저의 기분이 어제 혹은 저번주, 어쩌면 미래의 영향을 받았을 수도 있기 때문이죠. 이처럼 마코프 성질을 정확하게 가진 사건은 현재에 존재하기 힘듭니다.

 

그렇다면 위의 설명을 토대로 주어진 수열이 마코프 성질을 가졌다는 근거에 대해 설명해 보겠습니다. 앞서 마코프 체인은 무기억성을 가졌다고 설명했습니다. 무기억성이란 아예 기억을 하지 못하는 것이 아닙니다. 현재의 상태가 어쩌면 과거, 더 과거의 영향을 받았을 수도 있지만, 바로 직전의 과거에 현재 상태가 결정되는 모든 정보가 있다는 것이죠. 그렇다면 주어진 수열을 분석해 보겠습니다. 주어진 수열은 길이가 1000이지만 원소가 1, 2, 3으로만 이루어진 수열입니다. 먼저 수열의 특성을 파악하기 위해서, 어떠한 반복, 특징들을 파악하기 위해 계속 관찰하였습니다. 그 결과 주어진 수열에서 1다음에 1이 나오는 구간은 한 구간도 존재하지 않는다는 것을 발견하였습니다. 이것을 근거로 마코프 체인으로 이루어진 수열이라는 것을 몰랐을 때에 완전하게 랜덤하게 나열된 수열이 아니라는 것을 유추할 수 있습니다. 정말 무질서하게 나열되었다면 1다음에 1이 한 번은 나와야 정상이겟죠. 그리고 살펴보면 2다음에 2가 유난히 많이 반복되는 것을 알 수 있습니다. 어떠한 규칙이 있겠다고 알 수 있었습니다. 알아낸 것들을 기반으로 주어진 수열이 마코프 성질을 가졌다는 것을 유추해 볼 수 있습니다. 정확히 분석해보지 않더라도 1다음에 1이 올 확률은 없으므로 ‘어떠한 형태로든 현재의 상태가 직전상태의 영향을 받는 다는 것’을 알 수 있습니다. 또한, 2가 유난히 많이 반복된다는 것은 2다음에 2가 나올 어떠한 확률이 높다는 것을 예상할 수 있습니다. 이렇게 예측을 해보면 1다음에 1,2,3이 나오는 확률이 존재할 것이라는 가정을 할 수 있습니다. 마찬가지로 2,3 다음에 나오는 수들에도 확률이 존재할 것이라고 생각할 수 있겠죠. 그렇게 예상해보면 어떤 원소가 나오고 알 수 없는 확률에 의해 다음 원소가 나온다면, 현재의 상태가 정해지는 데에 필요한 모든 정보가 바로 직전상태에 모두 있다고 표현을 해도 무방하다고 할 수 있습니다.

 

주어진 수열로부터 마코프 전이행렬을 구해보겠습니다.

 

마코프 전이행렬은 현재상태에서 다음상태로 갈 확률을 행렬로 표현한 것입니다. 즉, 각 상태들이 다른 상태로의 전이가 얼마의 확률로 이루어질 것인가를 기술한 것이죠. 이 정의에 따라 주어진 수열을 분석해보겠습니다. 주어진 수열은 길이가 1000이지만 원소는 3개를 가지고 있습니다. 그리고 마코프 성질을 지녔다는 것을 알 수 있으므로 1 -> 1,2,3 , 2 -> 1,2,3 , 3 -> 1,2,3 으로 총 9가지의 경우의 수가 나옵니다. 이것을 행렬로 표현하면 3X3 행렬이 됩니다.

 

파이썬을 이용하여 수열을 받아 각각의 경우의 수를 구해보았습니다. 그 결과는 이러합니다.

 

마코프 전이행렬의 원소는 현재에서 다음상태로 갈 확률이므로 길이가 1000인 수열에서 마코프 전이행렬을 구하면 999개의 원소가 나오게 됩니다. 그래서 각 경우의 수를 구한 값을 모두 더하면 999가 나오는 것입니다.

 

마코프 전이행렬은 두 가지 특징을 가집니다. 첫 번째 특징은 모든 원소의 값이 0보다 크거나 같다는 것입니다. 오직 양수만 허용된다는 것이죠. 이유는 기본적으로 전이 확률을 나타내기 위한 행렬이기 때문에 확률 값을 원소로 가집니다. 확률 값에는 음수가 있을 수 없기 때문에 원소 값들은 반드시 0보다 크거나 같아야만 합니다. 두 번째 특징은 각 행의 원소의 합이 1이 된다는 것입니다. 이것은 마코프 전이행렬을 거듭제곱해도 마찬가지입니다. 행의 모든 원소의 합이 1이 되는 이유는 하나의 행은 어떤 상태에 대한 모든 전이확률을 나타내기 때문입니다. 각각의 경우의 수와 마코프 전이행렬이 가져야하는 특징에 따라서 마코프 전이행렬(P)는 다음과 같습니다.

 

얻어진 마코프 전이행렬을 써서 상태전이도를 그려보고, 어느 상태에 가장 오래 머물러 있을지 적절한 근거를 가지고 예측해 보고, 실제 데이터와 일치하는지 확인하는 과정을 진행하겠습니다.

 

먼저 위에서 구한 마코프 전이행렬을 통해 상태전이도를 그려보면 다음과 같습니다.

 

 

먼저 상태전이도를 통해 각 원소의 상태(state)에 대해 언급해본다면, 모든 원소는 Accessible하다고 할 수 있습니다. 몇 번의 step을 거치면 어디든 갈 수 있기 때문이죠. 또한 서로 Accessible하기 때문에 Communicate하다고 말할 수 있습니다. 그리고 모든 성분이 communicate하기 때문에 irreducible하다 할 수 있습니다. 버릴 chain이 하나도 없다는 뜻입니다. 원소들을 분석해보면 원소 2가 recurrent할 확률이 가장 높을 것입니다. 즉, 가장 오래 머물러 있을 거라 예상할 수 있습니다.

 

조금 더 직관적으로 판단해 본다면, 모든 원소를 더했을 때 3이 되는 것을 확인해 볼 수 있습니다.(실제로 마코프 전이행렬의 행 원소의 모든 합은 1이고 3행이므로 3입니다.) 그렇다면 최종 1에 머물러 있을 확률을 모두 더하면 마코프 전이행렬의 1열의 원소를 모두 더한 값이 됩니다. 즉, 0.4166이고 이것은 3으로 나눠주면 0.1388이 됩니다. 마찬가지 방법으로 2에 머물러있을 확률은 0.5171이고, 3에 머물러 있을 확률은 0.3444가 됩니다. 이로써 2에 머물 확률이 가장 높을 것이라고 예상할 수 있습니다.

 

한 가지 더 확인해본다면, 마코프 전이행렬을 거듭제곱해볼 수 있습니다. 예를 들어 제곱을 한다면 은 1에서 중간에 어떤 것을 거쳐 다시 1로 올 확률이 됩니다. 이렇게 확인해 보기위해, 구했던 마코프 전이행렬을 제곱하면 마코프 전이행렬(P)는 아래와 같습니다.

 

 

제곱한 결과에서도 알 수 있듯이, 2에서 어떤 것을 거쳐 다시 2로 올 확률이 0.5749로 가장 높습니다. 거듭제곱을 해도 비슷한 결과가 나올 것입니다.

 

이렇게 하여 2에 머물러 있을 가능성이 가장 크다고 판단하였고 실제로 주어진 수열에서 확인한 결과 1의 개수는 136, 2의 개수는 625, 3의 개수는 239로 실제 데이터와 비교해봤을 때에도 마코프 전이행렬로 예상했던 것과 실제 데이터가 같았다는 것을 알 수 있습니다.