является ли матрица эргодичной или нет

midasco

Есть матрица значений (матрица переходов из одного состояния в другое). По какому критерию можно определить является ли данная матрица эргодичной или нет. Какие есть теоремы или признаки...Что-то не могу найти что-либо подходящее в Феллере. Заранее спасибо.

a7137928

Плохо ищешь, значит.
Первый том Феллера, глава 15. Марковские цепи. Тебя будут интересовать, видимо, параграфы "Замкнутые множества", "классификация состояний", "Эргодическое свойство".
Как проверить цепь на эргодичность:
Способ 1) разбиваешь все состояния на замкнутые классы, так чтобы в пределах одного класса из любого состояния можно было попасть в любое за конечное время с положительной вероятностью. Если у тебя всего один класс, значит твоя цепь эргодична.
Способ 2) Берёшь матрицу переходов и ищешь предел P^n при n стремящемся к бесконечности. Если есть эргодичность, то предел будет выглядеть как матрица, в каждой строке которой записано стационарное распределение цепи. Если предела нет, то нет и эргодичности.

midasco

Это я все читал в Феллере и согласен. Но 1 способ не подходит: большие размеры матрицы и ее тяжело становится анализировать таким образом. А второй способ мне непонятно, как искать предел аналитически. Допустим я написал процедуру перемножения матриц и могу искать для произвольного r перемножение матриц, то как я найду предел при r, стремящимся к бесконечности. ИЛи это умеет делать матлаб или maple?

a7137928

Ты на компьютере считаешь?
Тогда можно попробовать так: ищем левую собственную вектор-строку (с собственным значением 1). Это будет стационарное распределение. Если существует единственный (с точн. до мультипликативного множителя) вектор [math]$\pi$[/math], разрешающий систему
[math]$\pi \cdot P = \pi$[/math]
да ещё и являющийся вектором распределения (все компоненты неотрицательны то это говорит об эргодичности.
Или так тоже не получится посчитать?

midasco

левый собственный вектор я нашел (отвечающий собственному значению 1)! Но из этого не следует, что что это есть стационарное распределение. Необходимо показать эргодичность, тогда будеи обоснованно, что это и есть стационарное распределение.

natunchik

Я не понимаю чего-то?
Если у тебя есть матрица n*n, то разбиение на состояния совсем тупым методом занимает n*n*n, при этом наверняка можно ускорить практически до n*n.
Вычисление же хотя бы квадрата матрицы уже жрёт n*n*n операций.

a7137928

Но из этого не следует, что что это есть стационарное распределение
:mad:
Извините, а какое это тогда распределение?
Найден левый собственный вектор. Запускаем цепь с этим начальным распределением и нашей матрицей переходных вероятностей. Поскольку вектор собственный, то распределение цепи на каждом шаге будет сохраняться. Значит, это и есть стационарное распределение.
Далее.
1) Если цепь конечна, то хотя бы одно стационарное распределение у неё есть.
2) Если цепь эргодична, то стационарное распределение единственно.
Значит, если левый собственный вектор только один, то цепь эргодична.

midasco

это точно так?
По-моему, все с точностью наоборот...

a7137928

Предлагаю тебе подтвердить свою точку зрения ссылками на теоремы из Феллера, тогда и поговорим. Тем более, что ты их вроде уже изучил.

midasco

Вот хоть убей, но не понимаю...
1) Если цепь конечна, то хотя бы одно стационарное распределение у неё есть.
Откуда данное утверждение 1)? В Феллере я что-то не могу найти такого...
Со 2) утверждением согласен, а вот с выводом НЕТ! Во втором утверждение следствие в одну сторону!
2) Если цепь эргодична, то стационарное распределение единственно.
Значит, если левый собственный вектор только один, то цепь эргодична.

a7137928

1) Если цепь конечна, то хотя бы одно стационарное распределение у неё есть.
Откуда данное утверждение 1)? В Феллере я что-то не могу найти такого...
Да йопрст.
Берём цепь.
Выкидываем всё говно (невозвратные состояния). Остаются только замкнутые классы.
Каждый класс либо периодический, либо апериодический.
В каждом апериодическом классе существует единственное стационарное распределение. Феллер, первый том, глава 15, параграф 6.
В каждом периодическом классе тоже существует единственное стационарное распределение. Феллер, первый том, глава 15, параграф 7.
Таким образом, если замкнутый класс всего один, то существует единственное стац. распределение. В этом случае цепь эргодична, проверяется тупо по определению или по какому-нибудь свойству эргодичности, в зависимости от того, как ты её определяешь.
Если замкнутый класс не один, то мы можем посадить в каждый замкнутый класс своё стац. распределение, и взять произвольную выпуклую комбинацию этих распределений. Эргодичности в этом случае не будет.
Всё, анализ цепи закончен.
Утверждение "в конечной цепи всегда есть хоть одно стац. распределение" следует из того, что в конечной цепи всегда есть хотя бы один замкнутый класс.
Если стац. распределение всего одно, то цепь заведомо эргодична, потому что других вариантов нет.
Блин, я не знаю, как объяснить ещё. Это же вроде простые достаточно вещи. Ну почитай второй том Ширяева вместо Феллера, там есть всё то же самое, только с картинками и, на мой взгляд, более хорошо написано.

midasco

В этом случае цепь эргодична, проверяется тупо по определению или по какому-нибудь свойству эргодичности, в зависимости от того, как ты её определяешь.
Кроме как через предел при n, стремящимся к бесконечности, как проверить можно эргодиность? Какие еще есть свойства эргодичноcти, которые можно на практике применить без аналиического расчета предела по определению?

a7137928

как проверить можно эргодиность? Какие еще есть свойства эргодичноcти, которые можно на практике применить без аналиического расчета предела по определению?
Это зависит от того, как ты определяешь эргодичность.
Я определяю так:
1) Мера эргодична относительно измеримого преобразования, если все инвариантные множества тривиальны (имеют меру 0 или 1). При этом хорошо бы мере самой быть инвариантной относительно преобразования. Но это не обязательно.
2) Стационарная марковская цепь (характеризуемая начальным распределением и переходными вероятностями) эргодична, если распределение, которое она задаёт на пространстве последовательностей с цилиндрической сигма-алгеброй, эргодично относительно сдвига влево.
И поэтому мне вообще ничего доказывать не надо. Единственные инвариантные относительно сдвига множества в пространстве состояний стационарной марковской цепи задаются замкнутыми классами. Если замкнутый класс один, то инвариантными множествами будут либо пустое множества, либо множество, порождённое этим замкнутым классом, т.е. всё пространство (несущественные состояния не в счёт). А если классов больше одного, то инвариантные множества уже появляются, и эргодичности нет.
Если же ты под эргодичностью имеешь в виду существование предела переходных вероятностей за n шагов, и больше ты ничего про эргодичность не знаешь - значит ищи предел.
Меня ломает опять лезть в Феллера, но в Ширяеве про эргодичность дело всё написано. Новое издание, второй том, глава 5, параграф 2 - там определение эргодичности меры. Глава 8, параграфы 6 и 7 - применительно к марковским цепям.

491593

а что такое марковская цепь?
Оставить комментарий
Имя или ник:
Комментарий: