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