이산 시간 마르코프 연쇄

이산 시간 마르코프 연쇄는 정수 시간(integer times)에 걸쳐 셀 수 있는 상태 집합(countable set of states) 사이를 이동하며, 현재 상태에만 의존하는 확률로부터 다음 상태를 선택하고, 이는 전이 행렬(transition matrix)에 간결하게 인코딩됩니다.

Definition

이산 시간 마르코프 연쇄는 셀 수 있는 집합 내의 무작위 상태 시퀀스로, 다음 상태의 확률이 현재 상태에만 의존하며, 이러한 한 단계 확률(one-step probabilities)은 전이 행렬에 수집됩니다.

Scope

이 주제는 전이 행렬과 채프먼-콜모고로프 방정식(Chapman-Kolmogorov equations), 강한 마르코프 속성(strong Markov property), 상태를 통신 클래스(communicating classes)로 분류하고 일시적(transient), 영 재귀적(null-recurrent), 양 재귀적(positive-recurrent)으로 분류하는 것, 주기성(periodicity), 첫 단계 분석(first-step analysis)으로 계산되는 도달 확률(hitting probabilities) 및 예상 도달 시간(expected hitting times), 그리고 정수 격자(integer lattice) 상의 무작위 행보(random walks)에 대한 재귀 이분법(recurrence dichotomy)을 다룹니다.

Core questions

• 전이 행렬은 여러 단계에 걸친 연쇄의 동역학을 어떻게 인코딩합니까?
• 상태는 통신 구조와 재귀성에 따라 어떻게 분류됩니까?
• 도달 확률과 예상 도달 시간은 어떻게 계산됩니까?
• 어떤 무작위 행보가 확실히 시작점으로 돌아오고 어떤 행보가 무한대로 벗어납니까?

Key concepts

• 전이 행렬
• 채프먼-콜모고로프 방정식
• 통신 클래스
• 재귀성 및 일시성
• 도달 시간

Key theories

강한 마르코프 속성

마르코프 속성은 정지 시간(stopping times)이라고 불리는 적절한 무작위 시간에도 계속 유지되므로, 연쇄는 그러한 시간의 상태에서 새롭게 다시 시작되며, 이는 복귀, 이탈, 도달 시간을 분석하는 핵심 도구입니다.

재귀 이분법

각 상태는 확률 1로 무한히 자주 방문되는 재귀적이거나, 유한하게만 방문되는 일시적(transient)입니다. 단순 대칭 무작위 행보(simple symmetric random walk)의 경우 이는 차원에 따라 달라지며, 1차원과 2차원에서는 재귀적이고 3차원 이상에서는 일시적입니다.

Clinical relevance

이산 시간 마르코프 연쇄는 보드 게임, 재고 및 대기열 시스템, PageRank 연쇄를 통한 웹 탐색, 유전 및 생태학적 천이(ecological succession)를 모델링합니다. 이들의 도달 시간 및 재귀 이론은 시스템이 목표 상태에 도달하거나 참조 조건으로 돌아오는 데 걸리는 시간에 대한 실제적인 질문에 답합니다.

History

마르코프는 1906년에 이러한 연쇄를 도입하여 푸시킨 시의 모음과 자음 시퀀스에 적용함으로써 종속 변수(dependent variables)에 대해서도 큰 수의 법칙(law of large numbers)이 성립함을 보였습니다. 폴리아(Polya)의 1921년 무작위 행보 분석은 그의 영향을 받은 차원 의존적 재귀 이분법(dimension-dependent recurrence dichotomy)을 확립했습니다.

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

재귀 상태와 일시 상태의 차이점은 무엇입니까?

재귀 상태는 연쇄가 확실히 돌아올 것이며 무한히 자주 방문하는 상태인 반면, 일시 상태는 연쇄가 영원히 벗어나기 전에 유한한 횟수만 방문하는 상태입니다.

단순 무작위 행보가 낮은 차원에서는 재귀적이지만 높은 차원에서는 그렇지 않은 이유는 무엇입니까?

1차원과 2차원에서는 행보가 확률 1로 원점으로 돌아오지만, 3차원부터는 벗어날 공간이 충분하여 행보가 유한한 횟수만 돌아오고 일시적이 됩니다. 이는 폴리아의 고전적인 결과입니다.