Цепь Маркова

Диаграмма, представляющая марковский процесс с двумя состояниями. Числа — это вероятность перехода из одного состояния в другое.

Цепь Маркова или Марковский процесс — это стохастическая модель, описывающая последовательность возможных событий, в которой вероятность каждого события зависит только от состояния, достигнутого в предыдущем событии. Неофициально это можно представить так: «Что произойдет дальше, зависит только от текущего положения дел ». Счетная бесконечная последовательность, в которой цепь меняет состояние с дискретными шагами по времени, дает цепь Маркова с дискретным временем (DTMC). Процесс с непрерывным временем называется цепью Маркова с непрерывным временем (CTMC). Марковские процессы названы в честь русского математика Андрея Маркова .

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

Прилагательные «Марковский» и «Марковский» используются для описания чего-то, что связано с марковским процессом.

Принципы

Российский математик Андрей Марков

Определение

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

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

Виды цепей Маркова

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

	Счетное пространство состояний	Непрерывное или общее пространство состояний
Дискретное время	(дискретное время) цепь Маркова на счетном или конечном пространстве состояний	Цепь Маркова на измеримом пространстве состояний (например, цепь Харриса )
Непрерывное время	Марковский процесс с непрерывным временем или марковский скачкообразный процесс	Любой непрерывный случайный процесс , обладающий марковским свойством (например, винеровский процесс ).

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

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

Переходы

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

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

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

История

Андрей Марков изучал марковские процессы в начале 20 века, опубликовав свою первую статью по этой теме в 1906 году. Марковские процессы в непрерывном времени были открыты задолго до его работ в начале 20 века в виде процесса Пуассона . Марков был заинтересован в изучении расширения независимых случайных последовательностей, мотивированный разногласиями с Павлом Некрасовым , который утверждал, что независимость необходима для слабого закона больших чисел . выполнения В своей первой статье о цепях Маркова, опубликованной в 1906 году, Марков показал, что при определенных условиях средние результаты цепи Маркова будут сходиться к фиксированному вектору значений, тем самым доказав слабый закон больших чисел без предположения независимости. что обычно рассматривалось как требование для соблюдения таких математических законов. Позже Марков использовал цепи Маркова для изучения распределения гласных в «Евгении Онегине» , написанном Александром Пушкиным , и доказал центральную предельную теорему для таких цепей.

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

Андрей Колмогоров в статье 1931 года развил большую часть ранней теории марковских процессов с непрерывным временем. Колмогоров был частично вдохновлен работой Луи Башелье 1900 года о колебаниях фондового рынка, а также работой Норберта Винера над эйнштейновской моделью броуновского движения. Он ввел и изучил особый набор марковских процессов, известный как диффузионные процессы, где вывел набор дифференциальных уравнений, описывающих эти процессы. Независимо от работы Колмогорова, Сидней Чепмен в статье 1928 года вывел уравнение, теперь называемое уравнением Чепмена-Колмогорова , менее математически строгим способом, чем Колмогоров, изучая броуновское движение. Дифференциальные уравнения теперь называются уравнениями Колмогорова. или уравнения Колмогорова–Чепмена. Среди других математиков, которые внесли значительный вклад в основы марковских процессов, - Уильям Феллер , начиная с 1930-х годов, а затем Юджин Дынкин , начиная с 1950-х годов.

Примеры

Основная статья: Примеры цепей Маркова

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

Немарковский пример

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

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

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

Формальное определение

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

Основная статья: Цепь Маркова с дискретным временем

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

$\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}),$ если обе условные вероятности корректно определены, т. е. если $\Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.$

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

Вариации

• Однородные во времени цепи Маркова — это процессы, в которых $$\Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)$$ для всех н . Вероятность перехода не зависит от n .
• Стационарные цепи Маркова – это процессы, в которых $$\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 . По правилу Байеса можно доказать, что каждая стационарная цепь однородна во времени.
  Необходимым и достаточным условием стационарности однородной во времени цепи Маркова является то, что распределение $X_{0}$ является стационарным распределением цепи Маркова.
• Цепь Маркова с памятью (или цепь Маркова порядка m ), где m конечно, — это процесс, удовлетворяющий $${\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 состояний. Можно построить цепочку $(Y_{n})$ от $(X_{n})$ который обладает «классическим» марковским свойством, поскольку в качестве пространства состояний принимается упорядоченное m -кортеж значений X , т.е. $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 выбираются так, чтобы сумма каждой строки матрицы скорости перехода была равна нулю, а суммы строк матрицы вероятностного перехода в (дискретной) цепи Маркова были равны единице.

Существует три эквивалентных определения этого процесса.

Бесконечно малое определение

Цепь Маркова с непрерывным временем характеризуется скоростями перехода, производными по времени вероятностей перехода между состояниями i и j.

Позволять $X_{t}$ быть случайной величиной, описывающей состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . Тогда, зная $X_{t}=i$, $X_{t+h}=j$ не зависит от предыдущих значений $\left(X_{s}:s<t\right)$, и при h → 0 для всех j и для всех t , $$\Pr(X(t+h)=j\mid X(t)=i)=\delta _{ij}+q_{ij}h+o(h),$$где $\delta _{ij}$ — это дельта Кронекера , используя обозначение «маленькое-о» . $q_{ij}$ можно рассматривать как измерение того, насколько быстро происходит переход от i к j .

Определение цепочки прыжков/времени удержания

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

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

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

$\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 — решение прямого уравнения ( дифференциальное уравнение первого порядка )

$P'(t)=P(t)Q$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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 и определим ${\textstyle \mathbf {Q} =\lim _{k\to \infty }\mathbf {P} ^{k}.}$

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

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

Вычитание Q из обеих сторон и факторизация дают

$\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 , в крайнем правом столбце которой заменены все единицы. Если [ ж ( п - я _п )] ⁻¹ существует тогда

$\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 имеет элемент Pi _{i , i} на своей главной диагонали, который равен 1, а - я строка или столбец в противном случае заполнена нулями, то эта строка или столбец останутся неизменными во всех последующих полномочия P ^к . Следовательно, i -я строка или столбец Q будет иметь 1 и 0 в тех же позициях, что и в P .

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

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

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

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

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

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

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

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

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

${\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}^{\mathsf {T}}+a_{2}\mathbf {u} _{2}^{\mathsf {T}}+\cdots +a_{n}\mathbf {u} _{n}^{\mathsf {T}}\right)\mathbf {U\Sigma } ^{k}\mathbf {U} ^{-1}\\&=a_{1}\lambda _{1}^{k}\mathbf {u} _{1}^{\mathsf {T}}+a_{2}\lambda _{2}^{k}\mathbf {u} _{2}^{\mathsf {T}}+\cdots +a_{n}\lambda _{n}^{k}\mathbf {u} _{n}^{\mathsf {T}}&&u_{i}\bot u_{j}{\text{ for }}i\neq j\\&=\lambda _{1}^{k}\left\{a_{1}\mathbf {u} _{1}^{\mathsf {T}}+a_{2}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{2}^{\mathsf {T}}+a_{3}\left({\frac {\lambda _{3}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{3}^{\mathsf {T}}+\cdots +a_{n}\left({\frac {\lambda _{n}}{\lambda _{1}}}\right)^{k}\mathbf {u} _{n}^{\mathsf {T}}\right\}\end{aligned}}$

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

Общее государственное пространство

Основная статья: Цепи Маркова в измеримом пространстве состояний

Цепи Харриса

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

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

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

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

Характеристики

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

Состояние i имеет период k, если k — наибольший общий делитель числа переходов, с помощью которых i можно достичь , начиная с i . То есть:

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

Состояние периодическое, если $k>1$; в противном случае $k=1$ и состояние апериодическое .

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

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

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

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

неприводимость

Поскольку периодичность является свойством класса, если цепь Маркова неприводима, то все ее состояния имеют одинаковый период. В частности, если одно состояние апериодично, то апериодична и вся цепь Маркова.

Если конечная цепь Маркова неприводима, то все состояния положительно рекуррентны и имеют единственное стационарное распределение, определяемое формулой $\pi _{i}=1/E[T_{i}]$.

Эргодичность

Состояние i называется эргодическим, если оно апериодично и положительно рекуррентно. Другими словами, состояние i является эргодическим, если оно рекуррентно, имеет период 1 и имеет конечное среднее время возврата.

Если все состояния неприводимой цепи Маркова эргодичны, то цепь называется эргодической. Эквивалентно, существует некоторое целое число $k$ так, что все записи $M^{k}$ являются положительными.

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

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

Терминология

Некоторые авторы называют любые неприводимые положительные рекуррентные цепи Маркова эргодическими и даже периодическими. Фактически, просто неприводимые цепи Маркова соответствуют эргодическим процессам , определенным в соответствии с эргодической теорией .

Некоторые авторы называют матрицу примитивной тогда и только тогда, когда существует некоторое целое число. $k$ так, что все записи $M^{k}$ являются положительными. Некоторые авторы называют его регулярным .

Индекс примитивности

Индекс примитивности , или экспонента , регулярной матрицы является наименьшим $k$ так, что все записи $M^{k}$ являются положительными. Показатель степени является чисто теоретико-графовым свойством, поскольку он зависит только от того, является ли каждая запись $M$ равен нулю или положителен и, следовательно, может быть найден на ориентированном графе с $\mathrm {sign} (M)$ в качестве матрицы смежности.

Есть несколько комбинаторных результатов об показателе степени, когда состояний конечное число. Позволять $n$ быть числом штатов, тогда

• Экспонента $\leq (n-1)^{2}+1$. Единственный случай, когда это равенство, - это когда график $M$ идет как $1\to 2\to \dots \to n\to 1{\text{ and }}2$.
• Если $M$ имеет $k\geq 1$ диагональные элементы, то его показатель равен $\leq 2n-k-1$.
• Если $\mathrm {sign} (M)$ симметричен, то $M^{2}$ имеет положительные диагональные элементы, что согласно предыдущему утверждению означает, что его показатель равен $\leq 2n-2$.
• (Теорема Дульмаджа-Мендельсона) Показатель степени равен $\leq n+s(n-2)$ где $s$ это обхват графика . Его можно улучшить до $\leq (d+1)+s(d+1-2)$, где $d$ - диаметр графа .

Динамическая система, сохраняющая меру

Если цепь Маркова имеет стационарное распределение, то ее можно преобразовать в динамическую систему, сохраняющую меру : пусть вероятностное пространство равно $\Omega =\Sigma ^{\mathbb {N} }$, где $\Sigma$ представляет собой набор всех состояний цепи Маркова. Пусть сигма-алгебра в вероятностном пространстве порождается цилиндрическими множествами. Пусть вероятностная мера порождается стационарным распределением и переходом цепи Маркова. Позволять $T:\Omega \to \Omega$ быть оператором смены: $T(X_{0},X_{1},\dots )=(X_{1},\dots )$. Аналогично мы можем построить такую ​​динамическую систему с $\Omega =\Sigma ^{\mathbb {Z} }$ вместо.

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

В эргодической теории сохраняющая меру динамическая система называется «эргодической» тогда и только тогда, когда любое измеримое подмножество $S$ такой, что $T^{-1}(S)=S$ подразумевает $S=\emptyset$ или $\Omega$ (до нулевого набора).

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

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

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

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

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

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

Время ударов

Основная статья: Распределение фазового типа

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

Ожидаемое время попадания

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

${\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 обращенный во времени процесс определяется как ${\hat {X}}_{t}=X_{T-t}$. По лемме Келли этот процесс имеет такое же стационарное распределение, как и прямой процесс.

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

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

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

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

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

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

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

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

$\varphi S=\varphi ,$

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

$\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 основных типа моделей, которые обобщают цепи Маркова в зависимости от того, является ли каждое последовательное состояние наблюдаемым или нет, и подлежит ли система корректировке на основе сделанных наблюдений:

	Состояние системы полностью наблюдаемо	Состояние системы частично наблюдаемо
Система автономна	Цепь Маркова	Скрытая модель Маркова
Система контролируется	Марковский процесс принятия решения	Частично наблюдаемый марковский процесс принятия решений

Схема Бернулли

Основная статья: схема Бернулли

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

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

Подсдвиг конечного типа

Основная статья: Подсдвиг конечного типа

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

Приложения

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

Физика

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

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

Химия

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

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

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

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

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

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

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

Биология

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

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

Тестирование

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

Изменчивость солнечного излучения

Оценка изменчивости солнечного излучения полезна для применения в солнечной энергетике . Изменчивость солнечного излучения в любом месте с течением времени в основном является следствием детерминированной изменчивости пути Солнца по небесному куполу и изменчивости облачности. Изменчивость доступного солнечного излучения на поверхности Земли была смоделирована с помощью цепей Маркова. также включая моделирование двух состояний ясности и облачности как цепи Маркова с двумя состояниями.

Распознавание речи

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

Теория информации

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

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

Алгоритм сжатия данных без потерь LZMA сочетает в себе цепи Маркова со сжатием Лемпеля-Зива для достижения очень высокой степени сжатия.

Теория массового обслуживания

Основная статья: Теория массового обслуживания

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

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

Интернет-приложения

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

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

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

Статистика

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

Экономика и финансы

Цепи Маркова используются в финансах и экономике для моделирования множества различных явлений, включая распределение доходов, распределение фирм по размерам, цены на активы и рыночные крахи. Д. Г. Чамперноун построил модель распределения доходов, основанную на цепях Маркова, в 1953 году. Герберт А. Саймон и соавтор Чарльз Бонини использовали модель цепи Маркова, чтобы получить стационарное распределение Юла по размерам фирм. Луи Башелье был первым, кто заметил, что цены на акции движутся случайным образом. Позднее случайное блуждание рассматривалось как свидетельство в пользу гипотезы эффективного рынка , а модели случайного блуждания были популярны в литературе 1960-х годов. Модели бизнес-циклов со сменой режима были популяризированы Джеймсом Д. Гамильтоном (1989), который использовал цепь Маркова для моделирования переключения между периодами высокого и низкого роста ВВП (или, альтернативно, экономического подъема и рецессии). Более свежим примером является с марковским переключением мультифрактальная модель Лорана Э. Кальве и Адлая Дж. Фишера, которая основана на удобстве более ранних моделей переключения режимов. Он использует произвольно большую цепь Маркова для управления уровнем волатильности доходности активов.

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

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

Социальные науки

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

Игры

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

Музыка

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

Матрица 1-го порядка

Примечание	А	C ♯	E ♭
А	0.1	0.6	0.3
C ♯	0.25	0.05	0.7
E ♭	0.7	0.3	0

Матрица 2-го порядка

Примечания	А	Д	Г
АА	0.18	0.6	0.22
ОБЪЯВЛЕНИЕ	0.5	0.5	0
АГ	0.15	0.75	0.1
ДД	0	0	1
И	0.25	0	0.75
генеральный директор	0.9	0.1	0
GG	0.4	0.4	0.2
Джорджия	0.5	0.25	0.25
ГД	1	0	0

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

Цепи Маркова можно использовать структурно, как в Analogique A и B Ксенакиса. Цепи Маркова также используются в системах, которые используют модель Маркова для интерактивного реагирования на музыкальный ввод.

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

Бейсбол

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

Генераторы марковского текста

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

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

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

См. также

• Динамика марковских частиц
• Процесс Гаусса – Маркова
• Метод аппроксимации цепей Маркова
• Геостатистика цепей Маркова
• Время смешивания цепи Маркова
• Теорема о дереве цепи Маркова
• Марковский процесс принятия решения
• Марковский источник информации
• Марковский одометр
• Марковский оператор
• Марковское случайное поле
• Основное уравнение
• Квантовая цепь Маркова
• Полумарковский процесс
• Стохастический клеточный автомат
• Телескопическая цепь Маркова
• Марковская модель переменного порядка

Ссылки

• A. A. Markov (1906) "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete , 2-ya seriya, tom 15, pp. 135–156.
• А. А. Марков (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, связанных в цепочку». перепечатано в Приложении B: Р. Ховард. Динамические вероятностные системы, том 1: Цепи Маркова . Джон Уайли и сыновья.
• Классический текст в переводе: Марков А.А. (2006). «Пример статистического исследования текста «Евгений Онегин» по поводу соединения образцов в цепочки». Наука в контексте . 19 (4). Перевод Линка, Дэвид: 591–600. дои : 10.1017/s0269889706001074 .
• Лео Брейман (1992) [1968] Вероятность . Оригинальное издание опубликовано Аддисон-Уэсли; перепечатано Обществом промышленной и прикладной математики. ISBN   0-89871-296-3 . (См. главу 7)
• Дж. Л. Дуб (1953) Стохастические процессы . Нью-Йорк: Джон Уайли и сыновья ISBN   0-471-52369-0 .
• С. П. Мейн и Р. Л. Твиди (1993) Марковские цепи и стохастическая устойчивость . Лондон: Спрингер-Верлаг ISBN   0-387-19832-6 . онлайн: МЦСС . Появится второе издание, Cambridge University Press, 2009 г.
• Дынкин, Евгений Борисович (1965). Марковские процессы . Основные принципы математических наук. Том I (121). Перевод Фабиуса, Яапа; Гринберг, Вида Лазарус; Майтра, Ашок Прасад; Маджоне, Джандоменико . Берлин: Springer Verlag . дои : 10.1007/978-3-662-00031-1 . ISBN  978-3-662-00033-5 . Название-№. 5104. ; Марковские процессы . Том. II (122). 1965. doi : 10.1007/978-3-662-25360-1 . ISBN  978-3-662-23320-7 . Название-№. 5105. было опубликовано на русском языке под названием » (Примечание. Первоначально это «Марковские процессы Физматгизом в 1963 году и переведено на английский язык при содействии автора.)
• ИП Мейн. Методы управления сложными сетями . Издательство Кембриджского университета, 2007. ISBN   978-0-521-88441-9 . Приложение содержит сокращенную версию книги Meyn & Tweedie. онлайн: CTCN
• Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк, штат Нью-Йорк: John Wiley and Sons, Inc., номер карточного каталога Библиотеки Конгресса 67-25924. ] Обширная и обширная книга, предназначенная для специалистов и написанная как для ученых-теоретиков в области информатики, так и для инженеров-электриков. С подробными объяснениями методов минимизации состояний, автоматов, машин Тьюринга, марковских процессов и неразрешимости. Отличное рассмотрение марковских процессов, стр. 449 и далее. Обсуждаются Z-преобразования и D-преобразования в их контексте.
• Кемени, Джон Г.; Хэзлтон Миркил; Дж. Лори Снелл; Джеральд Л. Томпсон (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Prentice-Hall, Inc. Номер каталога карточек Библиотеки Конгресса 59-12841. Классический текст. см. главу 6. Конечные цепи Маркова, стр. 384 и далее.
• Джон Г. Кемени и Дж. Лори Снелл (1960) Конечные цепи Маркова , компания Д. ван Ностранда ISBN   0-442-04328-7
• Э. Нуммелин. «Общие неприводимые цепи Маркова и неотрицательные операторы». Издательство Кембриджского университета, 1984, 2004. ISBN   0-521-60494-X
• Сенета, Э. Неотрицательные матрицы и цепи Маркова . 2-я ред. изд., 1981, XVI, 288 стр., Серия Springer в мягкой обложке по статистике. (Первоначально опубликовано Allen & Unwin Ltd., Лондон, 1973 г.) ISBN   978-0-387-29765-1
• Кишор С. Триведи , Вероятность и статистика с приложениями надежности, массового обслуживания и информатики , John Wiley & Sons, Inc., Нью-Йорк, 2002. ISBN   0-471-33341-7 .
• К.С. Триведи и Р.А.Шанер, ШАРПЕ в возрасте двадцати двух лет , т. 1, с. 36, нет. 4, стр. 52–57, Обзор оценки производительности ACM SIGMETRICS, 2009 г.
• Р.А. Санер, К.С. Триведи и А. Пулиафито, Анализ производительности и надежности компьютерных систем: подход на основе примеров с использованием программного пакета SHARPE , Kluwer Academic Publishers, 1996. ISBN   0-7923-9650-2 .
• Г. Болх, С. Грейнер, Х. де Меер и К. С. Триведи, Сети массового обслуживания и цепи Маркова , Джон Уайли, 2-е издание, 2006 г. ISBN   978-0-7923-9650-5 .

Внешние ссылки

• «Цепь Маркова» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Глава о цепях Маркова во вводной книге о вероятностях Американского математического общества. Архивировано 22 мая 2008 г. в Wayback Machine.
• Введение в цепи Маркова на YouTube
• Визуальное объяснение цепей Маркова
• Оригинальная статья А. А. Маркова (1913 г.): Пример статистического исследования текста «Евгений Онегин» о соединении образцов в цепочки (перевод с русского)