Markov Chains (Concept) TODO
Concept
A Markov chain is a random process in which the distribution of the next state depends only on the current state, not on the path that led there. In the finite case it's fully described by a transition probability matrix P, and the distribution after n steps is the initial distribution multiplied by P raised to the n-th power. A stationary distribution is one that reproduces itself; if the chain is irreducible and aperiodic, the stationary distribution is unique and the chain converges to it regardless of the starting state. The rate of convergence is related to the magnitude of P's second-largest eigenvalue — this is the notion of mixing time. For chains with absorbing states, the quantities of interest are absorption probabilities and expected hitting times rather than a stationary distribution.
It lets you compute the long-run behavior of systems where "the next state is determined by the current state" — queue lengths, retry states, node synchronization stages — without simulation.
Code & Formula
# 마르코프 체인(개념) — 전이행렬의 거듭제곱 vs 정상분포(선형방정식) 비교
# 행 i, 열 j = "상태 i에서 상태 j로 갈 확률" 관례(행 합=1). 분포는 행벡터로 다룬다:
# dist_next[j] = sum_i dist[i] * P[i][j]
def step(dist, P):
n = len(dist)
return [sum(dist[i] * P[i][j] for i in range(n)) for j in range(n)]
# 상태: 0=pending, 1=included, 2=dropped (흡수상태가 있는 체인)
P = [
[0.6, 0.3, 0.1],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0],
]
dist = [1.0, 0.0, 0.0] # 전부 pending에서 시작
for t in range(1, 21):
dist = step(dist, P)
if t in (1, 2, 5, 10, 20):
print(f"step={t:2} 분포(pending,included,dropped)={[round(x, 4) for x in dist]}")
print("-> 흡수상태(included/dropped)가 있으면 정상분포는 자명(전부 흡수)해진다.\n")
# 흡수상태가 없는 기약·비주기(순환) 체인에서는 유일한 정상분포로 수렴한다
Q = [
[0.5, 0.3, 0.2],
[0.2, 0.5, 0.3],
[0.3, 0.2, 0.5],
]
dist2 = [1.0, 0.0, 0.0]
for _ in range(200):
dist2 = step(dist2, Q)
print("Q를 200번 거듭제곱해 근사한 정상분포:", [round(x, 6) for x in dist2])
# 정상분포는 pi = pi*Q, 즉 pi*(Q - I) = 0 을 만족하는 (좌)고유벡터다.
# (Q^T - I)^T pi^T = 0 형태의 3x3 선형시스템을 세우고 정규화 조건으로 한 식을 교체해 가우스 소거로 검증
n = 3
A = [[Q[j][i] - (1.0 if i == j else 0.0) for j in range(n)] for i in range(n)] # A @ pi = 0 <=> pi*Q = pi
A[-1] = [1.0, 1.0, 1.0] # 정규화 행(합=1)으로 교체
b = [0.0, 0.0, 1.0]
M = [row[:] + [b[i]] for i, row in enumerate(A)]
for col in range(n):
piv = max(range(col, n), key=lambda r: abs(M[r][col]))
M[col], M[piv] = M[piv], M[col]
for r in range(n):
if r != col:
factor = M[r][col] / M[col][col]
M[r] = [M[r][k] - factor * M[col][k] for k in range(n + 1)]
pi = [M[i][-1] / M[i][i] for i in range(n)]
print("선형방정식(고유벡터)으로 구한 정상분포 pi:", [round(x, 6) for x in pi])
print("일치 여부:", all(abs(a - b) < 1e-4 for a, b in zip(dist2, pi)))
Exercise
Build a transition matrix for three or four states, and check whether the distribution obtained by matrix powers matches the stationary distribution obtained from eigenvectors, and how many steps it takes to converge.
Practical Connection
Modeling block finalization, reorg-depth distributions, or the stages a transaction goes through before being included in the mempool as state transitions lets you approximate the expected value and tail of waiting times.
Where it lands in Jayverse
- Bridge: model the lock-and-mint state machine as a Markov chain. Estimate expected time-to-finality and its tail for pending → finalized → minted, feeding directly into the refill-rate window design.
- Rabbit: use absorption probabilities for mandate/session-key expiry. A mandate ends executed, expired, or revoked — compute expected time-to-absorption to size default session-key expiry windows.
- Verex: model the settlement queue the same way. Estimate expected wait before inclusion from transition probabilities instead of assuming a fixed block count.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| depends only on | 오직 ~에만 좌우되다 · 다음 상태가 과거 경로와 무관하게 현재 상태만으로 결정된다는 뜻 · "the next state depends only on the current state" |
| regardless of | ~와 상관없이, ~에 관계없이 · 시작 지점이 달라도 결국 같은 결과로 수렴한다는 뜻 · "converges to it regardless of the starting state" |
| mixing time | 혼합시간(수렴에 걸리는 시간) · 분포가 정상상태에 가까워지기까지 걸리는 단계 수 · "this is the notion of mixing time" |
| absorbing state | 흡수 상태 · 한번 들어가면 빠져나올 수 없는 상태 · "For chains with absorbing states, the quantities" |
| hitting time | 도달 시간 · 특정 상태에 처음 도달하기까지 걸리는 기대 시간 · "expected hitting times rather than a stationary distribution" |
| approximate | 근사치를 구하다 · 시뮬레이션 없이도 기대값과 꼬리를 어림잡아 계산한다는 뜻 · "lets you approximate the expected value and tail" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.