Цепи Маркова, деревья и близкие задачи

Доклад будет посвящен замечательной теореме в теории конечных марковских цепей - марковская цепь и деревья (МЦД), позволяющей выразить предельное распределение для конечной эргодической цепи в терминах направленных полных деревьев. Эта теорема была в другой форме открыта знаменитым физиком XIX века Г.Кирхгофом для расчета электрических цепей, она связывает цепи Маркова и теорию графов, а также математику и теорию электрических цепей. Ключевую роль в этой теореме играет вектор $q=(q(y), y\in S)$, где $y$ – точка в пространстве состояний $S$, а $q(y)$ вычисляется суммированием произведений соответствующих переходных вероятностей по всем полным деревьям, направленным в точку $y$. Применение этой теоремы сдерживается тем, что число деревьев в графе растет экспоненциально. В статье Сонина (Sonin, 1999) было замечено и доказано что существует простой полиномиальный алгоритм вычисления вектора $q(y)$, имеющий простую вероятностную интерпретацию. Доказательство было довольно сложным и использовало тонкие факты из теории графов. Этот алгоритм и теорема были обобщены на случай так называемого идемпотентного анализа в статье (Gursoy et al., 2015). Другое доказательство этой же теоремы было получено в статье (Fomin et al., 2016). В докладе будет объяснено новое доказательство этой теоремы, не использующее никаких результатов из теории графов.