Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

마르코프 체인(Markov Chain)에서 주어진 시간 T에 특정 상태에 도달할 확률 구하기 – Python 구현

마르코프 체인이란?

마르코프 체인(Markov Chain)은 여러 개의 상태(state)와 한 상태에서 다른 상태로 이동할 확률로 구성된 무작위 확률 과정(random process)입니다. 이는 방향 그래프(directed graph)로 나타낼 수 있으며, 이때 노드(node)는 각각의 상태를 의미하고, 에지(edge)에는 한 노드에서 다른 노드로 이동할 확률이 저장됩니다.

마르코프 체인의 핵심 성질은 다음과 같습니다.

  • 한 상태에서 다른 상태로 이동하는 데 걸리는 시간은 항상 단위 시간(unit time)입니다.
  • 모든 노드에서 나가는 에지(outgoing edge)들의 확률 합은 반드시 1이 됩니다.

문제 정의

마르코프 체인 그래프 g가 주어졌을 때, 시간 t = 0에서 상태 S에서 출발하여 시간 T에 상태 F에 도달할 확률을 구하는 것이 목표입니다.

예를 들어 입력이 N = 6(상태의 개수), S = 4(시작 상태), F = 2(목표 상태), T = 100(목표 시간)이라면, 출력은 다음과 같습니다.

0.28499144801478526

풀이 접근법: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • table[j][i] = 시간 i에 상태 j에 있을 확률을 저장하는 2차원 테이블을 사용합니다.
  • 초기 조건으로 시작 상태 S의 시간 0 확률을 1.0으로 설정합니다.
  • 이후 매 시간 단계마다 직전 시간(i-1)의 확률 값에 이동 확률을 곱해 누적하며 현재 시간의 확률을 계산합니다.

알고리즘 단계

  1. (N+1) × (T+1) 크기의 행렬 table을 생성하고 모든 값을 0.0으로 초기화합니다.
  2. table[S][0] := 1.0으로 설정합니다. (시작 상태의 초기 확률)
  3. i를 1부터 T까지 반복하면서:
    • j를 1부터 N까지 반복하면서:
    • 그래프 G[j]에 연결된 각 노드 k에 대해:
    • table[j][i] += k[1] * table[k[0]][i-1]을 누적합니다.
  4. 최종적으로 table[F][T]를 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.

def get_probability(G, N, F, S, T):
    table = [[0.0 for j in range(T+1)] for i in range(N+1)]
    table[S][0] = 1.0
    for i in range(1, T+1):
        for j in range(1, N +1):
            for k in G[j]:
                table[j][i] += k[1] * table[k[0]][i - 1]
    return table[F][T]

graph = []
graph.append([])
graph.append([(2, 0.09)])
graph.append([(1, 0.23),(6, 0.62)])
graph.append([(2, 0.06)])
graph.append([(1, 0.77),(3, 0.63)])
graph.append([(4, 0.65),(6, 0.38)])
graph.append([(2, 0.85),(3, 0.37), (4, 0.35), (5, 1.0)])

N = 6
S, F, T = 4, 2, 100
print(get_probability(graph, N, F, S, T))

입력

6, 4, 2, 100

출력

0.28499144801478526

코드 설명

그래프는 인접 리스트 형태로 표현되며, 각 요소는 (도착 노드, 이동 확률) 튜플로 구성됩니다. 예를 들어 graph[4]의 값 [(1, 0.77), (3, 0.63)]은 상태 4에서 상태 1로 이동할 확률이 0.77, 상태 3으로 이동할 확률이 0.63임을 의미합니다.

함수 내부에서는 먼저 확률 테이블을 초기화한 뒤, 시작 상태 S의 시점 0 확률을 1.0으로 설정합니다. 이후 시간 단계별로 모든 상태에 대해 이전 시간의 확률 값과 전이 확률을 곱해 누적함으로써 최종적으로 시간 T에 상태 F에 존재할 확률을 얻게 됩니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(T × N × E)입니다. 여기서 T는 목표 시간, N은 상태의 개수, E는 평균적으로 각 노드에 연결된 에지의 개수입니다. T가 클 경우에도 반복적인 경로 탐색 없이 선형적인 테이블 갱신만으로 답을 구할 수 있어 효율적입니다.