Markov Chains마르코프 체인

P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)

현재 상태 X_t만 알면 과거는 불필요

import numpy as np

# 날씨 마르코프 체인
# 상태: 0=맑음, 1=흐림, 2=비
transition_matrix = np.array([
    [0.7, 0.2, 0.1],  # 맑음 → [맑음, 흐림, 비]
    [0.3, 0.4, 0.3],  # 흐림 → [맑음, 흐림, 비]
    [0.2, 0.3, 0.5],  # 비   → [맑음, 흐림, 비]
])

def simulate_weather(initial_state: int, n_steps: int) -> list:
    states = [initial_state]
    current = initial_state
    for _ in range(n_steps):
        current = np.random.choice(3, p=transition_matrix[current])
        states.append(current)
    return states

# 시뮬레이션
weather = simulate_weather(0, 100)
print(f"처음 10일: {['맑음','흐림','비'][s] for s in weather[:10]}")

# 정상 분포 계산 (전이 행렬의 고유값)
eigenvalues, eigenvectors = np.linalg.eig(transition_matrix.T)
stationary_idx = np.argmax(np.abs(eigenvalues - 1) < 1e-10)
stationary = eigenvectors[:, stationary_idx].real
stationary /= stationary.sum()
print(f"정상 분포: 맑음={stationary[0]:.3f}, 흐림={stationary[1]:.3f}, 비={stationary[2]:.3f}")

# 검증: T^n이 수렴하는지 확인
T_n = np.linalg.matrix_power(transition_matrix, 100)
print(f"T^100 행: {T_n[0]}")  # 정상 분포와 동일해야 함

def pagerank(adjacency_matrix, damping=0.85, n_iter=100):
    """PageRank = 마르코프 체인의 정상 분포"""
    n = len(adjacency_matrix)

    # 확률 전이 행렬 생성
    col_sums = adjacency_matrix.sum(axis=0)
    col_sums[col_sums == 0] = 1  # dangling node 처리
    T = adjacency_matrix / col_sums

    # 댐핑 팩터 적용
    T = damping * T + (1 - damping) / n * np.ones((n, n))

    # 멱 반복법 (Power Iteration)
    rank = np.ones(n) / n
    for _ in range(n_iter):
        rank = T @ rank
    return rank

# 예시 그래프 (A→B, A→C, B→C, C→A)
adj = np.array([[0,0,1],[1,0,0],[1,1,0]], dtype=float)
ranks = pagerank(adj)
print(f"PageRank: A={ranks[0]:.3f}, B={ranks[1]:.3f}, C={ranks[2]:.3f}")