Рассмотрим стохастический процесс, принимающий значения в пространстве состояний. Процесс Маркова развивается так, что он не зависит от пути, который ведет к текущему состоянию. То есть текущее состояние содержит всю информацию, необходимую для прогнозирования условных вероятностей будущих путей. Эта характеристика называется марковской собственностью. Хотя марковский процесс является специфическим типом стохастического процесса, он широко используется при моделировании изменений состояния. Специфичность марковского процесса приводит к теории, относительно полной.
Марковские процессы могут быть ограничены различными способами, что приводит к прогрессивно более сжатым математическим формулировкам. Ниже приведены примеры ограничений.
Пространство состояний может быть ограничено дискретным набором. Эта характеристика свидетельствует о цепи Маркова. Вероятности перехода свойства Маркова «связывают» каждое состояние в цепочке в следующее.
Если пространство состояний конечное, цепочка является конечной.
Если процесс развивается дискретными временными шагами, цепочка является дискретной временной.
Если свойство Маркова не зависит от времени, цепь однородна.
Эконометрика Toolbox™ включающая dtmc объект модели, представляющий конечную, дискретно-временную, однородную цепь Маркова. Даже с ограничениями, dtmc объект имеет большую применимость. Он достаточно надежен, чтобы служить во многих сценариях моделирования в эконометрике, и математическая теория хорошо подходит для матричной алгебры MATLAB ®.
Цепи Маркова с конечным состоянием имеют двойственную теорию: одну в матричном анализе и одну в дискретных графах. Объектные функции dtmc объект выделяет эту двойственность. Функции позволяют перемещаться между числовым и графическим представлениями. Можно работать с инструментами, наиболее подходящими для определенных аспектов исследования. В частности, традиционные методы собственных значений для определения структуры матрицы перехода сопряжены с визуализацией для отслеживания эволюции цепи через связанный с ней диграф.
Ключевой особенностью любой марковской цепи является её ограничивающее поведение. Эта особенность особенно важна в эконометрических приложениях, где производительность прогноза модели зависит от того, имеет ли ее стохастический компонент четко определенное распределение, асимптотически. Объектные функции dtmc объект позволяет исследовать переходное и установившееся поведение цепи и свойства, создающие уникальный предел. Другие функции вычисляют предельное распределение и оценивают скорости сходимости или время смешения.
Моделирование основного стохастического процесса подходящей цепи Маркова является фундаментальным для применения. Моделирование может принимать форму генерации случайной последовательности переходов состояний из начального состояния или из временной эволюции всего распределения состояний. Моделирование позволяет определить статистические характеристики цепи, которые могут не быть очевидны из ее спецификации или теории. В эконометрике цепи Маркова становятся компонентами более крупных моделей переключения режимов, где они представляют собой сдвиги в экономической среде. dtmc объект включает функции моделирования и визуализации временной эволюции цепей Маркова.
Любую конечную, дискретно-временную, однородную цепь Маркова можно представить математически, посредством матрицы P перехода n-на-n, где n - число состояний, Хотя два представления эквивалентны - анализ, выполняемый в одной области, приводит к эквивалентным результатам в другой - существуют значительные различия как в концепции аналитических вопросов, так и в результирующих алгоритмических решениях. Эту дихотомию лучше всего проиллюстрировать сравнением развития теории в [7], например, с разработками в [6] и [9]. Или, используя MATLAB, дихотомия может быть проиллюстрирована путем сравнения алгоритмов, основанных на graph объект и его функции с основной функциональностью в матричном анализе.
Полный граф для конечного процесса имеет рёбра и вероятности перехода между каждым узлом i и каждым другим узлом j. Узлы представляют состояния в цепи Маркова. В D, если элемент матрицы Pij равен 0, тогда граничные соединительные состояния i и j удаляются. Поэтому D показывает только возможные переходы между состояниями. Кроме того, D может включать в себя самокольцы, указывающие ненулевые вероятности Pii перехода из состояния i обратно в себя. Вероятности самопереходов известны как инерция состояния или стойкость.
В D обход между состояниями i и j представляет собой последовательность соединенных состояний, которая начинается на i и заканчивается на j и имеет длину, по меньшей мере, две. Путь - это прогулка без повторяющихся состояний. Схема представляет собой прогулку, в которой i = j, но другие повторяющиеся состояния отсутствуют.
Состояние j достижимо или доступно из состояния i, обозначенного , если имеется переход от i к j. Состояния связываются, обозначенные , если каждое из них достижимо из другого. Связь - это отношение эквивалентности в пространстве состояний, разделяющее его на классы связи. В теории графов состояния, сообщающиеся, называются сильно связными компонентами. Для процессов Маркова важные свойства отдельных состояний совместно используются всеми остальными состояниями в связном классе, и поэтому становятся свойствами самого класса. Эти свойства включают в себя:
Recurrence - свойство быть достижимым из всех состояний, которые доступны. Это свойство эквивалентно асимптотической вероятности возврата, равной 1. Каждая цепь имеет по крайней мере один повторяющийся класс.
Переходность - свойство не быть повторяющимся, то есть возможность доступа к состояниям, из которых нет возврата. Это свойство эквивалентно асимптотической вероятности возврата, равной 0. Классы с транзитом не влияют на асимптотическое поведение.
Периодичность - свойство цикла между несколькими подклассами внутри класса и сохранения некоторой памяти начального состояния. Период состояния является наибольшим общим делителем длин всех цепей, содержащих состояние. Состояния или классы с периодом 1 являются апериодическими. Самокольцы на состояниях обеспечивают апериодичность и составляют основу для ленивых цепей.
Важным свойством цепи в целом является неприводимость. Цепь неприводима, если она состоит из одного класса связи. Свойства состояния или класса становятся свойствами всей цепочки, что упрощает описание и анализ. Обобщение - это унихайн, представляющий собой цепочку, состоящую из единого рекуррентного класса и любого числа переходных классов. Важные анализы, связанные с асимптотикой, могут быть сосредоточены на рецидивирующем классе.
Сконденсированный граф, который образуется путём консолидации состояний каждого класса в одну сверхнороду, упрощает визуальное понимание общей структуры. На этом рисунке один направленный край между супернодами C1 и C2 соответствует уникальному направлению перехода между классами.
Сжатый график показывает, что C1 является переходным и C2 является повторяющимся. Давность C1 положительна, что подразумевает скоротечность. Поскольку C1 содержит самокольцо, оно является апериодическим. C2 является периодическим с периодом 3. Единичные состояния в трёхцикле C2 являются, в более общем периодическом классе, сообщающимися подклассами. Цепь является редуцируемым унихаином. Представьте себе направленный край от C2 до C1. В этом случае C1 и C2 обмениваются классами, и они сворачиваются в один узел.
Эргодичность, желательное свойство, сочетает неприводимость с апериодичностью и гарантирует равномерное ограничивающее поведение. Поскольку неприводимость по своей сути является свойством цепи, а не классовым свойством, эргодичность также является свойством цепи. При использовании с унихинами эргодичность означает, что уникальный повторяющийся класс эргодичен.
С помощью этих определений можно суммировать фундаментальные теоремы существования и уникальности, относящиеся к 1-на-n стационарным распределениям , где .
Если P является правильным стохастическим, то всегда имеет решение вектора вероятности. Поскольку каждая строка P суммируется до единицы, P имеет правый собственный вектор с собственным значением единицы. В частности, e = 1n, вектор n-by-1 единиц. Так, P также имеет левый собственный вектор с собственным значением единицы. Как следствие теоремы Перрона - Фробениуса, неотрицательна и может быть нормализована для получения вектора вероятности.
уникален тогда и только тогда, когда P представляет unichain. В общем случае, если цепь содержит k рекуррентных классов, λ * = λ * P имеет k линейно независимых решений. В этом случае Pm сходится m→∞, но строки не идентичны.
Каждое начальное распределение § 0 сходится к тогда и только тогда, когда P представляет эргодический унихайн. В этом случае является ограничивающим распределением.
Теорема Перрона - Фробениуса - совокупность результатов, связанных с собственными значениями неотрицательных, неприводимых матриц. Применительно к цепям Маркова результаты можно суммировать следующим образом. Для унихена конечного состояния P имеет единственное собственное значение λ 1 = 1 (собственное значение Перрона-Фробениуса) с сопутствующим неотрицательным левым собственным вектором (который можно нормализовать до вектора вероятности) и правым собственным вектором e = 1n. Другие собственные значения λ i удовлетворяют , i = 2,..., n. Если унихаин или единственный рецидивирующий класс унихаина апериодический, то неравенство строгое. Когда есть периодичность периода k, есть k собственных значений на единичной окружности у k корней единицы. Если унихаин эргодичен, то Pm сходится асимптотически eπ∗ m→∞. Ошибка переходит в 0, по крайней мере, так же быстро, mq 'λ s m, где λ s - собственное значение второй наибольшей величины, а q - кратность λ s.
Скорость сходимости к зависит от второго по величине модуля собственного значения (SLEM) |. Скорость может быть выражена в терминах спектрального промежутка, который λ SLEM |. Большие промежутки обеспечивают более быструю сходимость. Время смешения является характерным временем для отклонения от равновесия в общем расстоянии изменения. Поскольку сходимость экспоненциальна, время смешения для распада на коэффициент e1 равно
1log 'λ SLEM |.
Учитывая теоремы сходимости, время смешения следует рассматривать в контексте эргодических унихин.
Связанные теоремы в теории неотрицательных, неприводимых матриц дают удобные характеристики двух решающих свойств для равномерной сходимости: редуктивности и эргодичности. Предположим, что Z - индикатор или нулевой шаблон P, то есть матрица с единицами вместо ненулевых записей в P. Тогда P неприводим тогда и только тогда, когда все записи n − 1 положительны. Теорема Виландта [11] утверждает, что P эргодичен тогда и только тогда, когда все записи Pm положительны n − 1) 2 + 1.
Теорема Перрона - Фробениуса и связанные с ней результаты являются неконструктивными для стационарного распределения. Существует несколько подходов для вычисления уникального ограничивающего распределения эргодической цепи.
Определите время возврата Tii в состояние i как минимальное количество шагов для возврата в состояние i после начала в состоянии I. Также определите среднее время возврата, как ожидаемое значение Tii. Затем, π∗=[1/τ11⋯1/τnn]. Этот результат имеет много интуитивного Среднее время смешивания может быть оценено методом моделирования Монте-Карло. Однако накладные расходы на моделирование и трудности оценки сходимости делают моделирование Монте-Карло нецелесообразным в качестве общего метода.
Поскольку Pm приближается к матрице со всеми строками, равными как , любая строка «высокой степени» P аппроксимирует δ *. Хотя этот метод является простым, он включает в себя выбор допуска сходимости и соответствующего большого m для каждого P. В общем, сложности анализа времени смешения также делают это вычисление нецелесообразным.
Линейная система может быть дополнена ограничением в виде , где 1n-by-n - матрица n-by-n единиц. С помощью ограничения эта система становится
) = 1n.
Система может быть эффективно решена с помощью оператора обратной косой черты MATLAB и является численно стабильной, потому что эргодические P не могут иметь единицы по главной диагонали (в противном случае P может быть уменьшен). Этот метод рекомендуется в [5].
Поскольку является уникальным левым собственным вектором, связанным с собственным значением Перрона-Фробениуса для P, сортировка собственных значений и соответствующих собственных векторов идентифицирует . Поскольку ограничения не является частью задачи собственного значения, требует нормализации. Этот метод использует надежные цифры MATLAB eigs и является подходом, реализованным asymptotics объектная функция dtmc объект.
Для любой цепи Маркова анализ конечных стадий может предполагать ее асимптотические свойства и скорость смешивания. Анализ конечных шагов включает в себя вычисление этих величин:
Вероятность попадания hiA - вероятность любое состояние в подмножестве состояний A (цель), начиная с состояния i в цепочке. Категорически, ударные вероятности показывают, какие состояния достижимы из других государств; hiA > 0 означает, что целевой объект A доступен из состояния i. Если hiA = 0, целевой объект A недоступен из состояния i, что означает состояние i является удаленным для целевого объекта. Если A образует повторяющийся класс, hiA - вероятность поглощения.
Ожидаемое время первого удара kiA является длительным средним количеством временных шагов, необходимых для достижения A в первый раз, начиная с состояния i. kiA = ∞ означает одну из следующих альтернатив:
Начальное состояние i является удаленным для цели A.
Начальное состояние i является удаленно достижимым для цели А; то есть > 0 и > 0, где B является повторяющимся классом, не содержащим никаких состояний в A.
Если A образует повторяющийся класс, является ожидаемым временем поглощения.
Вектор вероятностей попадания или ожидаемых времен первого попадания для цели, начиная с каждого состояния в цепи Маркова, предполагает скорость смешения цепи.
[1] Диболд, Ф.Х. и Г.Д. Рудебуш. Бизнес-циклы: продолжительность, динамика и прогнозирование. Принстон, Нью-Джерси: Princeton University Press, 1999.
[2] Галлагер, Р. Г. Стохастические процессы: теория для применения. Кембридж, Великобритания: Cambridge University Press, 2013.
[3] Gilks, W. R., С. Ричардсон и Д.Дж. Спиджелхэлтер. Марковская цепь Монте-Карло на практике. Бока Ратон: Чепмен энд Холл/КПР, 1996.
[4] Хаггстрем, О. Конечный Марков Цепочки и алгоритмические приложения. Кембридж, Великобритания: Cambridge University Press, 2002.
[5] Гамильтон, Джеймс Д. Анализ временных рядов. Принстон, Нью-Джерси: Princeton University Press, 1994.
[6] Рог, R. и К. Р. Джонсон. Матричный анализ. Кембридж, Великобритания: Cambridge University Press, 1985.
[7] Джарвис, Дж. П. и Д. Р. Шиер. «Граф-теоретический анализ конечных цепей Маркова». В прикладном математическом моделировании: многопрофильный подход. Бока Ратон: CRC Press, 2000.
[8] Маддала, Г. С. и И. М. Ким. Корни единиц, коинтеграция и структурные изменения. Кембридж, Великобритания: Cambridge University Press, 1998.
[9] Монтгомери, Дж. Математические модели социальных систем. Неопубликованная рукопись. Кафедра социологии, Университет Висконсина-Мэдисона, 2016.
[10] Норрис, J. R. Markov Chains. Кембридж, Великобритания: Cambridge University Press, 1997.
[11] Виландт, Х. Темы в аналитической теории матриц. Заметки к лекциям, подготовленные Р. Майером. Факультет математики, Висконсинский университет-Мэдисон, 1967 год.
asymptotics | classify | eigplot | eigs | graphplot | isergodic | isreducible | lazy | mcmix