Теорема о дереве цепи Маркова

В математической теории цепей Маркова теорема о дереве цепей Маркова является выражением стационарного распределения цепи Маркова с конечным числом состояний. Он суммирует члены для корневых остовных деревьев цепи Маркова с положительной комбинацией для каждого дерева. Теорема о дереве цепи Маркова тесно связана с теоремой Кирхгофа о подсчете остовных деревьев графа, из которой она может быть получена. Впервые это было сформулировано Хиллом (1966) для некоторых цепей Маркова, возникающих в термодинамике : и в полной мере доказан Лейтоном и Ривестом (1986) , мотивированным применением в оценке вероятности смещенной монеты с ограниченной памятью .

Конечная цепь Маркова состоит из конечного набора состояний и вероятности перехода $p_{i,j}$ для перехода из штата $i$ заявить $j$, так что для каждого состояния сумма вероятностей исходящего перехода равна единице. Из первоначального выбора состояния (который оказывается не имеющим отношения к этой проблеме) каждое последующее состояние выбирается случайным образом в соответствии с вероятностями перехода из предыдущего состояния. Цепь Маркова называется неприводимой, когда каждое состояние может достичь любого другого состояния посредством некоторой последовательности переходов, и апериодической, если для каждого состояния возможное количество шагов в последовательностях, которые начинаются и заканчиваются в этом состоянии, имеют наибольший общий делитель, равный единице. Неприводимая и апериодическая цепь Маркова обязательно имеет стационарное распределение, распределение вероятностей ее состояний, которое описывает вероятность пребывания в заданном состоянии после многих шагов, независимо от первоначального выбора состояния.

Теорема о дереве цепи Маркова рассматривает остовные деревья для состояний цепи Маркова, определенные как деревья , направленные к назначенному корню, в которых все направленные ребра являются допустимыми переходами данной цепи Маркова. Если переход из состояния $i$ заявить $j$ имеет вероятность перехода $p_{i,j}$, затем дерево $T$ с набором кромок $E(T)$ определяется как имеющий вес, равный произведению его вероятностей перехода: $$w(T)=\prod _{(i,j)\in E(T)}p_{i,j}.$$Позволять ${\mathcal {T}}_{i}$ обозначают набор всех остовных деревьев, имеющих состояние $i$ в их корне. Тогда, согласно теореме о дереве цепей Маркова, стационарная вероятность $\pi _{i}$ для государства $i$ пропорциональна сумме весов деревьев с корнями в $i$. То есть, $$\pi _{i}={\frac {1}{Z}}\sum _{T\in {\mathcal {T}}_{i}}w(T),$$где нормировочная константа $Z$ это сумма $w(T)$ над всеми пролетными деревьями.