цепь Маркова

Случайный процесс, независимый от прошлой истории

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

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

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

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

Принципы

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

Определение

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

Цепь Маркова — это тип марковского процесса, который имеет либо дискретное пространство состояний , либо дискретный набор индексов (часто представляющий время), но точное определение цепи Маркова варьируется. ^[6] Например, принято определять цепь Маркова как марковский процесс либо в дискретном, либо в непрерывном времени со счетным пространством состояний (таким образом, независимо от природы времени), ^{[7] [8] [9] [10]} но также принято определять цепь Маркова как имеющий дискретное время либо в счетном, либо в непрерывном пространстве состояний (таким образом, независимо от пространства состояний). ^[6]

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

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

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

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

Переходы

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

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

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

История

Андрей Марков изучал марковские процессы в начале 20 века, опубликовав свою первую статью по этой теме в 1906 году. ^{[16] [17] [18]} Марковские процессы в непрерывном времени были открыты задолго до его работы в начале 20 века в форме процесса Пуассона . ^{[19] [20] [21]} Марков интересовался изучением расширения независимых случайных последовательностей, что было мотивировано несогласием с Павлом Некрасовым , который утверждал, что независимость необходима для выполнения слабого закона больших чисел . ^[22] В своей первой статье о цепях Маркова, опубликованной в 1906 году, Марков показал, что при определенных условиях средние результаты цепи Маркова будут сходиться к фиксированному вектору значений, тем самым доказав слабый закон больших чисел без предположения о независимости, ^{[16] [17] [18]} которое обычно рассматривалось как требование для выполнения таких математических законов. ^[18] Позднее Марков использовал цепи Маркова для изучения распределения гласных в «Евгении Онегине» , написанном Александром Пушкиным , и доказал центральную предельную теорему для таких цепей. ^[16]

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

Андрей Колмогоров в статье 1931 года разработал большую часть ранней теории непрерывных во времени марковских процессов. ^{[25] [26]} Колмогоров был частично вдохновлен работой Луи Башелье 1900 года о колебаниях на фондовом рынке, а также работой Норберта Винера о модели броуновского движения Эйнштейна. ^{[25] [27]} Он ввел и изучил определенный набор марковских процессов, известных как процессы диффузии, где он вывел набор дифференциальных уравнений, описывающих эти процессы. ^{[25] [28]} Независимо от работы Колмогорова, Сидни Чепмен вывел в статье 1928 года уравнение, теперь называемое уравнением Чепмена–Колмогорова , менее математически строгим способом, чем Колмогоров, изучая броуновское движение. ^[29] Дифференциальные уравнения теперь называются уравнениями Колмогорова ^[30] или уравнениями Колмогорова–Чепмена. ^[31] Другие математики, внесшие значительный вклад в основы марковских процессов, включают Уильяма Феллера , начиная с 1930-х годов, а затем, позднее, Евгения Дынкина , начиная с 1950-х годов. ^[26]

Примеры

• Случайные блуждания на основе целых чисел и проблема разорения игрока являются примерами марковских процессов. ^{[32] [33]} Некоторые вариации этих процессов изучались сотни лет назад в контексте независимых переменных. ^{[34] [35]} Два важных примера марковских процессов — это винеровский процесс , также известный как процесс броуновского движения , и пуассоновский процесс , ^[19] которые считаются наиболее важными и центральными стохастическими процессами в теории стохастических процессов. ^{[36] [37] [38]} Эти два процесса являются марковскими процессами в непрерывном времени, в то время как случайные блуждания на основе целых чисел и проблема разорения игрока являются примерами марковских процессов в дискретном времени. ^{[32] [33]}
• Знаменитая цепь Маркова — это так называемая «прогулка пьяницы», случайное блуждание по числовой прямой , где на каждом шаге позиция может измениться на +1 или −1 с равной вероятностью. Из любой позиции возможны два перехода: к следующему или предыдущему целому числу. Вероятности перехода зависят только от текущей позиции, а не от способа, которым она была достигнута. Например, вероятности перехода из 5 в 4 и из 5 в 6 обе равны 0,5, а все остальные вероятности перехода из 5 равны 0. Эти вероятности не зависят от того, находилась ли система ранее в 4 или 6.
• Серия независимых состояний (например, серия подбрасываний монеты) удовлетворяет формальному определению цепи Маркова. Однако теория обычно применяется только тогда, когда распределение вероятностей следующего состояния зависит от текущего.

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

Предположим, что есть кошелек с пятью четвертаками (каждый по 25 центов), пятью десятицентовиками (каждый по 10 центов) и пятью никелями (каждый по 5 центов), и одна за другой монеты случайным образом вынимаются из кошелька и кладутся на стол. Если представляет собой общую стоимость монет, выложенных на стол после n вытягиваний, причем , то последовательность не является марковским процессом. ${\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 последовательных розыгрышей лежит один четвертак, ноль десятицентовиков и пять никелей. Эта новая модель могла бы быть представлена ​​возможными состояниями, где каждое состояние представляет количество монет каждого типа (от 0 до 5), находящихся на столе. (Не все эти состояния достижимы за 6 розыгрышей.) Предположим, что первый розыгрыш приводит к состоянию . Вероятность достижения теперь зависит от ; например, состояние невозможно. После второго розыгрыша третий розыгрыш зависит от того, какие монеты были до сих пор вытащены, но больше не только от монет, которые были вытащены для первого состояния (поскольку с тех пор в сценарий была добавлена ​​вероятностно важная информация). Таким образом, вероятность состояния зависит исключительно от результата состояния . ${\displaystyle X_{n}}$ ${\displaystyle X_{n}}$ ${\displaystyle X_{6}=1,0,5}$ ${\displaystyle 6\times 6\times 6=216}$ ${\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, называемое пространством состояний цепи.

Вариации

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

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

Определение бесконечно малых величин

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

Пусть будет случайной величиной, описывающей состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . Тогда, зная , не зависит от предыдущих значений , и при h → 0 для всех j и для всех t , где — дельта Кронекера , используя обозначение с маленькой буквой «о» . Можно рассматривать как измерение того, насколько быстро происходит переход от i к j . ${\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),}$$ ${\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) — единичная матрица .

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

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

${\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. Если имеется более одного единичного собственного вектора, то взвешенная сумма соответствующих стационарных состояний также является стационарным состоянием. Но для цепи Маркова обычно больше интересуются стационарным состоянием, которое является пределом последовательности распределений для некоторого начального распределения. ${\textstyle \sum _{i}\pi _{i}=1}$

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

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

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

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

${\displaystyle \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}}$

${\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 , и определите ${\textstyle \mathbf {Q} =\lim _{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 с ее самым правым столбцом, замененным на все 1. Если [ f ( P − I _n )] ⁻¹ существует, то ^{[41] [40]}

${\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 уравнений из «Q, умноженное на самый правый столбец (P-In)» были заменены n стохастическими.

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

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

Как было сказано ранее, из уравнения (если оно существует) стационарное (или устойчивое) распределение π является левым собственным вектором стохастической матрицы строк P. Тогда, предполагая, что P диагонализируема или, что эквивалентно, что P имеет n линейно независимых собственных векторов, скорость сходимости определяется следующим образом. (Для недиагонализуемых, то есть дефектных матриц , можно начать с нормальной формы Жордана P и продолжить с немного более сложным набором аргументов аналогичным образом. ^[42] ) ${\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}|\geq |\lambda _{3}|\geq \cdots \geq |\lambda _{n}|.}$

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

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

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

цепи Харриса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Есть несколько комбинаторных результатов об экспоненте, когда есть конечное число состояний. Пусть будет числом состояний, тогда ^[54] ${\displaystyle n}$

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

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

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

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

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

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

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

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

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

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

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

Время удара

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

Ожидаемое время удара

Для подмножества состояний A  ⊆  S вектор k ^A времен попадания (где элемент представляет собой ожидаемое значение , начиная с состояния i , при котором цепь входит в одно из состояний в наборе A ) является минимальным неотрицательным решением ^[58] ${\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 {\hat {X}}_{t}=X_{T-t}}$

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

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

Один из методов нахождения стационарного распределения вероятностей , π , эргодической непрерывной по времени цепи Маркова, Q , заключается в первом нахождении ее вложенной цепи Маркова (EMC) . Строго говоря, 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 }$ ${\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 основных типа моделей, которые обобщают цепи Маркова в зависимости от того, является ли каждое последовательное состояние наблюдаемым или нет, и должна ли система корректироваться на основе сделанных наблюдений:

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

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

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

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

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

Приложения

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

Физика

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

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

Химия

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

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

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

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

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

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

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

Биология

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

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

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

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

Изменчивость солнечной радиации

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

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

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

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

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

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

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

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

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

Многочисленные модели очередей используют цепи Маркова с непрерывным временем. Например, очередь 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 , определяется цепью Маркова. ^{[81] [82] [83]} Это вероятность оказаться на странице в стационарном распределении следующей цепи Маркова на всех (известных) веб-страницах. Если — количество известных веб-страниц, и страница имеет ссылки на нее, то она имеет вероятность перехода для всех страниц, на которые есть ссылки, и для всех страниц, на которые нет ссылок. Параметр принимается равным примерно 0,15. ^[84] ${\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). В последние годы это произвело революцию в практической применимости методов байесовского вывода , позволяя моделировать широкий диапазон апостериорных распределений и находить их параметры численно. ^{[ необходима цитата ]}

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

Цепи Маркова используются в финансах и экономике для моделирования различных явлений, включая распределение доходов, распределение размеров фирм, цены на активы и рыночные крахи. DG Champernowne построил модель цепи Маркова для распределения доходов в 1953 году. ^[85] Герберт А. Саймон и соавтор Чарльз Бонини использовали модель цепи Маркова для получения стационарного распределения Юла размеров фирм. ^[86] Луи Башелье был первым, кто заметил, что цены акций следуют случайному блужданию. ^[87] Случайное блуждание позже рассматривалось как доказательство в пользу гипотезы эффективного рынка , и модели случайного блуждания были популярны в литературе 1960-х годов. ^[88] Модели переключения режимов деловых циклов были популяризированы Джеймсом Д. Гамильтоном (1989), который использовал цепь Маркова для моделирования переходов между периодами высокого и низкого роста ВВП (или, альтернативно, экономическими подъемами и рецессиями). ^[89] Более поздним примером является мультифрактальная модель переключения Маркова Лорана Э. Кальве и Эдлая Дж. Фишера, которая основывается на удобстве более ранних моделей переключения режимов. ^{[90] [91]} Она использует произвольно большую цепь Маркова для управления уровнем волатильности доходности активов.

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

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

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

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

Игры

Цепи Маркова можно использовать для моделирования многих азартных игр. Детские игры Snakes and Ladders и " Hi Ho! Cherry-O ", например, представлены именно цепями Маркова. На каждом ходу игрок начинает в заданном состоянии (на заданной клетке) и оттуда имеет фиксированные шансы перейти в определенные другие состояния (клетки).

Музыка

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

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

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

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

Бейсбол

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

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

Процессы Маркова также могут быть использованы для генерации поверхностно реалистичного текста с использованием образца документа. Процессы Маркова используются в различных развлекательных программах " генераторов пародий " (см. dissociated press , Jeff Harrison, ^[102] Mark V. Shaney , ^{[103] [104]} и Academias Neutronium). Существует несколько библиотек генерации текста с открытым исходным кодом, использующих цепи Маркова.

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

Цепи Маркова использовались для прогнозирования в нескольких областях: например, ценовые тенденции, ^[105] ветроэнергетика, ^[106] стохастический терроризм , ^{[107] [108]} и солнечное излучение . ^[109] Модели прогнозирования на основе цепей Маркова используют различные настройки: от дискретизации временных рядов, ^[106] до скрытых моделей Маркова в сочетании с вейвлетами, ^[105] и модель распределения смеси цепей Маркова (MCM). ^[109]

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

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

Примечания

1. Sean Meyn; Richard L. Tweedie (2 апреля 2009 г.). Цепи Маркова и стохастическая устойчивость. Cambridge University Press. стр. 3. ISBN 978-0-521-73182-9.
2. Реувен Ю. Рубинштейн; Дирк П. Крозе (20 сентября 2011 г.). Моделирование и метод Монте-Карло. Джон Уайли и сыновья. п. 225. ИСБН 978-1-118-21052-9.
3. Дани Геймерман; Хедиберт Ф. Лопес (10 мая 2006 г.). Марковская цепь Монте-Карло: стохастическое моделирование для байесовского вывода, второе издание. CRC Press. ISBN 978-1-58488-587-0.
4. "Марковский" . Оксфордский словарь английского языка (Электронная правка). Oxford University Press . (Требуется подписка или членство в участвующем учреждении.)
5. Øksendal, BK (Bernt Karsten) (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Springer. ISBN 3540047581. OCLC  52203046.
6. Сорен Асмуссен (15 мая 2003 г.). Прикладная вероятность и очереди. Springer Science & Business Media. п. 7. ISBN 978-0-387-00211-8.
7. Эмануэль Парзен (17 июня 2015 г.). Стохастические процессы. Courier Dover Publications. стр. 188. ISBN 978-0-486-79688-8.
8. Сэмюэл Карлин; Говард Э. Тейлор (2 декабря 2012 г.). Первый курс по стохастическим процессам. Academic Press. стр. 29 и 30. ISBN 978-0-08-057041-9.
9. Джон Ламперти (1977). Стохастические процессы: обзор математической теории. Springer-Verlag. С. 106–121. ISBN 978-3-540-90275-1.
10. Шелдон М. Росс (1996). Стохастические процессы. Wiley. С. 174 и 231. ISBN 978-0-471-12062-9.
11. Эверитт, Б.С. (2002) Кембриджский словарь статистики . CUP. ISBN 0-521-81099-X 
12. Парзен, Э. (1962) Стохастические процессы , Холден-Дэй. ISBN 0-8162-6664-6 (таблица 6.1) 
13. Додж, И. (2003) Оксфордский словарь статистических терминов , OUP. ISBN 0-19-920613-9 (статья для «цепи Маркова») 
14. Додж, Y. Оксфордский словарь статистических терминов , OUP. ISBN 0-19-920613-9 
15. Meyn, S. Sean P. и Richard L. Tweedie. (2009) Цепи Маркова и стохастическая устойчивость . Cambridge University Press. (Предисловие, стр. iii)
16. Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в теорию вероятностей. Американское математическое общество. стр. 464–466. ISBN 978-0-8218-0749-1.
17. Пьер Бремо (9 марта 2013 г.). Цепи Маркова: поля Гиббса, моделирование Монте-Карло и очереди. Springer Science & Business Media. стр. ix. ISBN 978-1-4757-3124-8.
18. Хейс, Брайан (2013). «Первые звенья в цепи Маркова». American Scientist . 101 (2): 92–96. doi :10.1511/2013.101.92.
19. Sheldon M. Ross (1996). Стохастические процессы. Wiley. стр. 235 и 358. ISBN 978-0-471-12062-9.
20. Джарроу, Роберт; Проттер, Филип (2004). «Краткая история стохастической интеграции и математических финансов: ранние годы, 1880–1970». Сборник статей для Германа Рубина . С. 75–91. CiteSeerX 10.1.1.114.632 . doi :10.1214/lnms/1196285381. ISBN  978-0-940600-61-4.
21. Гутторп, Питер; Тораринсдоттир, Тордис Л. (2012). «Что случилось с дискретным хаосом, процессом Кенуйля и свойством Sharp Markov? Некоторая история стохастических точечных процессов». International Statistical Review . 80 (2): 253–268. doi :10.1111/j.1751-5823.2012.00181.x.
22. Сенета, Э. (1996). «Марков и рождение теории цепной зависимости». International Statistical Review . 64 (3): 255–257. doi :10.2307/1403785. JSTOR  1403785.
23. Сенета, Э. (1998). «И. Ж. Бьенеме [1796–1878]: критичность, неравенство и интернационализация». Международный статистический обзор . 66 (3): 291–292. doi :10.2307/1403518. JSTOR  1403518.
24. Брю Б, Герц С (2001). «Морис Фреше». В Heyde CC , Seneta E, Crépel P, Fienberg SE, Gani J (ред.). Статистики веков . Нью-Йорк, штат Нью-Йорк: Спрингер. стр. 331–334. дои : 10.1007/978-1-4613-0179-0_71. ISBN 978-0-387-95283-3.
25. Кендалл, Д. Г.; Бэтчелор, Г. К.; Бингем, Н. Х.; Хейман, В. К.; Хайленд, Дж. М. Э.; Лоренц, Г. Г.; Моффат, Х. К.; Парри, В.; Разборов, А. А.; Робинсон, К. А.; Уиттл, П. (1990). "Андрей Николаевич Колмогоров (1903–1987)". Бюллетень Лондонского математического общества . 22 (1): 33. doi :10.1112/blms/22.1.31.
26. Cramér, Harald (1976). «Полвека с теорией вероятностей: некоторые личные воспоминания». Анналы вероятности . 4 (4): 509–546. doi : 10.1214/aop/1176996025 .
27. Марк Барбут; Бернард Локер; Лоран Мазлиак (23 августа 2016 г.). Поль Леви и Морис Фреше: 50 лет переписки в 107 письмах. Спрингер Лондон. п. 5. ISBN 978-1-4471-7262-8.
28. Валерий Скороход (5 декабря 2005 г.). Основные принципы и приложения теории вероятностей. Springer Science & Business Media. стр. 146. ISBN 978-3-540-26312-8.
29. Бернстайн, Джереми (2005). «Башелье». Американский журнал физики . 73 (5): 395–398. Bibcode : 2005AmJPh..73..395B. doi : 10.1119/1.1848117.
30. Уильям Дж. Андерсон (6 декабря 2012 г.). Цепи Маркова с непрерывным временем: подход, ориентированный на приложения. Springer Science & Business Media. стр. vii. ISBN 978-1-4612-3038-0.
31. Кендалл, Д. Г.; Бэтчелор, Г. К.; Бингем, Н. Х.; Хейман, В. К.; Хайленд, Дж. М. Э.; Лоренц, Г. Г.; Моффат, Х. К.; Парри, В.; Разборов, А. А.; Робинсон, К. А.; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 57. doi :10.1112/blms/22.1.31.
32. Ionut Florescu (7 ноября 2014 г.). Вероятность и стохастические процессы. John Wiley & Sons. стр. 373 и 374. ISBN 978-1-118-59320-2.
33. Сэмюэл Карлин; Говард Э. Тейлор (2 декабря 2012 г.). Первый курс по стохастическим процессам. Academic Press. стр. 49. ISBN 978-0-08-057041-9.
34. Вайс, Джордж Х. (2006). «Случайные блуждания». Энциклопедия статистических наук . стр. 1. doi :10.1002/0471667196.ess2180.pub2. ISBN 978-0471667193.
35. Майкл Ф. Шлезингер (1985). Удивительный мир стохастики: дань уважения Эллиотту В. Монтроллу. Северная Голландия. С. 8–10. ISBN 978-0-444-86937-1.
36. Эмануэль Парзен (17 июня 2015 г.). Стохастические процессы. Courier Dover Publications. стр. 7, 8. ISBN 978-0-486-79688-8.
37. Джозеф Л. Дуб (1990). Стохастические процессы. Wiley. стр. 46, 47.
38. Дональд Л. Снайдер; Майкл И. Миллер (6 декабря 2012 г.). Случайные точечные процессы во времени и пространстве. Springer Science & Business Media. стр. 32. ISBN 978-1-4612-3166-0.
39. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем I». Цепи Маркова . С. 60–107. doi :10.1017/CBO9780511810633.004. ISBN 9780511810633.
40. Serfozo, Richard (2009). Основы прикладных стохастических процессов . Вероятность и ее приложения. Berlin: Springer. doi :10.1007/978-3-540-89332-5. ISBN 978-3-540-89331-8.
41. "Глава 11 "Цепи Маркова"" (PDF) . Получено 2017-06-02 .
42. Шмитт, Флориан; Ротлауф, Франц (2001). «О важности второго по величине собственного значения для скорости сходимости генетических алгоритмов». Труды 14-го симпозиума по надежным распределенным системам . CiteSeerX 10.1.1.28.6191 . 
43. Розенталь, Джеффри С. (1995). «Скорости сходимости для цепей Маркова». Обзор SIAM . 37 (3): 387–405. doi :10.1137/1037083. JSTOR  2132659. Получено 31 мая 2021 г.
44. Franzke, Brandon; Kosko, Bart (1 октября 2011 г.). «Шум может ускорить сходимость в цепях Маркова». Physical Review E. 84 ( 4): 041112. Bibcode : 2011PhRvE..84d1112F. doi : 10.1103/PhysRevE.84.041112. PMID  22181092.
45. Спитцер, Франк (1970). «Взаимодействие марковских процессов». Успехи математики . 5 (2): 246–290. doi : 10.1016/0001-8708(70)90034-4 .
46. Добрушин, Р. Л.; Крюков, В. И.; Тоом, А. Л. (1978). Стохастические клеточные системы: эргодичность, память, морфогенез. Manchester University Press. ISBN 9780719022067. Получено 2016-03-04 .
47. Хейман, Дэниел П.; Собель, Мэтью Дж. (1982). Стохастические модели в исследовании операций, том 1. Нью-Йорк: McGraw-Hill. стр. 230. ISBN 0-07-028631-0.
48. Перес, Юваль . "Покажите, что положительная повторяемость является свойством класса". Mathematics Stack Exchange . Получено 2024-02-01 .
49. Лэлли, Стив (2016). "Цепи Маркова: Базовая теория" (PDF) . Получено 22 июня 2024 г.
50. Парзен, Эмануэль (1962). Стохастические процессы . Сан-Франциско: Holden-Day. стр. 145. ISBN 0-8162-6664-6.
51. Shalizi, Cosma (1 декабря 2023 г.). "Эргодическая теория". bactra.org . Получено 01.02.2024 .
52. Сенета, Э. (Юджин) (1973). Неотрицательные матрицы; введение в теорию и приложения. Архив Интернета. Нью-Йорк, Wiley. ISBN 978-0-470-77605-6.
53. "10.3: Регулярные цепи Маркова". Mathematics LibreTexts . 2020-03-22 . Получено 2024-02-01 .
54. Seneta, E. (Eugene) (1973). "2.4. Комбинаторные свойства". Неотрицательные матрицы; введение в теорию и приложения. Архив Интернета. Нью-Йорк, Wiley. ISBN 978-0-470-77605-6.
55. Шен, Цзянь (1996-10-15). "Улучшение теоремы Дульмейджа-Мендельсона". Дискретная математика . 158 (1): 295–297. doi : 10.1016/0012-365X(95)00060-A .
56. Калленберг, Олав (2002). Основы современной вероятности . Вероятность и ее приложения (2-е изд., [Nachdr.] изд.). Нью-Йорк, Нью-Йорк Берлин Гейдельберг: Springer. Предложение 8.6 (стр. 145). ISBN 978-0-387-95313-7.
57. Доблингер, Г. (сентябрь 1998 г.). «Сглаживание зашумленных сигналов AR с использованием адаптивного фильтра Калмана» (PDF) . 9-я Европейская конференция по обработке сигналов (EUSIPCO 1998) : 781–784.
58. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем II». Цепи Маркова . С. 108–127. doi :10.1017/CBO9780511810633.005. ISBN 9780511810633.
59. Мэтью Никол и Карл Петерсен, (2009) «Эргодическая теория: основные примеры и конструкции», Энциклопедия сложности и системной науки , Springer https://doi.org/10.1007/978-0-387-30440-3_177
60. Фицпатрик, Ричард. "Термодинамика и статистическая механика" (PDF) . Получено 2017-06-02 .
61. van Ravenzwaaij, Don; Cassey, Pete; Brown, Scott D. (2016-03-11). «Простое введение в выборку Монте-Карло с цепями Маркова». Psychonomic Bulletin & Review . 25 (1): 143–154. doi :10.3758/s13423-016-1015-8. PMC 5862921. PMID  26968853 . 
62. Гаттингер, Кристоф; Ланг, Кристиан Б. (2010). Квантовая хромодинамика на решетке. Конспект лекций по физике. Том 788. Springer-Verlag Berlin Heidelberg. doi :10.1007/978-3-642-01850-3. ISBN 978-3-642-01849-7.
63. Андерсон, Дэвид Ф.; Курц, Томас Г. (2011), «Модели цепей Маркова с непрерывным временем для сетей химических реакций», Проектирование и анализ биомолекулярных цепей , Springer New York, стр. 3–42, doi :10.1007/978-1-4419-6766-4_1, ISBN 9781441967657
64. Ду, Чао; Коу, SC (сентябрь 2012 г.). «Корреляционный анализ ферментативной реакции одной белковой молекулы». Анналы прикладной статистики . 6 (3): 950–976. arXiv : 1209.6210 . Bibcode : 2012arXiv1209.6210D. doi : 10.1214/12-aoas541. PMC 3568780. PMID  23408514 . 
65. Кучукян, Питер; Лу, Дэвид; Шахнович, Юджин (2009). «FOG: алгоритм оптимизированного фрагментного роста для de Novo генерации молекул, занимающих лекарственноподобные химические вещества». Журнал химической информации и моделирования . 49 (7): 1630–1642. doi :10.1021/ci9000458. PMID  19527020.
66. Кучукян, PS; Лу, D.; Шахнович, Евгений И. (2009-06-15). "FOG: алгоритм оптимизированного фрагментного роста для de Novo генерации молекул, занимающих химическое пространство, подобное лекарственному средству". Журнал химической информации и моделирования . 49 (7): 1630–1642. doi :10.1021/ci9000458. PMID  19527020.
67. Копп, ВС; Каганер, ВМ; Шварцкопф, Дж.; Вайдик, Ф.; Реммеле, Т.; Квасьневский, А.; Шмидбауэр, М. (2011). «Дифракция рентгеновских лучей на непериодических слоистых структурах с корреляциями: аналитический расчет и эксперимент на смешанных пленках Ауривиллиуса». Acta Crystallographica Section A. 68 ( Pt 1): 148–155. Bibcode :2012AcCrA..68..148K. doi :10.1107/S0108767311044874. PMID  22186291.
68. Джордж, Дилип; Хокинс, Джефф (2009). Фристон, Карл Дж. (ред.). «К математической теории кортикальных микросхем». PLOS Comput Biol . 5 (10): e1000532. Bibcode : 2009PLSCB...5E0532G. doi : 10.1371/journal.pcbi.1000532 . PMC 2749218. PMID  19816557 . 
69. Гупта, Анкур; Роулингс, Джеймс Б. (апрель 2014 г.). «Сравнение методов оценки параметров в стохастических химических кинетических моделях: примеры в системной биологии». Журнал AIChE . 60 (4): 1253–1268. Bibcode : 2014AIChE..60.1253G. doi : 10.1002/aic.14409. PMC 4946376. PMID  27429455 . 
70. Aguiar, RJ; Collares-Pereira, M.; Conde, JP (1988). "Простая процедура генерации последовательностей ежедневных значений радиации с использованием библиотеки матриц перехода Маркова". Solar Energy . 40 (3): 269–279. Bibcode : 1988SoEn...40..269A. doi : 10.1016/0038-092X(88)90049-7.
71. Нгоко, БО; Сугихара, Х.; Фунаки, Т. (2014). «Синтетическая генерация данных солнечной радиации с высоким временным разрешением с использованием моделей Маркова». Солнечная энергия . 103 : 160–170. Bibcode : 2014SoEn..103..160N. doi : 10.1016/j.solener.2014.02.026.
72. Брайт, Дж. М.; Смит, К. И.; Тейлор, П. Г.; Крук, Р. (2015). «Стохастическая генерация синтетических поминутных временных рядов освещенности, полученных из данных среднечасовых наблюдений за погодой». Солнечная энергия . 115 : 229–242. Bibcode : 2015SoEn..115..229B. doi : 10.1016/j.solener.2015.02.032 .
73. Мункхаммар, Дж.; Виден, Дж. (2018). «Модель распределения смеси цепей Маркова с N-состояниями индекса ясного неба». Солнечная энергия . 173 : 487–495. Bibcode : 2018SoEn..173..487M. doi : 10.1016/j.solener.2018.07.056.
74. Морф, Х. (1998). «Стохастическая двухуровневая модель солнечного излучения (STSIM)». Солнечная энергия . 62 (2): 101–112. Bibcode : 1998SoEn...62..101M. doi : 10.1016/S0038-092X(98)00004-8.
75. Мункхаммар, Дж.; Виден, Дж. (2018). «Подход смеси распределения вероятностей цепей Маркова к индексу ясного неба». Солнечная энергия . 170 : 174–183. Bibcode : 2018SoEn..170..174M. doi : 10.1016/j.solener.2018.05.055.
76. Мор, Бхавья; Гархвал, Сунита; Кумар, Аджай (май 2021 г.). «Систематический обзор скрытых марковских моделей и их приложений». Архив вычислительных методов в инженерии . 28 (3): 1429–1448. doi :10.1007/s11831-020-09422-4. ISSN  1134-3060.
77. Томсен, Сэмюэл В. (2009), «Некоторые свидетельства, касающиеся генезиса теории информации Шеннона», Исследования по истории и философии науки , 40 (1): 81–91, Bibcode : 2009SHPSA..40...81T, doi : 10.1016/j.shpsa.2008.12.011
78. Пратас, Д; Сильва, Р; Пиньо, А; Феррейра, П. (18 мая 2015 г.). «Метод без выравнивания для поиска и визуализации перестроек между парами последовательностей ДНК». Научные отчеты . 5 (10203): 10203. Бибкод : 2015NatSR...510203P. дои : 10.1038/srep10203. ПМЦ 4434998 . ПМИД  25984837. 
79. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Цепь Маркова», Архив истории математики Мактьютора , Университет Сент-Эндрюс
80. SP Meyn, 2007. Методы управления сложными сетями. Архивировано 13 мая 2015 г. в Wayback Machine , Cambridge University Press, 2007.
81. Патент США 6,285,999
82. Гупта, Бридж; Агравал, Дхарма П.; Ямагучи, Синго (16 мая 2016 г.). Справочник по исследованиям современных криптографических решений для компьютерной и кибербезопасности. IGI Global. стр. 448–. ISBN 978-1-5225-0106-0.
83. Лэнгвилл, Эми Н.; Мейер, Карл Д. (2006). «Переупорядочение для проблемы PageRank» (PDF) . Журнал SIAM по научным вычислениям . 27 (6): 2112–2113. Bibcode :2006SJSC...27.2112L. CiteSeerX 10.1.1.58.8652 . doi :10.1137/040607551. 
84. Пейдж, Лоуренс; Брин, Сергей; Мотвани, Раджив; Виноград, Терри (1999). Рейтинг цитирования PageRank: наведение порядка в Интернете (технический отчет). CiteSeerX 10.1.1.31.1768 . 
85. Чамперноун, Д. (1953). «Модель распределения доходов». The Economic Journal . 63 (250): 318–51. doi :10.2307/2227127. JSTOR  2227127.
86. Саймон, Герберт; С. Бонини (1958). «Распределение размеров фирм». Am. Econ. Rev. 42 : 425–40.
87. Башелье, Луи (1900). «Теория спекуляций». Annales Scientifiques de l'École Normale Supérieure . 3 : 21–86. дои : 10.24033/asens.476. hdl : 2027/coo.31924001082803 .
88. например, Фама, Э. (1965). «Поведение цен на фондовом рынке». Журнал бизнеса . 38 .
89. Гамильтон, Джеймс (1989). «Новый подход к экономическому анализу нестационарных временных рядов и делового цикла». Econometrica . 57 (2): 357–84. CiteSeerX 10.1.1.397.3582 . doi :10.2307/1912559. JSTOR  1912559. 
90. Кальве, Лоран Э.; Фишер, Адлай Дж. (2001). «Прогнозирование мультифрактальной волатильности». Журнал эконометрики . 105 (1): 27–58. doi :10.1016/S0304-4076(01)00069-0.
91. Кальве, Лоран; Эдлай Фишер (2004). «Как прогнозировать долгосрочную волатильность: переключение режимов и оценка мультифрактальных процессов». Журнал финансовой эконометрики . 2 : 49–83. CiteSeerX 10.1.1.536.8334 . doi :10.1093/jjfinec/nbh003. 
92. Бреннан, Майкл; Сяб, Ихонг. "Волатильность цен на акции и премия за акции" (PDF) . Департамент финансов, Школа менеджмента Андерсона, Калифорнийский университет в Лос-Анджелесе . Архивировано из оригинала (PDF) 28.12.2008.
93. "Пример цепи Маркова в моделировании кредитного риска" (PDF) . Колумбийский университет . Архивировано из оригинала (PDF) 24 марта 2016 г.
94. Асемоглу, Дарон; Георгий Егоров; Константин Сонин (2011). «Политическая модель социальной эволюции». Труды Национальной академии наук . 108 (Приложение 4): 21292–21296. Bibcode : 2011PNAS..10821292A. CiteSeerX 10.1.1.225.6090 . doi : 10.1073/pnas.1019454108 . PMC 3271566. PMID  22198760 .  
95. K McAlpine; E Miranda; S Hoggar (1999). «Создание музыки с помощью алгоритмов: система изучения случая». Computer Music Journal . 23 (2): 19–30. doi :10.1162/014892699559733.
96. Curtis Roads, ред. (1996). Учебник компьютерной музыки . MIT Press. ISBN 978-0-262-18158-7.
97. Ксенакис, Ианнис; Канах, Шарон (1992) Формализованная музыка: математика и мысль в композиции , Pendragon Press. ISBN 1576470792 
98. "Continuator". Архивировано из оригинала 13 июля 2012 года.
99. Пачет, Ф.; Рой, П.; Барбьери, Г. (2011) «Марковские процессы конечной длины с ограничениями». Архивировано 14 апреля 2012 г. в Wayback Machine , Труды 22-й Международной совместной конференции по искусственному интеллекту , IJCAI, страницы 635–642, Барселона, Испания, июль 2011 г.
100. Панкин, Марк Д. "МАРКОВСКИЕ ЦЕПНЫЕ МОДЕЛИ: ТЕОРЕТИЧЕСКИЕ ОСНОВЫ". Архивировано из оригинала 2007-12-09 . Получено 2007-11-26 .
101. Панкин, Марк Д. "БЕЙСБОЛ КАК ЦЕПЬ МАРКОВА" . Получено 24.04.2009 .
102. "Poet's Corner – Fieralingue". Архивировано из оригинала 6 декабря 2010 года.
103. Кеннер, Хью; О'Рурк, Джозеф (ноябрь 1984 г.). «Генератор травести для микросхем». BYTE . 9 (12): 129–131, 449–469.
104. Хартман, Чарльз (1996). Виртуальная муза: эксперименты в области компьютерной поэзии . Ганновер, Нью-Гэмпшир: Wesleyan University Press. ISBN 978-0-8195-2239-9.
105. de Souza e Silva, EG; Legey, LFL; de Souza e Silva, EA (2010). "Прогнозирование тенденций цен на нефть с использованием вейвлетов и скрытых марковских моделей". Energy Economics . 32 (6): 1507. Bibcode : 2010EneEc..32.1507D. doi : 10.1016/j.eneco.2010.08.006.
106. Карпиноне, А; Джорджио, М; Ланджелла, Р.; Теста, А. (2015). «Моделирование цепи Маркова для сверхкраткосрочного прогнозирования ветроэнергетики». Исследования электроэнергетических систем . 122 : 152–158. Bibcode : 2015EPSR..122..152C. doi : 10.1016/j.epsr.2014.12.025 .
107. Ву, Гордон (2002-04-01). «Количественная оценка риска терроризма». Журнал Risk Finance . 4 (1): 7–14. doi :10.1108/eb022949 . Получено 5 октября 2023 г.
108. Ву, Гордон (декабрь 2003 г.). «Страхование от Аль-Каиды» (PDF) . Кембридж: Национальное бюро экономических исследований . Получено 26 марта 2024 г.
109. Munkhammar, J.; van der Meer, DW; Widén, J. (2019). «Вероятностное прогнозирование временных рядов индекса ясного неба с высоким разрешением с использованием модели распределения смеси цепей Маркова». Solar Energy . 184 : 688–695. Bibcode : 2019SoEn..184..688M. doi : 10.1016/j.solener.2019.04.014.

Ссылки

• А. А. Марков (1906) "Распространение закона больших долот на величины, зависящие друг от друга". Известия физико-математического общества при Казанском университете , 2-я серия, том 15, стр. 135–156.
• А. А. Марков (1971). "Распространение предельных теорем теории вероятностей на сумму переменных, соединенных в цепь". перепечатано в Приложении B к: Р. Ховард. Динамические вероятностные системы, том 1: Цепи Маркова . John Wiley and Sons.
• Классический текст в переводе: Марков, А.А. (2006). «Пример статистического исследования текста «Евгений Онегин» относительно связи выборок в цепях». Наука в контексте . 19 (4). Перевод Линка, Дэвида: 591–600. doi :10.1017/s0269889706001074.
• Лео Брейман (1992) [1968] Вероятность . Оригинальное издание опубликовано Addison-Wesley; перепечатано Society for Industrial and Applied Mathematics ISBN 0-89871-296-3 . (См. Главу 7) 
• JL Doob (1953) Стохастические процессы . Нью-Йорк: John Wiley and Sons ISBN 0-471-52369-0 . 
• SP Meyn и RL Tweedie (1993) Markov Chains and Stochastic Stability . London: Springer-Verlag ISBN 0-387-19832-6 . online: MCSS. Второе издание выйдет в Cambridge University Press, 2009. 
• Дынкин, Евгений Борисович (1965). Марковские процессы . Grundlehren der mathematischen Wissenschaften. Том. Я (121). Перевод Фабиуса, Яапа; Гринберг, Вида Лазарус; Майтра, Ашок Прасад; Маджоне, Джандоменико . Берлин: Springer-Verlag . дои : 10.1007/978-3-662-00031-1. ISBN 978-3-662-00033-5. Титул № 5104.; Марковские процессы . Grundlehren der mathematischen Wissenschaften. Том. II (122). 1965. doi : 10.1007/978-3-662-25360-1. ISBN 978-3-662-23320-7. Титул № 5105.(Примечание. Первоначально эта работа была опубликована на русском языке под названием « Марковские процессы » в Физматгизе в 1963 году и переведена на английский язык при содействии автора.)
• SP Meyn. Методы управления сложными сетями . Cambridge University Press, 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 
• Э. Нуммелин. "Общие неприводимые цепи Маркова и неотрицательные операторы". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X 
• Сенета, Э. Неотрицательные матрицы и цепи Маркова . 2-е перераб. изд., 1981, XVI, 288 стр., Мягкая обложка Springer Series in Statistics. (Первоначально опубликовано Allen & Unwin Ltd., Лондон, 1973) ISBN 978-0-387-29765-1 
• Кишор С. Триведи , Вероятность и статистика с приложениями надежности, очередей и вычислительной техники , John Wiley & Sons, Inc. Нью-Йорк, 2002. ISBN 0-471-33341-7 . 
• KS Trivedi и RASahner, SHARPE в возрасте двадцати двух лет , т. 36, № 4, стр. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
• RA Sahner, KS Trivedi и A. Puliafito, Анализ производительности и надежности компьютерных систем: подход на основе примеров с использованием программного пакета SHARPE , Kluwer Academic Publishers, 1996. ISBN 0-7923-9650-2 . 
• Г. Больх, С. Грейнер, Х. де Меер и К. С. Триведи, Сети очередей и цепи Маркова , John Wiley, 2-е издание, 2006. ISBN 978-0-7923-9650-5 . 

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

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