이산 시간 마르코프 연쇄
이산 시간 마르코프 연쇄는 정수 시간(integer time)에 따라 진화하는 무작위 상태들의 시퀀스로, 다음 상태의 분포가 전체 과거가 아닌 현재 상태에만 의존하는 특성을 가집니다.
Definition
이산 시간 마르코프 연쇄는 음이 아닌 정수(non-negative integers)로 색인된 가산 상태 공간(countable state space)에서 정의되는 확률 과정(stochastic process)으로, 전체 이력(entire history)이 주어진 상태에서 다음 상태의 조건부 분포가 현재 상태에만 의존하며, 이는 한 단계 전이 확률 행렬(one-step transition probability matrix)로 인코딩됩니다.
Scope
이 분야는 마르코프 속성(Markov property)과 전이 행렬(transition matrices), 통신(communication), 재귀성(recurrence), 일시성(transience), 주기성(periodicity)에 따른 상태 분류, 정상 분포(stationary distributions) 및 극한 분포(limiting distributions)의 존재 및 유일성, 수렴 및 혼합 속도(mixing rates), 그리고 마르코프 연쇄 몬테카를로(Markov chain Monte Carlo) 및 은닉 마르코프 모델(hidden Markov models)을 포함한 주요 응용 분야를 다룹니다.
Sub-topics
Core questions
- 마르코프 속성은 무엇을 의미하며, 전이 행렬에 의해 어떻게 포착됩니까?
- 상태는 재귀적(recurrent), 일시적(transient), 주기적(periodic) 클래스로 어떻게 분류됩니까?
- 연쇄는 언제 고유한 정상 분포를 가지며 그 분포로 수렴합니까?
- 연쇄는 평형 상태에 얼마나 빨리 접근하며, 이는 시뮬레이션에서 어떻게 활용됩니까?
Key theories
- 마르코프 속성 및 채프먼-콜모고로프 방정식
- 현재가 주어졌을 때 미래는 과거와 조건부 독립이므로, 다단계 전이 확률은 전이 행렬을 곱하여 얻어지며, 이는 한 단계 행렬로부터 n단계 행동을 계산 가능하게 합니다.
- 마르코프 연쇄에 대한 에르고딕 정리
- 기약적(irreducible), 비주기적(aperiodic), 양의 재귀적(positive-recurrent) 연쇄는 고유한 정상 분포를 가지며, 주변 분포(marginal distribution)는 이 분포로 수렴하고 함수의 시간 평균은 거의 확실하게(almost surely) 수렴하여 장기 빈도(long-run frequencies)를 정상 법칙(stationary law)과 연결합니다.
Clinical relevance
이산 시간 마르코프 연쇄는 무작위 보행(random walks), 큐잉 스냅샷(queueing snapshots), 개체군 유전학(population genetics), PageRank와 같은 순위 알고리즘, 그리고 경제 상태 전이(economic state transitions)를 모델링합니다. 이들의 수렴 이론은 통계학, 물리학, 기계 학습 전반에 걸쳐 복잡한 확률 분포에서 샘플링하는 지배적인 계산 방법인 마르코프 연쇄 몬테카를로의 기반이 됩니다.
History
안드레이 마르코프(Andrey Markov)는 1906년에 독립성(independence)을 넘어선 대수의 법칙(law of large numbers)을 확장하기 위해 의존적이지만 기억이 없는 전이(dependent but memoryless transitions)를 가진 연쇄를 도입했으며, 푸시킨(Pushkin) 시의 문자 시퀀스를 통해 이를 설명했습니다. 콜모고로프(Kolmogorov)와 되블린(Doeblin)은 1930년대에 수렴 이론을 엄격한 측도론적(measure-theoretic) 기반 위에 확립했습니다.
Key figures
- Andrey Markov
- Andrey Kolmogorov
- Wolfgang Doeblin
Related topics
Seminal works
- norris1997
Frequently asked questions
- 어떤 특성이 과정을 마르코프 연쇄로 만듭니까?
- 마르코프 속성(Markov property)입니다. 즉, 현재 상태가 주어졌을 때 미래의 진화는 연쇄가 그 상태에 도달한 방식과는 독립적이며, 따라서 전체 동역학은 한 단계 전이 확률(one-step transition probabilities)로 설명됩니다.
- 마르코프 연쇄는 언제 고유한 장기 분포로 수렴합니까?
- 연쇄가 기약적(irreducible), 비주기적(aperiodic), 그리고 양의 재귀적(positive recurrent)일 때입니다. 이 경우 시작 상태와 관계없이 연쇄가 수렴하는 단일 정상 분포가 존재합니다.