Stochastic Processes and Markov Chains

markov

확률 과정 (Stochastic Processes) 이란?

확률 과정은 시간의 흐름에 따라 변화하는 확률 변수들의 집합으로 정의됨. 즉, 시간에 따라 어떤 결과가 무작위로 나타나는 현상을 수학적으로 모델링한 것.

X = \{ X(t), t \in T \}

$t$ : 시간 (time)
$T$ : 시간의 집합. 이산적이거나(countable) 연속적일 수 있음(uncountable).
$X(t)$ : 특정 시간 $t$ 에서의 시스템의 상태(state)를 나타내는 확률 변수.

Definition (확률 과정 vs. 확률 변수)

확률 변수 (Random Variable): 단일 실험의 결과를 나타내는 변수. (예: 주사위 한 번 던지기)
확률 과정 (Stochastic Process): 시간의 흐름에 따른 일련의 확률 변수들의 집합. 즉, 시간 차원이 추가된 확률 변수로 볼 수 있음. (예: 매일 주사위를 던져 나오는 눈을 기록하는 과정)

이산 시간 마르코프 연쇄 (DTMCs)

이산 시간 마르코프 연쇄(Discrete-Time Markov Chains, DTMCs) 는 이산적인 시간(discrete time)을 갖는 확률 과정의 한 종류로, 다음 상태가 오직 현재 상태에 의해서만 결정되는 특징을 가짐.

DTMC의 기본 정의

DTMC는 다음 세 가지 요소로 구성됨:

이산적인 시간 집합 (Discrete Index Set): 시간 $n$ 이 0, 1, 2, 3, … 과 같이 정수로 표현됨.
셀 수 있는 상태 공간 (Countable State Space): 시스템이 가질 수 있는 모든 상태들의 집합 $S$ 가 유한하거나(finite) 셀 수 있는 무한(countably infinite) 집합임.
마르코프 특성 (Markov Property): “미래는 오직 현재에만 의존한다.” 시스템의 다음 상태( $n+1$ )는 과거의 모든 상태( $0, 1, ..., n-1$ )와는 무관하게, 오직 현재 상태( $n$ )에 의해서만 결정됨.

Note (마르코프 특성: Memorylessness)

마르코프 특성은 시스템이 ‘기억을 가지지 않는’ 속성으로 비유할 수 있음. 현재 상태에 도달하기까지 어떤 경로를 거쳐왔는지는 다음 상태를 결정하는 데 아무런 영향을 미치지 않음.

전이 확률 (Transition Probability)

마르코프 특성에 따라, 시스템이 현재 상태 $i$ 에서 다음 상태 $j$ 로 이동할 확률은 다음과 같이 단순하게 표현됨. 이를 전이 확률이라 함.

P(X_{n+1}=j | X_n=i)

이 전이 확률들을 모아 행렬 형태로 표현한 것을 **전이 확률 행렬(Transition Probability Matrix, P)**이라고 함.

채프먼-콜모고로프 방정식 (Chapman-Kolmogorov Equations)

이 방정식은 현재로부터 $m$ 단계 이후의 미래 상태 확률을 계산하는 방법을 제공함.

1단계 전이 확률: $p_{ij} = P(X_{n+1}=j | X_n=i)$
m단계 전이 확률: $p_{ij}^{(m)} = P(X_{n+m}=j | X_n=i)$

채프먼-콜모고로프 방정식은 (m+n)단계 후의 전이 확률은 중간 상태 $k$ 를 거쳐 가는 모든 경로의 확률을 더한 것과 같다고 설명함.

p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}

이는 행렬 곱셈으로 더 간단하게 표현할 수 있음. 즉, n단계 후의 전이 확률 행렬 $P^{(n)}$ 은 1단계 전이 확률 행렬 $P$ 를 n번 곱한 것과 같음.

P^{(n)} = P \cdot P \cdot ... \cdot P = P^n

정상 상태 (Steady-State Behavior)

시간이 무한히 흐르면( $m \to \infty$ ), 특정 조건 하에서 마르코프 연쇄는 초기 상태 $i$ 와 관계없이 특정 상태 $j$ 에 있을 확률이 일정한 값 $\pi_j$ 로 수렴함.

\lim_{m \to \infty} p_{ij}^{(m)} = \pi_j

이 $\pi_j$ 들의 집합을 정상 상태 분포(Steady-State Distribution) 또는 정적 분포(Stationary Distribution) 라고 하며, 이는 시스템의 장기적인 행동 패턴을 나타냄.

Example (DTMC의 응용: PageRank 알고리즘)

구글의 페이지랭크 알고리즘은 DTMC의 정상 상태 개념을 활용한 가장 유명한 사례. 웹 서퍼가 링크를 따라 무한히 웹 페이지를 이동하는 과정을 마르코프 연쇄로 모델링함. 각 웹 페이지의 장기적인 방문 확률(정상 상태 분포)이 바로 그 페이지의 중요도, 즉 페이지랭크 점수가 됨.

DTMC 예제: 날씨 예측 및 스마트폰 선호도

날씨 예측: 오늘의 날씨(비/맑음)가 내일의 날씨에만 영향을 미친다고 가정하고, 며칠 뒤의 날씨 확률을 전이 확률 행렬의 거듭제곱( $P^2, P^4, ...$ )으로 계산할 수 있음.
스마트폰 선호도: 사용자가 다음 스마트폰으로 특정 브랜드를 선택할 확률을 전이 확률로 모델링하여, 장기적으로 각 브랜드의 시장 점유율(정상 상태 분포)이 어떻게 될지를 예측할 수 있음.

1
# 날씨 예측
2
import numpy as np
3

4
# P[i, j] = i 상태에서 j 상태로 갈 확률
5
# 상태 0: 비/눈, 상태 1: 맑음
6
# P = [[P(0->0), P(0->1)],
7
#      [P(1->0), P(1->1)]]
8
P = np.array([[0.4, 0.6],
9
              [0.7, 0.3]])
10

11
# 2일 뒤의 날씨 전이 확률 행렬
12
P2 = np.matmul(P, P)
13

14
# P2[0, 0]: 오늘 비가 올 때 2일 뒤 비가 올 확률 (0.58)
15
# P2[1, 0]: 오늘 맑을 때 2일 뒤 비가 올 확률 (0.49)
16
print("2-step Transition Matrix (P^2):\n", P2)
17

18
# 전이 확률 행렬을 계속 곱하면 정상 상태로 수렴함
19
P4 = np.linalg.matrix_power(P, 4)
20
P8 = np.linalg.matrix_power(P, 8)
21
P16 = np.linalg.matrix_power(P, 16)
22
P32 = np.linalg.matrix_power(P, 32)
23

24
print("\n16-step Transition Matrix (P^16):\n", P16)
25
print("\n32-step Transition Matrix (P^32):\n", P32)

마르코프 결정 과정 (MDP)

마르코프 결정 과정(Markov Decision Process, MDP) 은 마르코프 연쇄에 행동(Action) 과 보상(Reward) 의 개념을 추가하여 확장한 모델. 의사결정자가 각 상태에서 어떤 행동을 취해야 장기적인 보상을 최적화할 수 있는지 문제를 다룸.

핵심 구성 요소:
- $X_n$ : 시간 $n$ 에서의 상태
- $A_n$ : 시간 $n$ 에서의 행동
- $p_{ij}(a)$ : 상태 $i$ 에서 행동 $a$ 를 했을 때 상태 $j$ 로 전이될 확률
- $R_{ij}(a)$ : 상태 $i$ 에서 행동 $a$ 를 하여 상태 $j$ 로 갔을 때 받는 보상

MDP - 유한 단계 (Finite Stage)

정해진 끝(N)이 있는 문제에서, 현재 상태에서 미래의 총 기대 보상을 최대화하는 최적의 행동을 찾는 것을 목표로 함.

이는 최적성의 원리(Principle of Optimality) 와 동적 계획법(Dynamic Programming)을 사용하여 해결함. 마지막 단계(N)부터 거꾸로 계산하여 각 시점, 각 상태에서의 최적 행동과 그때의 기대 보상을 찾아 나감.

Definition (벨만 방정식 (Bellman Equation))

유한 단계 MDP는 벨만 방정식을 통해 최적의 가치 함수 $f_n(i)$ 를 재귀적으로 계산함. $f_n(i)$ 는 시간 $n$ , 상태 $i$ 에서의 최대 미래 기대 보상을 의미함.

f_n(i) = \max_{a} \sum_{j=0}^{\infty} p_{ij}(a)[R_{ij}(a) + f_{n+1}(j)]

이 방정식을 마지막 단계부터 거꾸로( $f_{N-1}, f_{N-2}, ...$ ) 풀어 최적 정책을 찾음.

MDP - 무한 단계 (Infinite Stage)

끝이 없는 문제에서는 시간이 지나도 변하지 않는 최적의 정책, 즉 정상 정책(Stationary Policy) 을 찾는 것이 목표. 이 정책은 오직 현재 상태에만 의존하여 최적의 행동을 결정함.

정상 정책을 찾는 방법:
- 정책 반복 (Policy Iteration)
- 가치 반복 (Value Iteration)
- 선형 계획법 (Linear Programming)

MDP 예제: 입찰 최적화

광고 성과를 ‘좋음’, ‘평균’, ‘나쁨’의 3가지 상태로, 입찰 전략을 ‘보수적’, ‘공격적’의 2가지 행동으로 정의. 각 행동에 따른 상태 전이 확률 행렬과 보상 행렬이 주어졌을 때, 향후 3개월간의 총 보상을 최대화하는 최적의 행동 순서를 벨만 방정식을 통해 역산하여 찾을 수 있음.