|
|
Семинар отдела дискретной математики МИАН
26 декабря 2017 г. 16:00, г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
|
|
|
|
|
|
Цепи Маркова, деревья и близкие задачи
И. М. Сонин University of North Carolina Charlotte
|
Количество просмотров: |
Эта страница: | 204 |
|
Аннотация:
Доклад будет посвящен замечательной теореме в теории конечных
марковских цепей - марковская цепь и деревья (МЦД), позволяющей выразить
предельное распределение для конечной эргодической цепи в терминах
направленных полных деревьев. Эта теорема была в другой форме открыта
знаменитым физиком XIX века Г.Кирхгофом для расчета электрических цепей,
она связывает цепи Маркова и теорию графов, а также математику и теорию
электрических цепей. Ключевую роль в этой теореме играет вектор
$q=(q(y), y\in S)$, где $y$ – точка в пространстве состояний $S$, а
$q(y)$ вычисляется суммированием произведений соответствующих переходных
вероятностей по всем полным деревьям, направленным в точку $y$.
Применение этой теоремы сдерживается тем, что число деревьев в графе
растет экспоненциально. В статье Сонина (Sonin, 1999) было замечено и
доказано что существует простой полиномиальный алгоритм вычисления
вектора $q(y)$, имеющий простую вероятностную интерпретацию.
Доказательство было довольно сложным и использовало тонкие факты из
теории графов. Этот алгоритм и теорема были обобщены на случай так
называемого идемпотентного анализа в статье (Gursoy et al., 2015).
Другое доказательство этой же теоремы было получено в статье (Fomin et
al., 2016). В докладе будет объяснено новое доказательство этой теоремы,
не использующее никаких результатов из теории графов.
|
|