마르코프 체인에서 주어진 시간 후 특정 상태에 도달할 확률을 구하는 C++ 프로그램

개요

이 글에서는 마르코프 체인(Markov Chain)에서 초기 상태에서 최종 상태까지 주어진 시간 안에 도달할 확률을 계산하는 C++ 프로그램을 살펴봅니다.

마르코프 체인은 여러 개의 상태(state)와 한 상태에서 다른 상태로 이동할 확률들로 구성된 무작위 프로세스입니다. 한 상태에서 다른 상태로 이동하는 데에는 단위 시간이 소요됩니다.

접근 방법

마르코프 체인은 유향 그래프(directed graph)로 표현할 수 있습니다. 문제를 해결하려면 주어진 마르코프 체인을 전이 행렬(transition matrix) 형태로 변환하면 됩니다. 이 행렬에서 위치 (a, b)의 원소는 상태 'a'에서 상태 'b'로 이동할 확률을 나타냅니다.

전이 행렬을 구한 뒤에는 다음 공식을 이용해 시간 t에서의 확률 분포를 재귀적으로 계산할 수 있습니다.

P(t) = Matrix * P(t-1)

이 공식을 반복 적용하면 P(t) = Matrix^t가 되므로, 결국 전이 행렬의 T제곱을 빠르게 계산하는 것이 핵심입니다. 여기서는 지수 분할 기법(이진 거듭제곱, binary exponentiation)을 활용하면 시간 복잡도를 O(N³ log T)로 줄일 수 있어 T가 매우 큰 경우에도 효율적으로 계산할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
#define float_vec vector<float>
// 두 행렬을 곱하는 함수
vector<float_vec > multiply(vector<float_vec > A, vector<float_vec > B, int N) {
   vector<float_vec > C(N, float_vec(N, 0));
   for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j)
         for (int k = 0; k < N; ++k)
            C[i][j] += A[i][k] * B[k][j];
   return C;
}
// 행렬의 거듭제곱을 계산하는 함수
vector<float_vec > matrix_power(vector<float_vec > M, int p, int n) {
   vector<float_vec > A(n, float_vec(n, 0));
   for (int i = 0; i < n; ++i)
      A[i][i] = 1;
   while (p) {
      if (p % 2)
         A = multiply(A, M, n);
      M = multiply(M, M, n);
      p /= 2;
   }
   return A;
}
// 초기 상태에서 최종 상태에 도달할 확률을 계산하는 함수
float calc_prob(vector<float_vec > M, int N, int F, int S, int T) {
   vector<float_vec > matrix_t = matrix_power(M, T, N);
   return matrix_t[F - 1][S - 1];
}
int main() {
   vector<float_vec > G{
      { 0, 0.08, 0, 0, 0, 0 },
      { 0.33, 0, 0, 0, 0, 0.62 },
      { 0, 0.06, 0, 0, 0, 0 },
      { 0.77, 0, 0.63, 0, 0, 0 },
      { 0, 0, 0, 0.65, 0, 0.38 },
      { 0, 0.85, 0.37, 0.35, 1.0, 0 }
   };
   // 상태의 개수
   int N = 6;
   int S = 4, F = 2, T = 100;
   cout << "Probability of reaching: " << F << " in time " << T << " after starting from: " << S << " is " << calc_prob(G, N, F, S, T);
   return 0;
}

코드 설명

multiply 함수: 두 개의 N×N 행렬을 곱하는 표준적인 행렬 곱셈을 수행합니다.
matrix_power 함수: 단위 행렬을 초기값으로 두고, 지수 p를 이진수로 분해하며 거듭제곱을 계산합니다. 이를 통해 O(log p)번의 행렬 곱셈만으로 M^p를 구할 수 있습니다.
calc_prob 함수: 전이 행렬의 T제곱을 구한 뒤, [F-1][S-1] 위치의 값을 반환하여 상태 S에서 출발해 T시간 후 상태 F에 도달할 확률을 얻습니다.

실행 결과

Probability of reaching: 2 in time 100 after starting from: 4 is 0.271464

위 결과는 상태 4에서 출발했을 때 100단위 시간이 지난 후 상태 2에 도달할 확률이 약 0.271464, 즉 약 27.15%임을 의미합니다.