마르코프 연쇄수 정리

마르코프 연쇄의 수학 이론에서 마르코프 연쇄 나무 정리는 최종적으로 많은 상태를 가진 마르코프 연쇄의 정상 분포에 대한 표현이다.마르코프 사슬의 뿌리 스패닝 트리에 대한 용어를 각 트리에 대한 양의 조합으로 요약합니다.마르코프 연쇄 나무 정리는 그래프의 스패닝 트리를 세는 키르히호프의 정리와 밀접하게 관련되어 있으며,^[1] 여기서 파생될 수 있다.이것은 ^[1][2]열역학에서 발생하는 특정 마르코프 체인에 대해 힐(1966년)에 의해 처음 언급되었고, 라이튼 & 리베스트(1986년)에 의해 편향된 ^[1][3]동전의 확률에 대한 제한된 기억 추정에 대한 응용에 의해 동기 부여되어 완전한 일반성을 증명했다.

유한 마르코프 체인은 유한한 상태 집합과 상태$i$에서 $상태{\displaystyle }$j(\$displaystyle$$$i$)$로 변화하기 위한 전이 $확률{\displaystyle {}_{}}$ ${\displaystyle {p,}_{}}$(\$displaystyle$ $p_{i,j})$로 구성되어 각 상태에 대해 발신 전이 확률이 1이 된다.(이 문제와 무관한 것으로 판명된) 상태의 최초 선택에서 각 연속 상태는 이전 상태로부터의 전이 확률에 따라 무작위로 선택됩니다.마르코프 사슬은 모든 상태가 어떤 천이의 시퀀스를 통해 다른 모든 상태에 도달할 수 있을 때 환원 불가능하다고 하며, 만약 모든 상태에 대해 그 상태에서 시작하고 끝나는 시퀀스의 가능한 단계 수가 최대 공통 제수를 갖는다면 비주기적이라고 한다.환원 불가능한 비주기적 마르코프 사슬은 반드시 정상 분포, ^[1]즉 상태의 초기 선택에 관계없이 많은 단계 후에 주어진 상태에 있을 확률을 기술하는 그 상태에 대한 확률 분포를 가진다.

마르코프 연쇄 트리 정리는 지정된 루트로 향하는, 나무로 정의된 마르코프 연쇄의 상태에 대한 스패닝 트리를 고려하며, 여기서 모든 유도된 가장자리는 주어진 마르코프 연쇄의 유효한 전이이다.$상태{\displaystyle }$i에서 $상태{\displaystyle }$j({$displaystyle$i})로의 이행이 $이행확률{\displaystyle {}_{}}$ ${\displaystyle {pi,}_{}}$({$displaystyle p_{i,j$인 경우 엣지 세트 $(T)$의 $트리{\displaystyle }$ T$({displaystyle$ T$})$는 이행확률 곱과 동일한 가중치를 갖도록 정의됩니다.

$$\displaystyle w(T)=\prod _{(i,j)\in E(T)}p_{i,j}.}$$

$(\$})는$$ 루트에 $상태{\displaystyle }$i(\$displaystyle$ i$)$가 있는 모든 스패닝 트리의 집합을 $나타냅니다{\displaystyle {\mathcal{}}_{}}$.다음으로 마르코프 연쇄 트리 정리에 따르면 상태$i$에 대한 정상 확률 ${\displaystyle {\theta }_{}}$ i$\$$displaystyle$$\pi$ _${i$$}$는 i$\displaystyle$i에$$$뿌리$를 둔 나무의 무게 합계에 비례한다.그것은,

$$\displaystyle \pi _{i}=sum frac {1}{Z}}\sum _{T\in\mathcal {T}_{i}w(T)},}$$

여기서 정규화 $상수{\displaystyle }$Z(\$displaystyle$ Z$)$는 모든 스패닝 ^[1]트리에 대한 w$(T)$의 $합계$입니다.

레퍼런스