Цепь Маркова

Диаграмма, представляющая марковский процесс с двумя состояниями, с состояниями, обозначенными E и A. Каждое число представляет вероятность перехода марковского процесса из одного состояния в другое состояние, направление которого указано стрелкой. Например, если марковский процесс находится в состоянии A, то вероятность, что он перейдет в состояние E, равна 0,4, а вероятность, что он останется в состоянии A, равна 0,6.

Цепь Маркова является вероятностной моделью , описывающей последовательность возможных событий , в которых вероятность каждого события зависит только от состояния достигнутого в предыдущем случае. ^{[1] [2] [3]} счетное последовательность, в которой цепь движется состояние в дискретных временных шагов, дает дискретное времени цепь Маркова (DTMC). Непрерывное время процесс называется непрерывное время цепи Маркова (СТМС). Он назван в честь русского математика Андрея Маркова .

Цепи Маркова имеют множество приложений в качестве статистических моделей реальных процессов ^{[1] [4] [5] [6],} таких как изучение систем круиз-контроля в транспортных средствах , очередях или очередях клиентов, прибывающих в аэропорт, обменных курсах валют и динамика поголовья животных. ^[7]

Марковские процессы являются основой общих методов стохастического моделирования, известных как цепь Маркова Монте-Карло , которые используются для моделирования выборки из сложных распределений вероятностей и нашли применение в байесовской статистике , термодинамике , статистической механике , физике , химии , экономике , финансах , сигнальной обработка , теория информации и искусственный интеллект . ^{[7] [8] [9]}

Прилагательное Марковский используется для описания чего-то, что связано с марковским процессом. ^{[1] [10]}

Введение [ править ]

Определение [ править ]

Марковский процесс - это случайный процесс, который удовлетворяет марковскому свойству ^[1] (иногда характеризуемому как «отсутствие памяти »). Проще говоря, это процесс, для которого можно делать прогнозы относительно будущих результатов, основываясь исключительно на его текущем состоянии, и, что наиболее важно, такие прогнозы так же хороши, как и те, которые можно было бы сделать, зная полную историю процесса. ^[11] Другими словами, в зависимости от текущего состояния системы ее будущее и прошлое состояния независимы .

Цепь Маркова - это тип марковского процесса, который имеет либо дискретное пространство состояний, либо дискретный набор индексов (часто представляющих время), но точное определение цепи Маркова меняется. ^[12] Например, цепь Маркова принято определять как марковский процесс в дискретном или непрерывном времени со счетным пространством состояний (таким образом, независимо от природы времени), ^{[13] [14] [15] [16 ],} но также принято определять цепь Маркова как имеющую дискретное время либо в счетном, либо в непрерывном пространстве состояний (таким образом, независимо от пространства состояний). ^[12]

Типы цепей Маркова [ править ]

Необходимо указать пространство состояний системы и индекс параметра времени. В следующей таблице представлен обзор различных примеров марковских процессов для разных уровней общности пространства состояний и для дискретного времени и непрерывного времени :

Обратите внимание, что в литературе нет окончательного соглашения об использовании некоторых терминов, обозначающих частные случаи марковских процессов. Обычно термин «цепь Маркова» зарезервирован для процесса с дискретным набором моментов времени, то есть цепи Маркова с дискретным временем (DTMC) , ^{[1] [17],} но некоторые авторы используют термин «процесс Маркова» для обозначения относятся к цепи Маркова с непрерывным временем (CTMC) без явного упоминания. ^{[18] [19] [20]} Кроме того, существуют другие расширения марковских процессов, которые называются таковыми, но не обязательно подпадают ни под одну из этих четырех категорий (см. Модель Маркова). Более того, временной индекс не обязательно должен быть действительным; как и в случае с пространством состояний, есть мыслимые процессы, которые перемещаются по индексным наборам с другими математическими конструкциями. Обратите внимание, что общая цепь Маркова с непрерывным временем в пространстве состояний является общей до такой степени, что в ней нет обозначенного термина.

Хотя параметр времени обычно дискретен, пространство состояний цепи Маркова не имеет каких-либо общепринятых ограничений: термин может относиться к процессу в произвольном пространстве состояний. ^[21] Однако во многих приложениях цепей Маркова используются конечные или счетно бесконечные пространства состояний, которые имеют более простой статистический анализ. Помимо параметров временного индекса и пространства состояний, существует множество других вариаций, расширений и обобщений (см. Варианты ). Для простоты большая часть этой статьи сосредоточена на дискретном времени и дискретном пространстве состояний, если не указано иное.

Переходы [ править ]

Изменения состояния системы называются переходами. ^[1] Вероятности, связанные с различными изменениями состояния, называются вероятностями перехода. Процесс характеризуется пространством состояний, матрицей переходов, описывающей вероятности конкретных переходов, и начальным состоянием (или начальным распределением) в пространстве состояний. По соглашению мы предполагаем, что все возможные состояния и переходы были включены в определение процесса, поэтому всегда есть следующее состояние, и процесс не завершается.

Случайный процесс с дискретным временем включает систему, которая находится в определенном состоянии на каждом шаге, причем состояние меняется случайным образом между шагами. ^[1] Шаги часто называют моментами времени, но они также могут относиться к физическому расстоянию или любому другому дискретному измерению. Формально шаги представляют собой целые или натуральные числа , а случайный процесс - это их отображение на состояния. ^[22] Марковское свойство утверждает, что условное распределение вероятностей для системы на следующем шаге (и фактически на всех будущих шагах) зависит только от текущего состояния системы, а не дополнительно от состояния системы на предыдущих шагах. .

Поскольку система изменяется случайным образом, обычно невозможно с уверенностью предсказать состояние цепи Маркова в данной точке в будущем. ^[22] Однако статистические свойства системы в будущем можно предсказать. ^[22] Во многих приложениях важны именно эти статистические свойства.

История [ править ]

Марков изучал марковские процессы в начале 20 - го века, опубликовал свою первую статью на эту тему в 1906 году ^{[23] [24] [25] [26]} марковские процессы в непрерывное время были обнаружены задолго до того, Андрей Марков работы «s в начале 20 - го века ^[1] в виде пуассоновского процесса . ^{[27] [28] [29]} Марков интересовался расширением независимых случайных последовательностей, мотивированным разногласием с Павлом Некрасовым, который утверждал, что независимость необходима для выполнения слабого закона больших чисел . ^{[1] [30]}В своей первой статье о цепях Маркова, опубликованной в 1906 году, Марков показал, что при определенных условиях средние результаты цепи Маркова будут сходиться к фиксированному вектору значений, таким образом доказывая слабый закон больших чисел без предположения независимости ^{[1]. [24] [25] [26],} которые обычно рассматривались как требование соблюдения таких математических законов. ^[26] Марков позже использовал цепи Маркова, чтобы изучить распределение гласных в « Евгении Онегине» , написанном Александром Пушкиным , и доказал центральную предельную теорему для таких цепей. ^{[1] [24]}

В 1912 году Анри Пуанкаре изучал цепи Маркова на конечных группах с целью изучения перетасовки карт. Другие ранние применения цепей Маркова включают модель диффузии, введенную Полом и Татьяной Эренфест в 1907 году, и процесс ветвления, введенный Фрэнсисом Гальтоном и Генри Уильямом Ватсоном в 1873 году, предшествующий работе Маркова. ^{[24] [25]} После работы Гальтона и Ватсона позже выяснилось, что их процесс ветвления был независимо открыт и изучен примерно тремя десятилетиями ранее Ирене-Жюль Бьенайме . ^[31] Начиная с 1928 года, Морис Фрешезаинтересовался цепями Маркова, в результате чего в 1938 году он опубликовал подробное исследование цепей Маркова. ^{[24] [32]}

Андрей Колмогоров в своей статье 1931 года развил большую часть ранней теории марковских процессов с непрерывным временем. ^{[33] [34]} Колмогоров был частично вдохновлен работой Луи Башелье 1900 года о колебаниях фондового рынка, а также работой Норберта Винера над моделью броуновского движения Эйнштейна. ^{[33] [35]} Он представил и изучил конкретный набор марковских процессов, известных как процессы диффузии, где он вывел набор дифференциальных уравнений, описывающих процессы. ^{[33] [36]} Независимо от работ Колмогорова, Сидней Чепмен вывел в статье 1928 года уравнение, которое теперь называется уравнением Чепмена – Колмогорова., менее математически строго, чем Колмогоров, при изучении броуновского движения. ^[37] Дифференциальные уравнения теперь называются уравнениями Колмогорова ^[38] или уравнениями Колмогорова – Чепмена. ^[39] Среди других математиков, внесших значительный вклад в основы марковских процессов, - Уильям Феллер , начиная с 1930-х годов, а затем Юджин Дынкин , начиная с 1950-х годов. ^[34]

Примеры [ править ]

Случайные блуждания, основанные на целых числах, и проблема разорения игрока - примеры марковских процессов. ^{[40] [41]} Некоторые вариации этих процессов изучались сотни лет назад в контексте независимых переменных. ^{[42] [43] [44]} Два важных примеры процессов Маркова являются винеровский процесс , известный также как броуновское движение процесса, и пуассоновский процесс , ^[27] , которые считаются наиболее важных и центральных стохастических процессов в теории случайные процессы. ^{[45] [46] [47]}Эти два процесса являются марковскими процессами в непрерывном времени, в то время как случайные блуждания целых чисел и проблема разорения игрока являются примерами марковских процессов в дискретном времени. ^{[40] [41]}

Известная цепь Маркова - это так называемая «прогулка пьяницы», случайное блуждание по числовой прямой, где на каждом шаге позиция может меняться на +1 или -1 с равной вероятностью. Из любой позиции возможны два перехода к следующему или предыдущему целому числу. Вероятности перехода зависят только от текущей позиции, а не от того, каким образом она была достигнута. Например, вероятности перехода от 5 к 4 и от 5 к 6 равны 0,5, а все другие вероятности перехода от 5 равны 0. Эти вероятности не зависят от того, была ли система ранее в 4 или 6.

Другой пример - пищевые привычки существа, которое ест только виноград, сыр или салат и чьи пищевые привычки соответствуют следующим правилам:

• Кушает ровно раз в сутки.
• Если сегодня он ел сыр, завтра он с равной вероятностью съест салат или виноград.
• Если он ел виноград сегодня, завтра он будет есть виноград с вероятностью 1/10, сыр с вероятностью 4/10 и салат с вероятностью 5/10.
• Если он ел салат сегодня, завтра он будет есть виноград с вероятностью 4/10 или сыр с вероятностью 6/10. Завтра он больше не будет есть салат.

Привычки этого существа в еде можно смоделировать с помощью цепи Маркова, поскольку его выбор завтра зависит исключительно от того, что он ел сегодня, а не от того, что он ел вчера или в другое время в прошлом. Одно статистическое свойство, которое можно вычислить, - это ожидаемый процент за долгий период дней, когда существо будет есть виноград.

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

Немарковский пример [ править ]

Предположим, что есть кошелек для монет, содержащий пять четвертей (каждая по 25 центов), пять десятицентовиков (каждая по 10 центов) и пять пятак (каждая по 5 центов), и одна за другой монеты случайным образом извлекаются из кошелька и поставить на стол. Если представляет собой суммарную величину монет , установленных на столе после того, как п - дро, с , то последовательность является не марковским процессом.${\displaystyle X_{n}}$${\displaystyle X_{0}=0}$${\displaystyle \{X_{n}:n\in \mathbb {N} \}}$

Чтобы понять, почему это так, предположим, что в первых шести розыгрышах разыгрываются все пять пятак и четверть. Итак . Если мы знаем не только , но и более ранние значения, то мы можем определить, какие монеты были вытянуты, и мы знаем, что следующая монета не будет никелем; так что мы можем определить это с вероятностью 1. Но если мы не знаем более ранние значения, то, основываясь только на этом значении, мы можем предположить, что мы вытащили четыре цента и два цента, и в этом случае, безусловно, можно было бы взять еще один цент. следующий. Таким образом, на наши догадки влияет наше знание ценностей до .${\displaystyle X_{6}=\$0.50}$${\displaystyle X_{6}}$${\displaystyle X_{7}\geq \$0.60}$${\displaystyle X_{6}}$${\displaystyle X_{7}}$${\displaystyle X_{6}}$

Однако можно смоделировать этот сценарий как марковский процесс. Вместо определения , чтобы представить общую стоимость монет на столе, мы могли бы определить , чтобы представить количество различных типов монет на столе. Например, можно определить состояние, в котором на столе лежит одна четверть, ноль десятицентовиков и пять пятак после 6 розыгрышей по одному. Эта новая модель будет представлена ​​216 возможными состояниями (то есть состояниями 6x6x6, так как каждый из трех типов монет может иметь от нуля до пяти монет на столе к концу 6 розыгрышей). Предположим, что первый розыгрыш приводит к состоянию . Вероятность достижения сейчас зависит от ; например, государство${\displaystyle X_{n}}$${\displaystyle X_{n}}$${\displaystyle X_{6}=1,0,5}$${\displaystyle X_{1}=0,1,0}$${\displaystyle X_{2}}$${\displaystyle X_{1}}$${\displaystyle X_{2}=1,0,1}$это невозможно. После второго розыгрыша третий розыгрыш зависит от того, какие монеты были разыграны на данный момент, но больше не только от монет, которые были разыграны для первого состояния (поскольку с тех пор в сценарий была добавлена ​​вероятностно важная информация). Таким образом, вероятность состояния зависит исключительно от результатов состояния.${\displaystyle X_{n}=i,j,k}$${\displaystyle X_{n-1}=\ell ,m,p}$

Формальное определение [ править ]

Цепь Маркова с дискретным временем [ править ]

Марковская цепь с дискретным временем - это последовательность случайных величин X ₁ , X ₂ , X ₃ , ... со свойством Маркова , а именно, что вероятность перехода в следующее состояние зависит только от текущего состояния, а не от предыдущего. состояния:

${\displaystyle \Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),}$если обе условные вероятности хорошо определены, то есть если${\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}$

Возможные значения X _i образуют счетное множество S, называемое пространством состояний цепочки.

Варианты [ править ]

• Однородные по времени цепи Маркова - это процессы, в которых

${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}$

для всех п . Вероятность перехода не зависит от n .

• Стационарные цепи Маркова - это процессы, в которых

${\displaystyle \Pr(X_{0}=x_{0},X_{1}=x_{1},\ldots ,X_{k}=x_{k})=\Pr(X_{n}=x_{0},X_{n+1}=x_{1},\ldots ,X_{n+k}=x_{k})}$

для всех n и k . Каждую стационарную цепь можно доказать однородностью по времени с помощью правила Байеса.

Необходимым и достаточным условием стационарности однородной по времени цепи Маркова является то, что распределение является стационарным распределением цепи Маркова.${\displaystyle X_{0}}$

• Цепь Маркова с памятью (или цепь Маркова порядка m )

где m конечно, - процесс, удовлетворяющий

${\displaystyle {\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}$

Другими словами, будущее состояние зависит от прошлых m состояний. Можно построить цепочку из которых имеет «классическое» марковское свойство, взяв в качестве пространства состояний упорядоченных м -грамм из X значений, то есть. .${\displaystyle (Y_{n})}$${\displaystyle (X_{n})}$${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$

Цепь Маркова с непрерывным временем [ править ]

Марковская цепь с непрерывным временем ( X _t ) _{t  ≥ 0} определяется конечным или счетным пространством состояний S , матрицей скорости перехода Q с размерами, равными размерности пространства состояний, и начального распределения вероятностей, определенного в пространстве состояний. Для i  ≠  j элементы q _ij неотрицательны и описывают скорость переходов процесса из состояния i в состояние j . Элементы q _ii выбираются так, чтобы каждая строка матрицы скорости перехода была равна нулю, а суммы строк матрицы вероятности перехода в (дискретной) цепи Маркова были равны единице.

Есть три эквивалентных определения процесса. ^[48]

Бесконечно малое определение [ править ]

Пусть будет случайной величиной, описывающей состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . Тогда, зная , не зависит от предыдущих значений , и при h → 0 для всех j и всех t ,${\displaystyle X_{t}}$${\displaystyle X_{t}=i}$${\displaystyle X_{t+h}=j}$${\displaystyle \left(X_{s}:s<t\right)}$

${\displaystyle \Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h)}$,

где - дельта Кронекера , используя обозначение small-o . Можно рассматривать как измерения , как быстро переход от I к J происходит.${\displaystyle \delta _{ij}}$${\displaystyle q_{ij}}$

Цепочка прыжков / определение времени удержания [ править ]

Задайте цепь Маркова Y _n с дискретным временем для описания n- го скачка процесса и переменные S ₁ , S ₂ , S ₃ , ... для описания времени удержания в каждом из состояний, где S _i следует экспоненциальному распределению со скоростью параметр - q _{Y i Y i} .

Определение вероятности перехода [ править ]

Для любого значения n = 0, 1, 2, 3, ... и времен, проиндексированных до этого значения n : t ₀ , t ₁ , t ₂ , ... и всех состояний, записанных в эти моменты времени i ₀ , i ₁ , i ₂ , i ₃ , ... выполняется

${\displaystyle \Pr(X_{t_{n+1}}=i_{n+1}\mid X_{t_{0}}=i_{0},X_{t_{1}}=i_{1},\ldots ,X_{t_{n}}=i_{n})=p_{i_{n}i_{n+1}}(t_{n+1}-t_{n})}$

где p _ij - решение прямого уравнения ( дифференциального уравнения первого порядка )

${\displaystyle P'(t)=P(t)Q}$

с начальным условием P (0) - единичная матрица .

Конечное пространство состояний [ править ]

Если пространство состояний конечное распределение вероятностей перехода может быть представлена в виде матрицы , называется матрица перехода, с ( я , J ) -й элемент из Р , равных

${\displaystyle p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i).}$

Поскольку каждая строка P суммируется с одним и всеми элементами неотрицательна, P является правой стохастической матрицей .

Отношение стационарного распределения к собственным векторам и симплексам [ править ]

Стационарное распределение π - это вектор (строка), элементы которого неотрицательны и в сумме равны 1, не изменяется при действии на него матрицы перехода P и, таким образом, определяется как

${\displaystyle \pi \mathbf {P} =\pi .}$

Сравнивая это определение с определением собственного вектора, мы видим, что эти два понятия связаны и что

${\displaystyle \pi ={\frac {e}{\sum _{i}{e_{i}}}}}$

является нормированным ( ) кратным левого собственного вектора e матрицы перехода P с собственным значением 1. Если имеется более одного единичного собственного вектора, то взвешенная сумма соответствующих стационарных состояний также является стационарным состоянием. Но для цепи Маркова обычно больше интересует стационарное состояние, которое является пределом последовательности распределений для некоторого начального распределения.${\displaystyle \textstyle \sum _{i}\pi _{i}=1}$

Значения стационарного распределения связаны с пространством состояний P, и его собственные векторы сохраняют свои относительные пропорции. Поскольку компоненты π положительны и ограничение, что их сумма равна единице, можно переписать, поскольку мы видим, что скалярное произведение π с вектором, все компоненты которого равны 1, равно единице и что π лежит на симплексе .${\displaystyle \textstyle \pi _{i}}$${\displaystyle \textstyle \sum _{i}1\cdot \pi _{i}=1}$

Однородная по времени цепь Маркова с конечным пространством состояний [ править ]

Этот раздел включает список ссылок , связанных материалов для чтения или внешних ссылок , но его источники остаются неясными, поскольку в нем отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить этот раздел, добавив более точные цитаты. ( Февраль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Если цепь Маркова однородна по времени, то матрица перехода P остается той же самой после каждого шага, поэтому вероятность перехода k- шага может быть вычислена как k-я степень матрицы перехода P ^k .

Если цепь Маркова неприводима и апериодична, то существует единственное стационарное распределение π . ^[49] Кроме того, в этом случае P ^k сходится к матрице первого ранга, в которой каждая строка является стационарным распределением π :

${\displaystyle \lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\mathbf {1} \pi }$

где 1 - вектор-столбец, все элементы которого равны 1. Это утверждается теоремой Перрона – Фробениуса . Если каким-либо образом будет найдено, то стационарное распределение рассматриваемой цепи Маркова может быть легко определено для любого начального распределения, как будет объяснено ниже.${\displaystyle \scriptstyle \lim _{k\to \infty }\mathbf {P} ^{k}}$

Для некоторых стохастических матриц P предел не существует, в то время как стационарное распределение существует, как показано в этом примере:${\displaystyle \scriptstyle \lim \limits _{k\to \infty }\mathbf {P} ^{k}}$

${\displaystyle \mathbf {P} ={\begin{pmatrix}0&1\\1&0\end{pmatrix}}\qquad \mathbf {P} ^{2k}=I\qquad \mathbf {P} ^{2k+1}=\mathbf {P} }$

${\displaystyle {\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}{\begin{pmatrix}0&1\\1&0\end{pmatrix}}={\begin{pmatrix}{\frac {1}{2}}&{\frac {1}{2}}\end{pmatrix}}}$

(Этот пример иллюстрирует периодическую цепь Маркова.)

Поскольку необходимо учитывать ряд различных особых случаев, процесс определения этого предела, если он существует, может оказаться длительной задачей. Однако есть много методов, которые могут помочь найти этот предел. Пусть P - матрица размера n × n , и определим${\displaystyle \scriptstyle \mathbf {Q} =\lim \limits _{k\to \infty }\mathbf {P} ^{k}.}$

Это всегда правда, что

${\displaystyle \mathbf {QP} =\mathbf {Q} .}$

Вычитание Q с обеих сторон и факторинг затем дает

${\displaystyle \mathbf {Q} (\mathbf {P} -\mathbf {I} _{n})=\mathbf {0} _{n,n},}$

где I _n - единичная матрица размера n , а 0 _{n , n} - нулевая матрица размера n × n . Умножение стохастических матриц всегда дает другую стохастическую матрицу, поэтому Q должна быть стохастической матрицей (см. Определение выше). Иногда достаточно использовать матричное уравнение выше , и тот факт , что Q представляет собой стохастическая матрица решить для Q . Включая тот факт, что сумма каждой строки в P равна 1, существует n + 1 уравнений для определенияn неизвестных, поэтому с вычислительной точки зрения проще, если, с одной стороны, выбрать одну строку в Q и заменить каждый из ее элементов на один, а с другой - подставить соответствующий элемент (тот, что находится в том же столбце) в векторе 0 , и последующие левые умножают этот последний вектор инверсии преобразованной бывшей матрицы найти Q .

Вот один из способов сделать это: сначала определите функцию f ( A ), чтобы вернуть матрицу A, в которой крайний правый столбец заменен на все единицы. Если [ f ( P - I _n )] ⁻¹ существует, то ^{[50] [49]}

${\displaystyle \mathbf {Q} =f(\mathbf {0} _{n,n})[f(\mathbf {P} -\mathbf {I} _{n})]^{-1}.}$

Объясните: исходное матричное уравнение эквивалентно системе линейных уравнений размера n × n от переменных n × n. И есть еще n линейных уравнений из-за того, что Q - это правая стохастическая матрица , каждая строка которой в сумме равна 1. Таким образом, для решения n × n необходимы любые независимые линейные уравнения n × n из (n × n + n) уравнений. n переменных. В этом примере n уравнений из «Q, умноженного на крайний правый столбец (P-In)» были заменены n стохастическими уравнениями.

Следует отметить, что если P имеет элемент P _{i , i} на своей главной диагонали, равный 1, а i- я строка или столбец в противном случае заполнены нулями, то эта строка или столбец останется неизменным во всех последующих мощности P ^k . Следовательно, я - й строки или столбца из Q будет иметь 1 и 0 в том же позиции , как и в P .

Скорость сходимости к стационарному распределению [ править ]

Этот раздел включает список ссылок , связанных материалов для чтения или внешних ссылок , но его источники остаются неясными, поскольку в нем отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить этот раздел, добавив более точные цитаты. ( Февраль 2012 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Как отмечалось ранее, из уравнения (если существует) стационарное (или стационарное состояние) распределение π является левым собственным вектором строки стохастической матрицы Р . Затем, предполагая, что P диагонализуем, или, что то же самое, что P имеет n линейно независимых собственных векторов, скорость сходимости определяется следующим образом. (Для недиагонализуемого, то есть дефектные матрицы , то можно начать с нормальной формой Жордана из P и приступить к немного более вовлеченному набору аргументов в аналогичном образе. ^[51]${\displaystyle {\boldsymbol {\pi }}={\boldsymbol {\pi }}\mathbf {P} ,}$

Пусть U - матрица собственных векторов (каждый нормирован на норму L2, равную 1), где каждый столбец является левым собственным вектором P, и пусть Σ - диагональная матрица левых собственных значений P , то есть Σ = diag ( λ ₁ , λ ₂ , λ ₃ , ..., λ _n ). Тогда по собственному разложению

${\displaystyle \mathbf {P} =\mathbf {U\Sigma U} ^{-1}.}$

Пусть собственные значения пронумерованы так, что:

${\displaystyle 1=|\lambda _{1}|>|\lambda _{2}|\geqslant |\lambda _{3}|\geqslant \cdots \geqslant |\lambda _{n}|.}$

Поскольку P является стохастической матрицей-строкой, ее наибольшее левое собственное значение равно 1. Если существует уникальное стационарное распределение, то наибольшее собственное значение и соответствующий собственный вектор также уникальны (потому что нет другого π, которое решает уравнение стационарного распределения, приведенное выше). Пусть u _i будет i -м столбцом матрицы U , то есть u _i будет левым собственным вектором P, соответствующим λ _i . Также пусть x будет вектор-строкой длиной n, который представляет допустимое распределение вероятностей; поскольку собственные векторы u _i охватывают${\displaystyle \mathbb {R} ^{n},}$ мы можем написать

${\displaystyle \mathbf {x} ^{T}=\sum _{i=1}^{n}a_{i}\mathbf {u} _{i},\qquad a_{i}\in \mathbb {R} .}$

Если мы умножим x на P справа и продолжим эту операцию с результатами, в итоге мы получим стационарное распределение π . Другими словами, π = u _i ← xPP ... P = xP ^k при k → ∞. Это означает

${\displaystyle {\begin{aligned}{\boldsymbol {\pi }}^{(k)}&=\mathbf {x} \left(\mathbf {U\Sigma U} ^{-1}\right)\left(\mathbf {U\Sigma U} ^{-1}\right)\cdots \left(\mathbf {U\Sigma U} ^{-1}\right)\\&=\mathbf {xU\Sigma } ^{k}\mathbf {U} ^{-1}\\&=\left(a_{1}\mathbf {u} _{1}^{T}+a_{2}\mathbf {u} _{2}^{T}+\cdots +a_{n}\mathbf {u} _{n}^{T}\right)\mathbf {U\Sigma } ^{k}\mathbf {U} ^{-1}\\&=a_{1}\lambda _{1}^{k}\mathbf {u} _{1}^{T}+a_{2}\lambda _{2}^{k}\mathbf {u} _{2}^{T}+\cdots +a_{n}\lambda _{n}^{k}\mathbf {u} _{n}^{T}&&u_{i}\bot u_{j}{\text{ for }}i\neq j\\&=\lambda _{1}^{k}\left\{a_{1}\mathbf {u} _{1}^{T}+a_{2}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{2}^{T}+a_{3}\left({\frac {\lambda _{3}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{3}^{T}+\cdots +a_{n}\left({\frac {\lambda _{n}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{n}^{T}\right\}\end{aligned}}}$

Поскольку π = u ₁ , π ^{( k )} приближается к π при k → ∞ со скоростью порядка λ ₂ / λ ₁ экспоненциально. Это следует потому, что, следовательно, λ ₂ / λ ₁ является доминирующим членом. Случайный шум в распределении состояний π также может ускорить эту сходимость к стационарному распределению. ^[52]${\displaystyle |\lambda _{2}|\geqslant \cdots \geqslant |\lambda _{n}|,}$

Общее пространство состояний [ править ]

Цепи Харриса [ править ]

Многие результаты для цепей Маркова с конечным пространством состояний можно обобщить на цепи с несчетным пространством состояний с помощью цепей Харриса . Основная идея состоит в том, чтобы увидеть, есть ли точка в пространстве состояний, в которую цепочка попадает с вероятностью единица. Как правило, это неверно для непрерывного пространства состояний, однако мы можем определить множества A и B вместе с положительным числом ε и вероятностной мерой ρ , так что

${\displaystyle {\begin{cases}{\text{If }}\tau _{A}=\inf\{n\geq 0:X_{n}\in A\},&{\text{ then }}P_{z}(\tau _{A}<\infty )>0{\text{ for all }}z.\\{\text{If }}x\in A{\text{ and }}C\subset B,&{\text{ then }}p(x,C)\geq \varepsilon \rho (C).\end{cases}}}$

Затем мы могли бы свернуть множества во вспомогательную точку α , а рекуррентную цепь Харриса можно было бы модифицировать так, чтобы она содержала α . Наконец, набор цепей Харриса - это удобный уровень общности, который достаточно широк, чтобы содержать большое количество интересных примеров, но достаточно ограничен, чтобы учесть богатую теорию.

Использование цепей Маркова в методах Монте-Карло цепей Маркова охватывает случаи, когда процесс следует непрерывному пространству состояний.

Локально взаимодействующие цепи Маркова [ править ]

Рассмотрение набора цепей Маркова, эволюция которых учитывает состояние других цепей Маркова, связано с понятием локально взаимодействующих цепей Маркова . Это соответствует ситуации, когда пространство состояний имеет (декартову) форму произведения. См. Взаимодействующие системы частиц и стохастические клеточные автоматы (вероятностные клеточные автоматы). См., Например, « Взаимодействие марковских процессов» ^[53] или ^[54].

Свойства [ править ]

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

Состояние я имею период , если есть наибольший общий делитель числа переходов с помощью которых я могу быть достигнут, начиная с I . То есть:${\displaystyle k}$${\displaystyle k}$

${\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}$

Состояние i называется переходным, если, начиная с i , существует ненулевая вероятность того, что цепочка никогда не вернется в i . В противном случае он повторяется. Для повторяющегося состояния i среднее время достижения определяется как:

${\displaystyle M_{i}=E[T_{i}]=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}$

Состояние i является положительно рекуррентным, если оно конечно, и нулевым рекуррентным в противном случае. Периодичность, быстротечность, повторение и положительное и нулевое повторение являются свойствами класса, то есть, если одно состояние имеет свойство, то все состояния в его взаимодействующем классе имеют свойство.${\displaystyle M_{i}}$

Состояние i называется поглощающим, если нет исходящих переходов из состояния.

Эргодичность [ править ]

Состояние i называется эргодическим, если оно апериодическое и положительно рекуррентное. Другими словами, состояние i является эргодическим, если оно рекуррентно, имеет период 1 и конечное среднее время повторения. Если все состояния неприводимой цепи Маркова эргодичны, то цепь называется эргодической. ^{[ сомнительно - обсудить ]}

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

Цепь Маркова с более чем одним состоянием и только одним выходящим переходом для каждого состояния либо не является неприводимой, либо не апериодической, следовательно, не может быть эргодической.

Марковские представления [ править ]

В некоторых случаях очевидно немарковские процессы могут все еще иметь марковские представления, построенные путем расширения концепции «текущего» и «будущего» состояний. Например, пусть X - немарковский процесс. Затем определить процесс Y , таким образом, что каждое состояние Y представляет собой интервал времени состояний X . Математически это принимает форму:

${\displaystyle Y(t)={\big \{}X(s):s\in [a(t),b(t)]\,{\big \}}.}$

Если Y обладает свойством Маркова, то это марковским представление X .

Примером немарковского процесса с марковским представлением является авторегрессионный временной ряд порядка больше единицы. ^[55]

Время попадания [ править ]

Время достижения - это время, начиная с данного набора состояний до тех пор, пока цепочка не перейдет в данное состояние или набор состояний. Распределение такого временного периода имеет распределение фазового типа. Простейшим из таких распределений является одиночный экспоненциально распределенный переход.

Ожидаемое время попадания [ править ]

Для подмножества состояний A  ⊆  S вектор k ^A времени попадания (где элемент представляет ожидаемое значение , начиная с состояния i , когда цепочка входит в одно из состояний набора A ) является минимальным неотрицательным решением ^{[ 56]}${\displaystyle k_{i}^{A}}$

${\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}$

Обратное время [ править ]

Для CTMC X _t обратный во времени процесс определяется как . По лемме Келли этот процесс имеет такое же стационарное распределение, что и прямой процесс.${\displaystyle \scriptstyle {\hat {X}}_{t}=X_{T-t}}$

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

Встроенная цепь Маркова [ править ]

Один из методов нахождения стационарного распределения вероятностей , л , с концентрацией эргодической непрерывного времени марковской цепи, Q , являются первым нахождением его вложенного марковской цепью (ЭМС) . Строго говоря, EMC - это обычная цепь Маркова с дискретным временем, которую иногда называют скачкообразным процессом . Каждый элемент матрицы вероятности одношагового перехода EMC, S , обозначается s _ij и представляет собой условную вероятность перехода из состояния i в состояние j . Эти условные вероятности могут быть найдены

${\displaystyle s_{ij}={\begin{cases}{\frac {q_{ij}}{\sum _{k\neq i}q_{ik}}}&{\text{if }}i\neq j\\0&{\text{otherwise}}.\end{cases}}}$

Отсюда S можно записать как

${\displaystyle S=I-\left(\operatorname {diag} (Q)\right)^{-1}Q}$

где I - единичная матрица, а diag ( Q ) - диагональная матрица, сформированная путем выбора главной диагонали из матрицы Q и установки всех остальных элементов в ноль.

Чтобы найти вектор стационарного распределения вероятностей, мы должны затем найти такой, что${\displaystyle \varphi }$

${\displaystyle \varphi S=\varphi ,}$

с вектор-строкой, так что все элементы в больше 0 и = 1. Отсюда π может быть найдено как${\displaystyle \varphi }$${\displaystyle \varphi }$ ‖ φ ‖ 1 {\displaystyle \|\varphi \|_{1}}

${\displaystyle \pi ={-\varphi (\operatorname {diag} (Q))^{-1} \over \left\|\varphi (\operatorname {diag} (Q))^{-1}\right\|_{1}}.}$

( S может быть периодическим, даже если Q - нет. Как только π найдено, его необходимо нормировать на единичный вектор .)

Другой процесс с дискретным временем, который может быть получен из цепи Маркова с непрерывным временем, - это δ-скелет - цепь Маркова (дискретного времени), образованная наблюдением X ( t ) с интервалами в δ единиц времени. Случайные величины X (0),  X (δ),  X (2δ), ... задают последовательность состояний, которые посещает δ-скелет.

Специальные типы цепей Маркова [ править ]

Марковская модель [ править ]

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

Схема Бернулли [ править ]

Схема Бернулли является частным случаем марковской цепи , где матрица вероятности перехода имеет одинаковые строки, что означает , что следующее состояние даже независимо от текущего состояния (в дополнении к тому , не зависит от прошлых состояний). Схема Бернулли с двумя возможными состояниями известна как процесс Бернулли .

Заметим, однако, что по теореме об изоморфизме Орнштейна любая апериодическая неприводимая цепь Маркова изоморфна схеме Бернулли; ^[57] таким образом, можно также утверждать, что цепи Маркова являются «частным случаем» схем Бернулли. Изоморфизм обычно требует сложного перекодирования. Теорема об изоморфизме даже немного сильнее: она утверждает, что любой стационарный случайный процесс изоморфен схеме Бернулли; цепь Маркова - лишь один из таких примеров.

Подсдвиг конечного типа [ править ]

Когда матрица Маркова заменяется матрицей смежности о наличии конечного графа , полученный сдвиг Термины топологической марковской цепи или subshift конечного типа . ^[57] Марковская матрица, совместимая с матрицей смежности, может затем предоставить меру субсдвига. Многие хаотические динамические системы изоморфны топологическим цепям Маркова; примеры включают Диффеоморфизмы из замкнутых многообразий , то система Пруэ-Туэ- Морзе , то система Чакона , sofic системы , контекстно-свободные системы исистемы блочного кодирования . ^[57]

Приложения [ править ]

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

Физика [ править ]

Марковские системы широко используются в термодинамике и статистической механике всякий раз, когда вероятности используются для представления неизвестных или немоделированных деталей системы, если можно предположить, что динамика инвариантна во времени и что нет необходимости рассматривать соответствующую историю, которая еще не включена в описании состояния. ^{[58] [59]} Например, термодинамическое состояние работает с распределением вероятностей, которое сложно или дорого получить. Следовательно, метод Монте-Карло цепи Маркова может использоваться для случайного извлечения выборок из черного ящика для аппроксимации распределения вероятностей атрибутов по диапазону объектов. ^[59]

Пути в формулировке интегралов по путям квантовой механики являются цепями Маркова. ^[60]

Цепи Маркова используются при моделировании решеточной КХД . ^[61]

Химия [ править ]

${\displaystyle {\ce {{E}+{\underset {Substrate \atop binding}{S<=>E}}{\overset {Catalytic \atop step}{S->E}}+P}}}$

Кинетика Михаэлиса-Ментен . Фермент (E) связывает субстрат (S) и производит продукт (P). Каждая реакция представляет собой переход состояния в цепи Маркова.

Сеть реакций - это химическая система, включающая множество реакций и химических соединений. В простейших стохастических моделях таких сетей система рассматривается как цепь Маркова с непрерывным временем, состояние которой является числом молекул каждого вида, а реакции моделируются как возможные переходы цепи. ^[62] Цепи Маркова и марковские процессы с непрерывным временем полезны в химии, когда физические системы близко аппроксимируют марковское свойство. Например, представьте себе большое число nмолекул в растворе в состоянии A, каждая из которых может подвергнуться химической реакции до состояния B с определенной средней скоростью. Возможно, молекула - это фермент, и состояния относятся к тому, как она складывается. Состояние любого отдельного фермента следует марковской цепи, и поскольку молекулы по существу независимы друг от друга, количество молекул в состоянии A или B за один раз в n раз больше вероятности того, что данная молекула находится в этом состоянии.

Классическую модель активности фермента, кинетику Михаэлиса – Ментен , можно рассматривать как цепь Маркова, где на каждом временном шаге реакция протекает в определенном направлении. Хотя Михаэлис-Ментен довольно прост, с помощью цепей Маркова можно моделировать гораздо более сложные реакционные сети. ^[63]

Алгоритм, основанный на цепи Маркова, также использовался для сосредоточения роста химических веществ in silico на основе фрагментов в направлении желаемого класса соединений, таких как лекарства или натуральные продукты. ^[64] По мере роста молекулы в качестве «текущего» состояния выбирается фрагмент из возникающей молекулы. Он не осознает своего прошлого (то есть не осознает того, что уже связано с ним). Затем он переходит в следующее состояние, когда к нему прикрепляется фрагмент. Вероятности перехода обучаются на базах данных аутентичных классов соединений. ^[65]

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

Точно так же было высказано предположение, что кристаллизация и рост некоторых материалов из эпитаксиальных сверхрешеток оксидов могут быть точно описаны цепями Маркова. ^[66]

Биология [ править ]

Цепи Маркова используются в различных областях биологии. Известные примеры включают:

• Филогенетика и биоинформатика , где большинство моделей эволюции ДНК используют цепи Маркова с непрерывным временем для описания нуклеотида, присутствующего в данном месте в геноме .
• Динамика населения , где цепи Маркова являются, в частности, центральным инструментом теоретического исследования матричных моделей населения .
• Нейробиология , где цепи Маркова использовались, например, для моделирования неокортекса млекопитающих. ^[67]
• Системная биология , например, с моделированием вирусной инфекции отдельных клеток. ^[68]
• Компартментные модели для моделирования вспышек болезней и эпидемий.

Тестирование [ править ]

Несколько теоретиков предложили идею статистического теста цепей Маркова (MCST), метода соединения цепей Маркова для формирования « марковского одеяла », размещения этих цепей в нескольких рекурсивных слоях («вафли») и создания более эффективных наборов тестов - образцов. - в качестве замены исчерпывающего тестирования. MCST также используются во временных сетях на основе состояний; В статье Чилукури и др., Озаглавленной «Сети аргументов в пользу временной неопределенности для объединения доказательств с приложениями для обнаружения и отслеживания объектов» (ScienceDirect), представлены предыстория и тематическое исследование для применения MCST в более широком диапазоне приложений.

Изменчивость солнечного излучения [ править ]

Оценка изменчивости солнечной радиации полезна для применения в солнечной энергии . Изменчивость солнечного излучения в любом месте с течением времени в основном является следствием детерминированной изменчивости пути солнца по небесному куполу и изменчивости облачности. Изменчивость доступного солнечного излучения на поверхности Земли была смоделирована с использованием цепей Маркова ^{[69] [70] [71] [72],} также включая моделирование двух состояний ясности и облачности как двухуровневой цепи Маркова. ^{[73] [74]}

Распознавание речи [ править ]

Скрытые марковские модели являются основой большинства современных систем автоматического распознавания речи .

Информация и информатика [ править ]

Цепи Маркова используются при обработке информации. Знаменитая статья Клода Шеннона 1948 года «Математическая теория коммуникации» , которая в один шаг создала область теории информации , начинается с введения концепции энтропии посредством марковского моделирования английского языка. Такие идеализированные модели могут отражать многие статистические закономерности систем. Даже без точного описания полной структуры системы такие модели сигналов могут сделать возможным очень эффективное сжатие данных с помощью методов энтропийного кодирования , таких как арифметическое кодирование . Они также позволяют эффективно оценивать состояние ираспознавание образов . Цепи Маркова также играют важную роль в обучении с подкреплением .

Цепи Маркова также являются основой для скрытых марковских моделей, которые являются важным инструментом в таких разнообразных областях, как телефонные сети (которые используют алгоритм Витерби для исправления ошибок), распознавание речи и биоинформатика (например, при обнаружении перегруппировок ^[75] ).

В LZMA Lossless алгоритм сжатия данных объединяет цепь Маркова с компрессией Зив-Зив достичь очень высоких коэффициентов сжатия.

Теория массового обслуживания [ править ]

Цепи Маркова являются основой для аналитического рассмотрения очередей ( теория массового обслуживания ). Агнер Краруп Эрланг инициировал эту тему в 1917 году. ^[76] Это делает их критически важными для оптимизации производительности телекоммуникационных сетей, где сообщения часто должны конкурировать за ограниченные ресурсы (такие как пропускная способность). ^[77]

Во многих моделях массового обслуживания используются цепи Маркова с непрерывным временем. Например, очередь M / M / 1 - это CTMC для неотрицательных целых чисел, где восходящие переходы от i к i  + 1 происходят со скоростью λ в соответствии с процессом Пуассона и описывают поступление заданий, тогда как переходы от i к i  - 1 (для i  > 1) происходят со скоростью μ (время обслуживания заданий распределяется экспоненциально) и описывают выполненные услуги (выбытия) из очереди.

Интернет-приложения [ править ]

Диаграмма состояний, представляющая алгоритм PageRank с переходной вероятностью M, или .${\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}}$

PageRank веб - страницы, которые используются в Google определяется цепью Маркова. ^{[78] [79] [80]} Это вероятность оказаться на странице в стационарном распределении следующей цепи Маркова на всех (известных) веб-страницах. Если - количество известных веб-страниц, и на странице есть ссылки на нее, то вероятность перехода будет для всех страниц, на которые есть ссылки, и для всех страниц, на которые нет ссылок . Параметр принят около 0,15. ^[81]${\displaystyle i}$${\displaystyle N}$${\displaystyle i}$${\displaystyle k_{i}}$${\displaystyle {\frac {\alpha }{k_{i}}}+{\frac {1-\alpha }{N}}}$${\displaystyle {\frac {1-\alpha }{N}}}$${\displaystyle \alpha }$

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

Статистика [ править ]

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

Экономика и финансы [ править ]

Цепи Маркова используются в финансах и экономике для моделирования множества различных явлений, включая цены на активы и рыночные обвалы. Первая финансовая модель, в которой использовалась цепь Маркова, была предложена Прасадом и др. в 1974 году. ^{[ сомнительно - обсудить ] [82]} Другой была модель переключения режимов Джеймса Д. Гамильтона (1989), в которой цепь Маркова используется для моделирования переключения между периодами высокого и низкого роста ВВП (или, альтернативно, экономического роста и рецессии). ^[83] Более свежим примером является мультифрактальная модель с марковскими переключениями Лорана Э. Кальве.и Адлай Дж. Фишер, основанный на удобстве более ранних моделей переключения режимов. ^{[84] [85]} Он использует произвольно большую цепь Маркова для управления уровнем волатильности доходности активов.

В динамической макроэкономике широко используются цепи Маркова. Примером может служить использование цепей Маркова для экзогенного моделирования цен на акции (акции) в условиях общего равновесия . ^[86]

Рейтинговые агентства ежегодно составляют таблицы вероятностей перехода для облигаций с разными кредитными рейтингами. ^[87]

Социальные науки [ править ]

Цепи Маркова обычно используются при описании аргументов, зависящих от пути , где текущие структурные конфигурации обусловливают будущие результаты. Примером может служить переформулировка идеи, первоначально принадлежащая Карлу Марксу « Капитал» , связывающая экономическое развитие с подъемом капитализма . В текущих исследованиях обычно используется цепь Маркова для моделирования того, как по достижении страной определенного уровня экономического развития конфигурация структурных факторов, таких как размер среднего класса , соотношение городского и сельского проживания, уровень от политической мобилизации, и т.д., будет генерировать более высокую вероятность перехода от авторитарногок демократическому режиму . ^[88]

Игры [ править ]

Цепи Маркова можно использовать для моделирования многих азартных игр. ^[1] Детские игры « Змеи и лестницы» и « Хи-хо! Вишня-О », например, представлены именно цепями Маркова. На каждом ходу игрок начинает в заданном состоянии (на заданном квадрате) и оттуда имеет фиксированные шансы перейти в определенные другие состояния (квадраты).

Музыка [ править ]

Цепи Маркова используются в алгоритмической музыкальной композиции , особенно в таком программном обеспечении , как Csound , Max и SuperCollider . В цепочке первого порядка состояния системы становятся значениями ноты или высоты тона, и для каждой ноты строится вектор вероятности , завершая матрицу вероятности перехода (см. Ниже). Создан алгоритм для получения значений выходных нот на основе весов матрицы перехода, которые могут быть значениями нот MIDI , частотой ( Гц ) или любой другой желаемой метрикой. ^[89]

Цепь Маркова второго порядка может быть введена с учетом текущего состояния, а также предыдущего состояния, как указано во второй таблице. Цепочки более высокого , n- го порядка имеют тенденцию «группировать» отдельные ноты вместе, иногда «разрываясь» на другие паттерны и последовательности. Эти цепочки более высокого порядка имеют тенденцию генерировать результаты с чувством фразовой структуры, а не с «бесцельным блужданием», порождаемым системой первого порядка. ^[90]

Цепи Маркова могут использоваться структурно, как в «Аналогиках A и B» Ксенакиса ^[91]. Цепи Маркова также используются в системах, которые используют модель Маркова для интерактивной реакции на ввод музыки. ^[92]

Обычно музыкальные системы должны налагать определенные ограничения управления на последовательности конечной длины, которые они генерируют, но ограничения управления несовместимы с марковскими моделями, так как они вызывают дальнодействующие зависимости, которые нарушают марковскую гипотезу ограниченной памяти. Для преодоления этого ограничения был предложен новый подход. ^[93]

Бейсбол [ править ]

Модели цепей Маркова использовались в расширенном анализе бейсбола с 1960 года, хотя их использование все еще редко. Каждый тайм-тайм бейсбольной игры соответствует состоянию цепи Маркова, если учитывать количество бегунов и аутов. Во время любой битвы существует 24 возможных комбинации количества аутов и положения бегунов. Марк Панкин показывает, что модели цепей Маркова можно использовать для оценки прогонов, созданных как для отдельных игроков, так и для команды. ^[94] Он также обсуждает различные виды стратегий и условий игры: как модели цепей Маркова использовались для анализа статистики игровых ситуаций, таких как овсянка и кража базы, а также различия при игре на траве против AstroTurf . ^[95]

Генераторы марковского текста [ править ]

Марковские процессы также можно использовать для генерации текста, который внешне выглядит реальным, на основе образца документа. Марковские процессы используются в различных рекреационных « пародия генератора программного обеспечения» (см диссоциированного пресс , Джефф Харрисон, ^[96] Марк В. Shaney , ^{[97] [98]} и Academias нейтроний ). Существует несколько библиотек для генерации текста с открытым исходным кодом с использованием цепей Маркова, включая The RiTa Toolkit .

Вероятностное прогнозирование [ править ]

Цепи Маркова использовались для прогнозирования в нескольких областях: например, тенденции цен, ^[99] энергия ветра ^[100] и солнечное излучение. ^[101] В моделях прогнозирования цепей Маркова используются различные параметры, от дискретизации временных рядов ^[100] до скрытых моделей Маркова в сочетании с вейвлетами ^[99] и модели распределения смеси цепей Маркова (MCM). ^[101]

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]