Markov Chain: 상태 전이 확률

2026년 6월 29일 · 수정 2026년 6월 29일 · 📖 약 1분 · 159자/단어 #algorithm #foundation #probability #markov

정의

Markov Chain 은 다음 상태가 오직 현재 상태에만 의존하는 확률 과정. memoryless property.

전이확률 행렬 P: P[i][j] = P(다음 = j | 현재 = i). 각 행 합 = 1.

$P^{n}$ 의 (i, j) 원소 = i 에서 j 로 n 스텝에 도달할 확률.

Matrix Exponentiation 으로 O(K³ log n) 에 계산.

π P = π 인 확률벡터 π. irreducible + aperiodic 이면 유일 존재.

웹 페이지 랭킹은 stationary distribution 문제로 환원 (Google, 1998).

이 글의 용어 (3개)

Expected Value: 기댓값, Linearityalgorithm: 정의 확률변수 X 의 기댓값: $$ E[X] = \sumx x \cdot P(X = x) \quad \text{(discrete)} $$ $$ E[X] = \int x \cdot…
Federated Learning: 분산 학습 without central dataml: 정의 Federated Learning (FL) 은 데이터를 중앙에 모으지 않고 각 클라이언트 (edge device, 병원, 은행 등) 가 로컬 데이터로 모델을 학습한 뒤 모델…
Matrix Exponentiation: 선형 점화식 fastalgorithm: 정의 선형 점화식을 행렬 곱으로 표현한 뒤, 행렬 거듭제곱을 log 시간에 계산하여 N 번째 항을 O(K³ log N) 에 얻는 기법. K = 상태 차원. Fibonacci 예 …