マルコフ連鎖木定理

マルコフ連鎖の数学的理論において、マルコフ連鎖木定理は、有限個の状態を持つマルコフ連鎖の定常分布を表す表現である。これは、各木に正の組み合わせを持つ、マルコフ連鎖の根付き全域木の項をまとめたものである。マルコフ連鎖木定理は、グラフの全域木を数えるキルヒホッフの定理と密接に関連しており、そこから導かれる。^{[1]これは、}熱力学で生じる特定のマルコフ連鎖について、ヒル (1966) によって最初に述べられ、 ^{[1] [2] 、レイトン & リベスト (1986) によって、}偏ったコインの確率を限られたメモリで推定するアプリケーションをきっかけに、完全に一般化されて証明された。^{[1] [3]}

有限マルコフ連鎖は、有限の状態の集合と、状態から状態へ遷移する遷移確率から成り、各状態の出力遷移確率の合計は 1 になります。状態の初期選択 (この問題とは無関係であることが判明) から、各連続状態は、前の状態からの遷移確率に従ってランダムに選択されます。マルコフ連鎖は、すべての状態が何らかの遷移シーケンスを介して他のすべての状態に到達できる場合、既約であると言われます。また、すべての状態について、その状態で開始および終了するシーケンスの可能なステップ数の最大公約数が 1 である場合、非周期的であると言われます。既約で非周期的なマルコフ連鎖には、必然的に定常分布、つまり、最初の状態選択に関係なく、多くのステップの後に特定の状態になる確率を表す状態に関する確率分布があります。^[1]${\displaystyle p_{i,j}}$${\displaystyle i}$${\displaystyle j}$

マルコフ連鎖木定理は、マルコフ連鎖の状態に対する全域木を考察します。全域木は木と定義され、指定されたルートに向けられ、すべての有向エッジは指定されたマルコフ連鎖の有効な遷移です。状態から状態への遷移が遷移確率 を持つ場合、エッジセットを持つ木は、その遷移確率の積に等しい重みを持つと定義されます。 が、ルートに状態を持つすべての全域木の集合を表すものとします 。すると、マルコフ連鎖木定理によれば、状態の定常確率は、 に根を持つ木の重みの合計に比例します。つまり、 となります。ここで、 正規化定数は、すべての全域木におけるの合計です。 ^[1]${\displaystyle i}$${\displaystyle j}$${\displaystyle p_{i,j}}$${\displaystyle T}$${\displaystyle E(T)}$$${\displaystyle w(T)=\prod _{(i,j)\in E(T)}p_{i,j}.}$$${\displaystyle {\mathcal {T}}_{i}}$${\displaystyle i}$${\displaystyle \pi_{i}}$${\displaystyle i}$${\displaystyle i}$$${\displaystyle \pi _{i}={\frac {1}{Z}}\sum _{T\in {\mathcal {T}}_{i}}w(T),}$$${\displaystyle Z}$${\displaystyle w(T)}$