Дискретные цепи Маркова

Что такое дискретные цепи Маркова?

Рассмотрите стохастический процесс, принимающий значения в state space. Markov process развивается способом, который независим от пути, который приводит к текущему состоянию. Таким образом, текущее состояние содержит всю информацию, необходимую, чтобы предсказать условные вероятности будущих путей. Эта характеристика называется Markov property. Несмотря на то, что процесс Маркова является определенным типом стохастического процесса, он широко используется в моделировании изменений состояния. Специфика процесса Маркова приводит к теории, которая относительно завершена.

Процессы Маркова могут быть ограничены в различных способах, ведя к прогрессивно более кратким математическим формулировкам. Следующие условия являются примерами ограничений.

Пространство состояний может быть ограничено дискретным набором. Эта характеристика показательна из Markov chain. Вероятности перехода свойства Маркова “соединяют” каждое состояние в цепи к следующему.
Если пространство состояний конечно, цепью является finite-state.
Если процесс развивается на шагах дискретного времени, цепью является discrete-time.
Если свойство Маркова независимо от времени, цепью является homogeneous.

Econometrics Toolbox™ включает dtmc объект модели, представляющий конечное состояние, дискретное время, гомогенная Цепь Маркова. Даже с ограничениями, dtmc объект имеет большую применимость. Это достаточно устойчиво, чтобы служить во многих сценариях моделирования в эконометрике, и математическая теория хорошо подходит для матричной алгебры MATLAB^®.

Цепи Маркова конечного состояния имеют двойную теорию: один в анализе матрицы и один в дискретных графиках. Объектные функции dtmc возразите подсвечивают эту дуальность. Функции позволяют вам двигаться вперед-назад между числовыми и графическими представлениями. Можно работать с инструментами, которые подходят лучше всего для конкретных аспектов расследования. В частности, традиционные методы собственного значения для определения структуры матрицы перехода соединяются с визуализацией для трассировки эволюции цепи через ее связанный диграф.

Ключевая возможность любой Цепи Маркова является своим ограничивающим поведением. Эта функция особенно важна в эконометрических приложениях, где эффективность прогноза модели зависит от того, имеет ли ее стохастический компонент четко определенное распределение, асимптотически. Объектные функции dtmc объект позволяет вам исследовать переходное и установившееся поведение цепи и свойств, которые производят уникальный предел. Другие функции вычисляют ограничивающее распределение и оценивают уровни сходимости или mixing times.

Симуляция базового стохастического процесса подходящей Цепи Маркова является основным принципом приложения. Симуляция может принять форму генерации случайной последовательности изменений состояния от начального состояния или от эволюции времени целого распределения состояний. Симуляция позволяет вам определять статистические характеристики цепи, которая не может быть очевидна из ее спецификации или теории. В эконометрике Цепи Маркова становятся компонентами больших переключающих режим моделей, где они представляют, переключает экономическую обстановку на нижний регистр. dtmc объект включает функции для симуляции и визуализации эволюции времени Цепей Маркова.

Теория дискретной цепи Маркова

Любое конечное состояние, дискретное время, гомогенная Цепь Маркова может быть представлена, математически, или ее n-by-n матрица перехода P, где n является количеством состояний или его ориентированным графом D. Несмотря на то, что эти два представления эквивалентны — анализ, выполняемый в одной области, приводит к эквивалентным результатам в другом — существуют существенные различия и в концепции аналитических вопросов и в получившихся алгоритмических решениях. Эта дихотомия лучше всего проиллюстрирована путем сравнения разработки теории в [7], например, с разработками в [6] и [9]. Или с помощью MATLAB дихотомия может быть проиллюстрирована путем сравнения алгоритмов на основе graph возразите и его функции с базовой функциональностью в анализе матрицы.

Полный график для процесса конечного состояния имеет ребра и вероятности перехода между каждым узлом i и любым узлом j. Узлы представляют состояния в Цепи Маркова. В D, если матричная запись _Pij 0, то ребро, соединяющее состояния i и j, удалено. Поэтому D показывает только переходы feasible среди состояний. Кроме того, D может включать self-loops, указывающий на ненулевые вероятности _Pii перехода от i состояния назад к себе. Самовероятности перехода известны как inertia состояния или persistence.

В D walk между состояниями i и j являются последовательностью связанных состояний, которая начинается в i и заканчивается в j и имеет длину по крайней мере двух. path является обходом без повторных состояний. circuit является обходом, в котором i = j, но не присутствуют никакие другие повторные состояния.

j состояния является reachable или accessible, от i состояния, обозначенного $i \to j$ , если существует обход от i до j. Состояния communicate, обозначенный $i \leftrightarrow j$ , если каждый достижим от другого. Коммуникация является отношением эквивалентности на пространстве состояний, деля его в связывающиеся классы. В теории графов состояния, которые связываются, называются strongly connected components. Для процессов Маркова важные свойства отдельных государств совместно используются всеми другими состояниями в связывающемся классе, и так станьте свойствами самого класса. Эти свойства включают:

Recurrence — Свойство того, чтобы быть достижимым от всех состояний, которые достижимы. Это свойство эквивалентно асимптотической вероятности возврата, равного 1. Каждая цепь имеет по крайней мере один текущий класс.
Transience — Свойство того, чтобы не быть текущим, то есть, возможность доступа к состояниям, от которых нет никаких, возвращается. Это свойство эквивалентно асимптотической вероятности возврата, равного 0. Класс с быстротечностью не оказывает влияния на асимптотическое поведение.
Periodicity — Свойство циклического повторения среди нескольких подклассов в классе и сохранении некоторой памяти о начальном состоянии. Период состояния является наибольшим общим делителем длин всех схем, содержащих состояние. Состояния или классы с периодом 1 являются апериодическими. Самоциклы на состояниях гарантируют апериодичность и формируют основание для lazy chains.

Важным свойством цепи в целом является irreducibility. Цепь неприводима, если цепь состоит из одного класса передачи. Состояние или свойства класса становятся свойствами целой цепи, которая упрощает описание и анализ. Обобщением является unichain, который является цепью, состоящей из одного текущего класса и любое количество переходных классов. Важные анализы, связанные с asymptotics, могут быть сфокусированы на текущем классе.

График condensed, который формируется путем консолидации состояний каждого класса в один суперузел, упрощает визуальное понимание полной структуры. В этом рисунке одном ориентированном ребре между суперузлами C1 и C2 соответствуют уникальному направлению перехода между классами.

Сжатый график показывает, что C1 является переходным, и C2 является текущим. outdegree C1 положителен, который подразумевает быстротечность. Поскольку C1 содержит самоцикл, это является апериодическим. C2 является периодическим с периодом 3. Одно состояния в с тремя циклами из C2, в более общем периодическом классе, передавая подклассы. Цепь является приводимым unichain. Вообразите ориентированное ребро от C2 до C1. В этом случае C1 и C2 передают классы, и они выходят из строя в один узел.

Ergodicity, желательное свойство, комбинирует неприводимость с апериодичностью и универсальной формой гарантий ограничение поведения. Поскольку неприводимость является по сути цепочечным свойством, не свойством класса, эргодичность является цепочечным свойством также. Когда используется с unichains, эргодичность означает, что уникальный текущий класс является эргодическим.

С этими определениями возможно обобщить основное существование и теоремы уникальности, связанные с 1 n стационарными распределениями $π^{*}$ , где $π^{*} = π^{*} P$ .

Если P правильный стохастический, то $π^{*} = π^{*} P$ всегда имеет решение для вектора вероятности. Поскольку каждая строка сумм P одной, P имеет правый собственный вектор с собственным значением одного. А именно, e = 1_n, n-by-1 вектор из единиц. Так, P также имеет левый собственный вектор $π^{*}$ с собственным значением одного. В результате Теоремы Крыльца-Frobenius, $π^{*}$ является неотрицательным и может быть нормирован, чтобы произвести вектор вероятности.
$π^{*}$ уникально, если и только если P представляет unichain. В общем случае, если цепь содержит k текущие классы, π^* =, π ^*P имеет k линейно независимые решения. В этом случае ^Pm сходится как $m \to \infty$ , но строки не идентичны.
Каждое начальное распределение π ₀ сходится к $π^{*}$ если и только если P представляет эргодический unichain. В этом случае, $π^{*}$ limiting distribution.

Теорема Крыльца-Frobenius является набором результатов, связанных с собственными значениями неотрицательных, неприводимых матриц. Примененный Цепи Маркова, результаты могут быть получены в итоге можно следующим образом. Для конечного состояния unichain, P имеет одно собственное значение λ ₁ = 1 (Perron-Frobenius eigenvalue) с сопроводительным неотрицательным левым собственным вектором $π^{*}$ (который может быть нормирован к вектору вероятности), и правый собственный вектор e = 1_n. Другие собственные значения _λi удовлетворяют $| λ_{i} | \leq 1$ , i = 2, …, n. Если unichain или единственный текущий класс unichain являются апериодическими, то неравенство строго. Когда существует периодичность периода k, существуют собственные значения k на модульном круге в корнях из единицы k. Если unichain является эргодическим, то ^Pm сходится асимптотически к $e π^{*}$ как $m \to \infty$ . Ошибка переходит в 0, по крайней мере, с такой скоростью, как $m^{q} {| λ_{s} |}^{m}$ , где _λs является собственным значением второй по величине величины, и q является кратностью _λs.

Уровень сходимости к $π^{*}$ зависит от second largest eigenvalue modulus (SLEM) $| λ_{SLEM} |$ . Уровень может быть описан в терминах spectral gap, который является $1 - | λ_{SLEM} |$ . Большие разрывы дают к более быстрой сходимости. mixing time является характеристическим временем для отклонения от равновесия в общем расстоянии изменения. Поскольку сходимость экспоненциальна, смесительное время для затухания на коэффициент e ¹

$T_{mix} = - \frac{1}{\log | λ_{SLEM} |} .$

Учитывая теоремы сходимости, смешивая времена должен быть просмотрен в контексте эргодического unichains.

Связанные теоремы в теории неотрицательных, неприводимых матриц дают удобные характеристики двух решающих свойств для равномерной сходимости: приводимость и эргодичность. Предположим, что Z является indicator или zero pattern P, то есть, матрицы с единицами вместо ненулевых записей в P. Затем P неприводим если и только если все записи ${(I + Z)}^{n - 1}$ положительны. Теорема Виландта [11] состояния, что P является эргодическим, если и только если все записи ^Pm положительны для $m > {(n - 1)}^{2} + 1$ .

Теорема Крыльца-Frobenius и связанные результаты неконструктивны для стационарного распределения $π^{*}$ . Существует несколько подходов для вычисления уникального ограничивающего распределения эргодической цепи.

Задайте _Tii return time, чтобы утвердить, что i является минимальным количеством шагов, чтобы возвратиться, чтобы утвердить i после запуска в i состояния. Кроме того, задайте mean return time _{, τii} является ожидаемым значением _Tii. То, $π^{*} = [\begin{matrix} 1 / τ_{11} & \dots & 1 / τ_{n n} \end{matrix}]$ . Этот результат имеет много интуитивного содержимого. Отдельные средние времена смешивания могут быть оценены симуляцией Монте-Карло. Однако издержки симуляции и трудности оценки сходимости, сделайте симуляцию Монте-Карло непрактичной как общий метод.
Поскольку ^Pm приближается к матрице со всеми строками, равными $π^{*}$ как $m \to \infty$ , любая строка “большой мощности” P аппроксимирует π^*. Несмотря на то, что этот метод является прямым, он включает выбор допуска сходимости и соответственно большого m для каждого P. В общем случае осложнения смешивания временного анализа также делают этот расчет непрактичным.
Линейная система $π^{*} P = π^{*}$ может быть увеличен с ограничением $\sum π^{*} = 1$ , в форме $π^{*} 1_{n - n} = 1_{n}$ , где _1n-by-n является n-by-n матрица из единиц. Используя ограничение, эта система становится

$π^{*} (I - P + 1_{n -by- n}) = 1_{n} .$
Система может быть решена эффективно с оператором обратной косой черты MATLAB и численно устойчива, потому что эргодический P не может иметь единиц по основной диагонали (в противном случае, P был бы приводим). Этот метод рекомендуется в [5].
Поскольку $π^{*}$ уникальный левый собственный вектор, сопоставленный с собственным значением Крыльца-Frobenius P, сортирование собственных значений и соответствующих собственных векторов идентифицирует $π^{*}$ . Поскольку ограничение $\sum π^{*} = 1$ не часть задачи о собственных значениях, $π^{*}$ требует нормализации. Этот метод использует устойчивые численные данные MATLAB eigs функция, и является подходом, реализованным asymptotics объектная функция dtmc объект.

Для любой Цепи Маркова анализ конечного шага может предложить свои асимптотические свойства и смешивание уровня. Анализ конечного шага включает расчет этих количеств:

hitting probability $h_{i}^{A}$ вероятность когда-либо удара любого состояния в подмножестве состояний A (цель), начинающаяся с i состояния в цепи. Категорически, совершающие нападки вероятности показывают, какие состояния достижимы от других состояний; $h_{i}^{A}$ > 0 средних значений целевой A достижимы от i состояния. Если $h_{i}^{A}$ = 0, целевой A недостижим от i состояния, означая, что i состояния является remote для цели. Если A формирует текущий класс, $h_{i}^{A}$ absorption probability.
expected first hitting time $k_{i}^{A}$ отдаленное среднее количество временных шагов, требуемых достигнуть A впервые, начинаясь с i состояния. $k_{i}^{A}$ = ∞ означает одну из следующих альтернатив:
- Начальное состояние i является удаленным для целевого A.
- Начальным состоянием i является remote-reachable для целевого A; то есть, $h_{i}^{A}$ > 0 и $h_{i}^{B}$ > 0, где B является текущим классом, не содержащим любые состояния в A.
Если A формирует текущий класс, $k_{i}^{A}$ ожидаемый absorption time.

Вектор из совершающих нападки вероятностей или ожидаемый сначала совершающие нападки времена для цели, начинающейся с каждого состояния в Цепи Маркова, предлагает смесительный уровень цепи.

Ссылки

[1] Diebold, F.X., и Г.Д. Рудебуш. Деловые циклы: длительность, динамика и прогнозирование. Принстон, NJ: Издательство Принстонского университета, 1999.

[2] Gallager, R.G. Стохастические процессы: теория для приложений. Кембридж, Великобритания: Издательство Кембриджского университета, 2013.

[3] Gilks, W. R. С. Ричардсон и Д.Дж. Спиджелхэлтер. Цепь Маркова Монте-Карло на практике. Бока-Ратон: Chapman & Hall/CRC, 1996.

[4] Haggstrom, O. Конечные цепи Маркова и алгоритмические приложения. Кембридж, Великобритания: Издательство Кембриджского университета, 2002.

[5] Гамильтон, Джеймс. D. Анализ Временных Рядов. Принстон, NJ: Издательство Принстонского университета, 1994.

[6] Рог, R. и К. Р. Джонсон. Анализ матрицы. Кембридж, Великобритания: Издательство Кембриджского университета, 1985.

[7] Джарвис, J. P. и D. R. Более застенчивый. "Теоретический графиком анализ конечных цепей Маркова". В прикладном математическом моделировании: мультидисциплинарный подход. Бока-Ратон: нажатие CRC, 2000.

[8] Maddala, G. S. и я. М. Ким. Модульные корни, коинтеграция и структурное изменение. Кембридж, Великобритания: Издательство Кембриджского университета, 1998.

[9] Монтгомери, J. Математические модели Социальных систем. Неопубликованная рукопись. Отдел Социологии, Висконсинский университет в Мадисоне, 2016.

[10] Норрис, J. R. Цепи Маркова. Кембридж, Великобритания: Издательство Кембриджского университета, 1997.

[11] Wielandt, H. Темы в Аналитической Теории Матриц. Читайте лекции примечаниям, подготовленным Р. Майером. Отдел Математики, Висконсинский университет в Мадисоне, 1967.

Смотрите также

Объекты

dtmc | graph

Функции

asymptotics | classify | eigplot | eigs | graphplot | isergodic | isreducible | lazy | mcmix

Документация