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

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

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

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

Ссылки

  1. ^ abcde Уильямс, Лорен К. (май 2022 г.), «Комбинаторика прыгающих частиц и положительность в цепях Маркова», Информационный бюллетень Лондонского математического общества (500): 50–59 , arXiv : 2202.00214
  2. ^ Хилл, Террелл Л. (апрель 1966 г.), «Исследования по необратимой термодинамике IV: схематическое представление потоков стационарного состояния для мономолекулярных систем», Журнал теоретической биологии , 10 (3): 442– 459, Bibcode : 1966JThBi..10..442H, doi : 10.1016/0022-5193(66)90137-8, PMID  5964691
  3. ^ Лейтон, Фрэнк Томсон ; Ривест, Рональд Л. (1986), «Оценка вероятности с использованием конечной памяти», IEEE Transactions on Information Theory , 32 (6): 733– 742, CiteSeerX 10.1.1.309.6684 , doi :10.1109/TIT.1986.1057250 
Взято с "https://en.wikipedia.org/w/index.php?title=Markov_chain_tree_theorem&oldid=1268534082"