A Flow-Graph Formula for the Stationary Distribution of a Markov Chain
Overview
마르코프 체인의 정상 분포(stationary distribution)를 전이 행렬의 선형방정식으로 풀지 않고, 전이 그래프의 위상적 구조(spanning tree)로부터 직접 읽어내는 공식을 제시한다. Confluence(합류 트리)라는 개념을 핵심 도구로 사용하며, 각 상태의 정상 확률은 그 상태를 sink로 갖는 모든 confluence의 가중치 합에 비례함을 보인다.
Link to PDF and DOI
로컬 PDF: A_Flow-Graph_Formula_for_the_Stationary_Distribution_of_a_Markov_Chain.pdf
DOI: 10.1109/TSMC.1975.5408382
Related Concepts
논문 내용이 길지 않다.
바로 아래의 학습 노트 하나에 거의 모든 내용이 담겼다.