Markov Chain

Markov chain이란

Markov chain은 상태 간을 고정된 전이 확률로 이동하는 시스템을 모델링합니다. 다음 상태는 오직 현재 상태에만 의존합니다(무기억 성질). 이 모델은 신뢰성 모델링, 대기열 이론, PageRank, 도박사의 파산 문제, 날씨 예측 등에 활용됩니다. 각 상태에서 나가는 전이 확률의 합은 반드시 1이어야 합니다(행-확률론적 행렬).

Schematex의 강점은 엔진이 단순히 원과 화살표를 그리는 것이 아니라 선형 대수 계산을 직접 수행한다는 점입니다. 행-확률론적 행렬을 검증하고, SCC 분석을 통해 상태를 분류(일시적/재귀적/흡수적)하며, 정상 분포 π 또는 흡수 체인의 경우 흡수 확률과 기대 단계 수를 계산합니다. 모두 의존성 없이 직접 구현되어 있습니다.

1. 첫 번째 chain 만들기

markov 키워드(별칭 markovchain)로 시작하고, 선택적으로 제목을 입력한 후 확률 가중치가 있는 전이를 작성합니다. 상태는 처음 언급된 호로부터 자동으로 생성됩니다.

markov "Weather"
  Sunny -> Sunny : 0.9
  Sunny -> Rainy : 0.1
  Rainy -> Sunny : 0.5
  Rainy -> Rainy : 0.5

전이 형식은 FROM -> TO : PROBABILITY입니다. 자기 루프(Sunny -> Sunny)는 현재 상태에 머무를 확률입니다. 모든 확률은 [0, 1] 범위 내에 있어야 하며, 각 상태에서 나가는 확률의 합은 반드시 1이어야 합니다.

2. 상태 선언

레이블, 순서를 고정하거나 흡수 상태로 표시하기 위해 상태를 명시적으로 선언할 수 있습니다.

markov "Gambler's ruin"
  state Broke "$0" absorbing
  state Rich  "$4" absorbing
  state S1
  state S2
  Broke -> Broke : 1
  Rich  -> Rich  : 1
  S1 -> Broke : 0.5
  S1 -> S2 : 0.5
  S2 -> S1 : 0.5
  S2 -> Rich : 0.5

state ID "label" absorbing — 레이블은 선택 사항이며, absorbing은 해당 상태가 싱크(자기 루프 확률 1)임을 선언합니다. 엔진은 이 선언을 행렬과 교차 검증합니다.

3. 지시어

layout: layered       # 레이아웃 모드
normalize: true        # 오류 대신 각 행의 합이 1이 되도록 스케일 조정
analysis: classify, absorbing   # 계산할 항목: classify | absorbing | stationary

• normalize: true — 각 행을 합이 1이 되도록 재조정합니다(A -> B : 1, A -> C : 1처럼 정규화되지 않은 가중치에 유용합니다). 이 옵션 없이 합이 1이 되지 않는 행은 하드 에러입니다.
• analysis: — 실행하고 표시할 계산을 선택합니다.

4. 계산 결과

이것이 Schematex의 차별점입니다. 의존성 없이 직접 구현된 선형 대수 세 단계:

1. 행렬 조립 + 검증 — P를 구성하고 행 합계 정책을 적용합니다(하드 에러 또는 normalize 시 재조정).
2. 상태 분류 — Tarjan SCC → 통신 클래스; 클래스가 닫혀 있으면 재귀적, 그렇지 않으면 일시적; 자기 루프 확률이 1인 단원소 닫힌 집합은 흡수 상태입니다.
3. 정량적 결과:
   • 정상 분포 π (πP = π, Σπ = 1): 주기적 체인을 위한 정확한 가우스 소거법 대체를 포함한 거듭제곱 반복으로 계산합니다.
   • 흡수 체인의 경우: 기본 행렬 N = (I−Q)⁻¹, 흡수 확률 B = N·R, 흡수까지의 기대 단계 수 t = N·1.

일시적 상태, 재귀 클래스, 흡수 상태는 각각 다르게 렌더링되며, 계산 값은 data-*에 저장됩니다.

5. 자주 발생하는 실수

# 잘못됨 — 확률이 [0,1] 범위를 벗어남
A -> B : 1.5

# 잘못됨 — 확률 없는 전이
A -> B

# 잘못됨 — 행 합계가 1이 아님 (`normalize: true` 없이)
A -> B : 0.3
A -> C : 0.3

모든 전이에는 [0, 1] 범위의 확률이 필요하며, 각 상태에서 나가는 확률의 합이 1이어야 합니다. 그렇지 않으면 normalize: true를 설정해야 합니다. 전이가 없는 빈 체인은 거부됩니다.

6. 표준 준수

이 모델은 행-확률론적 전이 행렬을 가진 이산 시간, 시간-동질 Markov chain입니다. 분류(일시적/재귀적/흡수적), 정상 분포, 흡수 체인 기본 행렬 분석은 표준 교재(Kemeny & Snell, Finite Markov Chains)를 따릅니다.

7. 로드맵

보류 항목: 연속 시간 체인(속도 행렬), 은닉 Markov 모델, 평균 초기 통과 시간, 주기성 보고.