Цепь Маркова

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

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

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

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

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

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

Принципы

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

Определение

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

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

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

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

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

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

Переходы

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

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

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

История

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

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

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

Примеры

• Случайные блуждания , основанные на целых числах, и проблема разорения игрока являются примерами марковских процессов. ^{[41] [42]} Некоторые варианты этих процессов изучались сотни лет назад в контексте независимых переменных. ^{[43] [44] [45]} Двумя важными примерами марковских процессов являются винеровский процесс , также известный как процесс броуновского движения , и процесс Пуассона , ^[28] которые считаются наиболее важными и центральными случайными процессами в теории стохастические процессы. ^{[46] [47] [48]} Эти два процесса являются марковскими процессами в непрерывном времени, тогда как случайные блуждания по целым числам и проблема разорения игрока являются примерами марковских процессов в дискретном времени. ^{[41] [42]}
• Знаменитая цепь Маркова — это так называемая «блуждание пьяницы», случайное блуждание по числовой прямой , при котором на каждом шаге положение может меняться на +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 , называемое пространством состояний цепи.

Вариации

• Однородные во времени цепи Маркова — это процессы, в которых
  $${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}$$
  для всех н . Вероятность перехода не зависит от n .
• Стационарные цепи Маркова – это процессы, в которых
  $${\displaystyle \Pr(X_{0}=x_{0},X_{1}=x_{1},\ldots ,X_{k}=x_{k})=\Pr(X_{n}=x_{0},X_{n+1}=x_{1},\ldots ,X_{n+k}=x_{k})}$$
  для всех n и k . По правилу Байеса можно доказать, что каждая стационарная цепь однородна во времени.
  Необходимым и достаточным условием стационарности однородной во времени цепи Маркова является то, что распределение является стационарным распределением цепи Маркова. ${\displaystyle X_{0}}$
• Цепь Маркова с памятью (или цепь Маркова порядка m ), где m конечно, — это процесс, удовлетворяющий
  $${\displaystyle {\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}$$
  Другими словами, будущее состояние зависит от прошлых m состояний. Можно построить цепочку , обладающую «классическим» марковским свойством, взяв в качестве пространства состояний упорядоченные m -кортежи значений X , т. е. . ${\displaystyle (Y_{n})}$ ${\displaystyle (X_{n})}$ ${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$

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

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

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

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

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

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

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

дельта Кронекераобозначение «маленькое-о»ij ${\displaystyle \delta _{ij}}$ ${\displaystyle q_{ij}}$

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

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

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

Для любого значения 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 .

Если цепь Маркова неприводима и апериодична, то существует единственное стационарное распределение π . ^[50] Кроме того, в этом случае 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 , в крайнем правом столбце которой заменены все единицы. Если [ f ( P − I _n )] ⁻¹ существует, то ^{[51] [50]}

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

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

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

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

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

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

Цепи Харриса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Есть несколько комбинаторных результатов об показателе степени, когда состояний конечное число. Пусть – число состояний, тогда ^[63] ${\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}$
• (Теорема Дульмаджа-Мендельсона) Показатель степени – это обхват графа . Его можно улучшить до , где – диаметр графа . ^[64] ${\displaystyle \leq n+s(n-2)}$ ${\displaystyle s}$ ${\displaystyle \leq (d+1)+s(d+1-2)}$ ${\displaystyle d}$

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

Если цепь Маркова имеет стационарное распределение, то ее можно преобразовать в динамическую систему, сохраняющую меру : Пусть вероятностное пространство равно , где – множество всех состояний цепи Маркова. Пусть сигма-алгебра в вероятностном пространстве порождается цилиндрическими множествами. Пусть вероятностная мера порождается стационарным распределением и переходом цепи Маркова. Пусть – оператор сдвига: . Аналогично мы можем построить такую ​​динамическую систему вместо этого. ^[65] ${\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 }$

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

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

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

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

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

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

Время ударов

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

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

Для подмножества состояний A  ⊆  S вектор k ^A времен попадания (где элемент представляет ожидаемое значение , начиная с состояния i , когда цепь входит в одно из состояний в наборе A ) является минимальным неотрицательным решением ^{[ 67]} ${\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, _S , обозначается sij и представляет собой условную вероятность перехода из состояния 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 основных типа моделей, которые обобщают цепи Маркова в зависимости от того, является ли каждое последовательное состояние наблюдаемым или нет, и подлежит ли система корректировке на основе сделанных наблюдений:

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

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

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

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

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

Приложения

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

Физика

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

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

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

Химия

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

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

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

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

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

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

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

Биология

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

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

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

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

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

Оценка изменчивости солнечного излучения полезна для применения в солнечной энергетике . Изменчивость солнечного излучения в любом месте с течением времени является главным образом следствием детерминированной изменчивости пути Солнца по небесному куполу и изменчивости облачности. Изменчивость доступного солнечного излучения на поверхности Земли была смоделирована с использованием цепей Маркова, ^{[80] [81] [82] [83]} , включая моделирование двух состояний ясности и облачности как цепи Маркова с двумя состояниями. ^{[84] [85]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Игры

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

Музыка

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

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

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

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

Бейсбол

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

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

Марковские процессы также можно использовать для создания внешне реалистичного текста на основе образца документа. Марковские процессы используются в разнообразном развлекательном программном обеспечении « генератора пародий » (см. диссоциированную прессу , Джеффа Харрисона, ^[110] Марка В. Шейни , ^{[111] [112]} и Academias Neutronium). Существует несколько библиотек генерации текста с открытым исходным кодом, использующих цепи Маркова.

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

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

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

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

Примечания

1. Ганюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: Джон Уайли и сыновья. стр. 1–235. ISBN 978-1-119-38755-8.
2. «Цепь Маркова | Определение цепи Маркова на американском английском языке в Оксфордских словарях» . Оксфордские словари . Архивировано из оригинала 15 декабря 2017 года . Проверено 14 декабря 2017 г.
3. Определение на Brilliant.org «Brilliant Math and Science Wiki». Проверено 12 мая 2019 г.
4. Сэмюэл Карлин; Говард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. п. 47. ИСБН 978-0-08-057041-9. Архивировано из оригинала 23 марта 2017 года.
5. Брюс Хайек (12 марта 2015 г.). Случайные процессы для инженеров. Издательство Кембриджского университета. ISBN 978-1-316-24124-0. Архивировано из оригинала 23 марта 2017 года.
6. Г. Латуш; В. Рамасвами (1 января 1999 г.). Введение в методы матричного анализа в стохастическом моделировании. СИАМ. стр. 4–. ISBN 978-0-89871-425-8. Архивировано из оригинала 23 марта 2017 года.
7. Шон Мейн; Ричард Л. Твиди (2 апреля 2009 г.). Цепи Маркова и стохастическая устойчивость. Издательство Кембриджского университета. п. 3. ISBN 978-0-521-73182-9. Архивировано из оригинала 23 марта 2017 года.
8. Реувен Ю. Рубинштейн; Дирк П. Крозе (20 сентября 2011 г.). Моделирование и метод Монте-Карло. Джон Уайли и сыновья. п. 225. ИСБН 978-1-118-21052-9. Архивировано из оригинала 23 марта 2017 года.
9. Дэни Гамерман; Хедиберт Ф. Лопес (10 мая 2006 г.). Цепь Маркова Монте-Карло: стохастическое моделирование для байесовского вывода, второе издание. ЦРК Пресс. ISBN 978-1-58488-587-0. Архивировано из оригинала 23 марта 2017 года.
10. "Марковский" . Оксфордский словарь английского языка (онлайн-изд.). Издательство Оксфордского университета . (Требуется подписка или членство участвующей организации.)
11. Обработка сигналов на основе модели. Джон Уайли и сыновья. 27 октября 2005 г. ISBN. 9780471732662.
12. Оксендал, БК (Бернт Карстен) (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Шпрингер. ISBN 3540047581. ОСЛК  52203046.
13. Сорен Асмуссен (15 мая 2003 г.). Прикладная вероятность и очереди. Springer Science & Business Media. п. 7. ISBN 978-0-387-00211-8. Архивировано из оригинала 23 марта 2017 года.
14. Эмануэль Парзен (17 июня 2015 г.). Случайные процессы. Публикации Courier Dover. п. 188. ИСБН 978-0-486-79688-8. Архивировано из оригинала 20 ноября 2017 года.
15. Сэмюэл Карлин; Говард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. стр. 29 и 30. ISBN. 978-0-08-057041-9. Архивировано из оригинала 23 марта 2017 года.
16. Джон Ламперти (1977). Случайные процессы: обзор математической теории. Спрингер-Верлаг. стр. 106–121. ISBN 978-3-540-90275-1. Архивировано из оригинала 23 марта 2017 г.
17. Шелдон М. Росс (1996). Случайные процессы. Уайли. стр. 174 и 231. ISBN. 978-0-471-12062-9. Архивировано из оригинала 23 марта 2017 г.
18. Эверитт, BS (2002) Кембриджский статистический словарь . ЧАШКА. ISBN 0-521-81099-X 
19. Парзен, Э. (1962) Случайные процессы , Холден-Дэй. ISBN 0-8162-6664-6 (таблица 6.1) 
20. Додж, Ю. (2003) Оксфордский словарь статистических терминов , OUP. ISBN 0-19-920613-9 (запись о «Цепи Маркова») 
21. Додж, Ю. Оксфордский словарь статистических терминов , OUP. ISBN 0-19-920613-9 
22. Мейн, С. Шон П. и Ричард Л. Твиди. (2009) Цепи Маркова и стохастическая устойчивость . Издательство Кембриджского университета. (Предисловие, стр. iii)
23. Gagniuc, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: Джон Уайли и сыновья. стр. 159–163. ISBN 978-1-119-38755-8.
24. Ганюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: Джон Уайли и сыновья. стр. 2–8. ISBN 978-1-119-38755-8.
25. Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. Американское математическое соц. стр. 464–466. ISBN 978-0-8218-0749-1.
26. Пьер Бремо (9 марта 2013 г.). Цепи Маркова: поля Гиббса, моделирование Монте-Карло и очереди. Springer Science & Business Media. п. ix. ISBN 978-1-4757-3124-8. Архивировано из оригинала 23 марта 2017 года.
27. Хейс, Брайан (2013). «Первые звенья цепи Маркова». Американский учёный . 101 (2): 92–96. дои : 10.1511/2013.101.92.
28. Шелдон М. Росс (1996). Случайные процессы. Уайли. стр. 235 и 358. ISBN. 978-0-471-12062-9. Архивировано из оригинала 23 марта 2017 г.
29. Джарроу, Роберт; Проттер, Филип (2004). «Краткая история стохастической интеграции и математических финансов: первые годы, 1880–1970». Фестиваль Германа Рубина . Конспект лекций Института математической статистики – Серия монографий. стр. 75–91. CiteSeerX 10.1.1.114.632 . doi : 10.1214/lnms/1196285381. ISBN  978-0-940600-61-4. ISSN  0749-2170.
30. Гутторп, Питер; Тораринсдоттир, Тордис Л. (2012). «Что случилось с дискретным хаосом, процессом Кенуя и свойством Шарпа Маркова? Немного истории стохастических точечных процессов». Международный статистический обзор . 80 (2): 253–268. дои : 10.1111/j.1751-5823.2012.00181.x. ISSN  0306-7734. S2CID  80836.
31. Сенета, Э. (1996). «Марков и рождение теории цепной зависимости». Международное статистическое обозрение/Revue Internationale de Statistique . 64 (3): 255–257. дои : 10.2307/1403785. ISSN  0306-7734. JSTOR  1403785.
32. Сенета, Э. (1998). «И. Ж. Бьенеме [1796–1878]: критичность, неравенство и интернационализация». Международное статистическое обозрение/Revue Internationale de Statistique . 66 (3): 291–292. дои : 10.2307/1403518. ISSN  0306-7734. JSTOR  1403518.
33. Брю Б, Герц С (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.
34. Кендалл, генеральный директор; Бэтчелор, ГК; Бингем, Нью-Хэмпшир; Хейман, ВК; Хайланд, JME; Лоренц, Г.Г.; Моффатт, Гонконг; Парри, В.; Разборов А.А.; Робинсон, Калифорния; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 33. doi :10.1112/blms/22.1.31. ISSN  0024-6093.
35. Крамер, Харальд (1976). «Полвека с теорией вероятностей: некоторые личные воспоминания». Анналы вероятности . 4 (4): 509–546. дои : 10.1214/aop/1176996025 . ISSN  0091-1798.
36. Марк Барбут; Бернард Локер; Лоран Мазлиак (23 августа 2016 г.). Поль Леви и Морис Фреше: 50 лет переписки в 107 письмах. Спрингер Лондон. п. 5. ISBN 978-1-4471-7262-8. Архивировано из оригинала 23 марта 2017 года.
37. Валерий Скороход (5 декабря 2005 г.). Основные принципы и приложения теории вероятностей. Springer Science & Business Media. п. 146. ИСБН 978-3-540-26312-8. Архивировано из оригинала 23 марта 2017 года.
38. Бернштейн, Джереми (2005). «Башелье». Американский журнал физики . 73 (5): 395–398. Бибкод : 2005AmJPh..73..395B. дои : 10.1119/1.1848117. ISSN  0002-9505.
39. Уильям Дж. Андерсон (6 декабря 2012 г.). Цепи Маркова с непрерывным временем: прикладно-ориентированный подход. Springer Science & Business Media. п. VII. ISBN 978-1-4612-3038-0. Архивировано из оригинала 23 марта 2017 года.
40. Кендалл, генеральный директор; Бэтчелор, ГК; Бингем, Нью-Хэмпшир; Хейман, ВК; Хайланд, JME; Лоренц, Г.Г.; Моффатт, Гонконг; Парри, В.; Разборов А.А.; Робинсон, Калифорния; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества . 22 (1): 57. doi :10.1112/blms/22.1.31. ISSN  0024-6093.
41. Ионут Флореску (7 ноября 2014 г.). Вероятность и случайные процессы. Джон Уайли и сыновья. стр. 373 и 374. ISBN. 978-1-118-59320-2. Архивировано из оригинала 23 марта 2017 года.
42. Сэмюэл Карлин; Говард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. п. 49. ИСБН 978-0-08-057041-9. Архивировано из оригинала 23 марта 2017 года.
43. Ганюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам . США, Нью-Джерси: Джон Уайли и сыновья. стр. 1–2. ISBN 978-1-119-38755-8.
44. Вайс, Джордж Х. (2006). «Случайные прогулки». Энциклопедия статистических наук . п. 1. дои : 10.1002/0471667196.ess2180.pub2. ISBN 978-0471667193.
45. Майкл Ф. Шлезингер (1985). Чудесный мир стохастики: дань уважения Эллиоту В. Монтроллу. Северная Голландия. стр. 8–10. ISBN 978-0-444-86937-1. Архивировано из оригинала 23 марта 2017 г.
46. Эмануэль Парзен (17 июня 2015 г.). Случайные процессы. Публикации Courier Dover. п. 7 и 8. ISBN 978-0-486-79688-8. Архивировано из оригинала 20 ноября 2017 года.
47. Джозеф Л. Дуб (1990). Сточастипоические процессы. Уайли. п. 46 и 47. Архивировано из оригинала 20 ноября 2017 г.
48. Дональд Л. Снайдер; Майкл И. Миллер (6 декабря 2012 г.). Случайные точечные процессы во времени и пространстве. Springer Science & Business Media. п. 32. ISBN 978-1-4612-3166-0. Архивировано из оригинала 20 ноября 2017 года.
49. Норрис, младший (1997). «Цепи Маркова в непрерывном времени I». Марковские цепи . стр. 60–107. дои : 10.1017/CBO9780511810633.004. ISBN 9780511810633.
50. Серфозо, Ричард (2009). «Основы прикладных случайных процессов» . Вероятность и ее приложения . дои : 10.1007/978-3-540-89332-5. ISBN 978-3-540-89331-8. ISSN  1431-7028.
51. «Глава 11 «Цепи Маркова»» (PDF) . Архивировано (PDF) из оригинала 15 февраля 2017 г. Проверено 2 июня 2017 г.
52. Шмитт, Флориан; Ротлауф, Франц (2001). «О важности второго по величине собственного значения для скорости сходимости генетических алгоритмов». Материалы 14-го симпозиума по надежным распределенным системам . CiteSeerX 10.1.1.28.6191 . 
53. Розенталь, Джеффри С. (1995). «Скорость сходимости цепей Маркова». Обзор СИАМ . 37 (3): 387–405. дои : 10.1137/1037083. ISSN  0036-1445. JSTOR  2132659 . Проверено 31 мая 2021 г.
54. Францке, Брэндон; Коско, Барт (1 октября 2011 г.). «Шум может ускорить сходимость цепей Маркова». Физический обзор E . 84 (4): 041112. Бибкод : 2011PhRvE..84d1112F. doi : 10.1103/PhysRevE.84.041112. ПМИД  22181092.
55. Спитцер, Фрэнк (1970). «Взаимодействие марковских процессов». Достижения в математике . 5 (2): 246–290. дои : 10.1016/0001-8708(70)90034-4 .
56. Добрушин, Р.Л .; Крюков В.И.; Тум, Ал. (1978). Стохастические клеточные системы: эргодичность, память, морфогенез. Издательство Манчестерского университета. ISBN 9780719022067. Архивировано из оригинала 5 февраля 2017 г. Проверено 4 марта 2016 г.
57. Хейман, Дэниел П.; Собел, Мэтью Дж. (1982). Стохастические модели в исследовании операций, Том 1 . Нью-Йорк: МакГроу-Хилл. п. 230. ИСБН 0-07-028631-0.
58. Перес, Юваль . «Покажите, что положительная повторяемость является свойством класса». Математический обмен стеками . Проверено 1 февраля 2024 г.
59. Парзен, Эмануэль (1962). Случайные процессы . Сан-Франциско: Холден-Дэй. п. 145. ИСБН 0-8162-6664-6.
60. Шализи, Косма (1 декабря 2023 г.). «Эргодическая теория». bactra.org . Архивировано из оригинала 31 декабря 2023 года . Проверено 1 февраля 2024 г.
61. Сенета, Э. (Юджин) (1973). Неотрицательные матрицы; введение в теорию и приложения. Интернет-архив. Нью-Йорк, Уайли. ISBN 978-0-470-77605-6.
62. «10.3: Регулярные цепи Маркова». Математика LibreTexts . 22 марта 2020 г. Проверено 1 февраля 2024 г.
63. Сенета, Э. (Юджин) (1973). «2.4. Комбинаторные свойства». Неотрицательные матрицы; введение в теорию и приложения. Интернет-архив. Нью-Йорк, Уайли. ISBN 978-0-470-77605-6.
64. Шен, Цзянь (15 октября 1996 г.). «Улучшение теоремы Дулмаджа-Мендельсона». Дискретная математика . 158 (1): 295–297. дои : 10.1016/0012-365X(95)00060-A . ISSN  0012-365X.
65. Калленберг, Олав (2002). Основы современной вероятности . Вероятность и ее приложения (2-е изд., [Начдр.] изд.). Нью-Йорк, Нью-Йорк, Берлин, Гейдельберг: Springer. Предложение 8.6 (стр. 145). ISBN 978-0-387-95313-7.
66. Доблингер, Г. (сентябрь 1998 г.). «Сглаживание зашумленных сигналов AR с помощью адаптивного фильтра Калмана» (PDF) . 9-я Европейская конференция по обработке сигналов (EUSIPCO 1998) : 781–784.
67. Норрис, младший (1997). «Цепи Маркова в непрерывном времени II». Марковские цепи . стр. 108–127. дои : 10.1017/CBO9780511810633.005. ISBN 9780511810633.
68. Мэтью Никол и Карл Петерсен, (2009) «Эргодическая теория: основные примеры и конструкции», Энциклопедия сложности и системных наук , Springer https://doi.org/10.1007/978-0-387-30440-3_177
69. Фицпатрик, Ричард. «Термодинамика и статистическая механика» (PDF) . Архивировано (PDF) из оригинала 30 ноября 2016 г. Проверено 2 июня 2017 г.
70. ван Равенцваай, Дон; Кэсси, Пит; Браун, Скотт Д. (11 марта 2016 г.). «Простое введение в выборку методом Монте-Карло с помощью цепи Маркова». Психономический бюллетень и обзор . 25 (1): 143–154. дои : 10.3758/s13423-016-1015-8. ISSN  1069-9384. ПМК 5862921 . ПМИД  26968853. 
71. Райдер, Льюис Х. (1985). Квантовая теория поля . Кембридж [Кембриджшир]: Издательство Кембриджского университета. стр. 160. ISBN. 978-0521338592. ОСЛК  10533049.
72. Гаттрингер, Кристоф; Ланг, Кристиан Б. (2010). Квантовая хромодинамика на решетке. Конспект лекций по физике. Том. 788. Шпрингер-Верлаг Берлин Гейдельберг. дои : 10.1007/978-3-642-01850-3. ISBN 978-3-642-01849-7. Архивировано из оригинала 01 августа 2017 г.
73. Андерсон, Дэвид Ф.; Курц, Томас Г. (2011), «Модели марковской цепи непрерывного времени для сетей химических реакций», Проектирование и анализ биомолекулярных цепей , Springer New York, стр. 3–42, номер документа : 10.1007/978-1-4419-6766- 4_1, ISBN 9781441967657
74. Ду, Чао; Коу, Южная Каролина (сентябрь 2012 г.). «Корреляционный анализ ферментативной реакции одиночной белковой молекулы». Анналы прикладной статистики . 6 (3): 950–976. arXiv : 1209.6210 . Бибкод : 2012arXiv1209.6210D. дои : 10.1214/12-aoas541. ISSN  1932-6157. ПМК 3568780 . ПМИД  23408514. 
75. Кучукян, Питер; Лу, Дэвид; Шахнович, Евгений (2009). «FOG: оптимизированный по фрагментам алгоритм роста для нового поколения молекул, занимающих химические вещества, подобные лекарствам». Журнал химической информации и моделирования . 49 (7): 1630–1642. дои : 10.1021/ci9000458. ПМИД  19527020.
76. Кучукян, Питер С.; Лу, Дэвид; Шахнович, Евгений Иванович (15 июня 2009 г.). «FOG: оптимизированный по фрагментам алгоритм роста для нового поколения молекул, занимающих химическое пространство, подобное лекарству». Журнал химической информации и моделирования . 49 (7): 1630–1642. дои : 10.1021/ci9000458. ISSN  1549-9596. ПМИД  19527020.
77. Копп, В.С.; Каганер, В.М.; Шварцкопф, Дж.; Вайдик, Ф.; Реммеле, Т.; Квасьневский А.; Шмидбауэр, М. (2011). «Рентгеновская дифракция на непериодических слоистых структурах с корреляциями: аналитический расчет и эксперимент на смешанных пленках Ауривиллиуса». Acta Crystallographica Раздел А. 68 (Часть 1): 148–155. Бибкод : 2012AcCrA..68..148K. дои : 10.1107/S0108767311044874. ПМИД  22186291.
78. Джордж, Дилип; Хокинс, Джефф (2009). Фристон, Карл Дж. (ред.). «К математической теории корковых микросхем». ПЛОС Компьютерная Биол . 5 (10): е1000532. Бибкод : 2009PLSCB...5E0532G. дои : 10.1371/journal.pcbi.1000532 . ПМК 2749218 . ПМИД  19816557. 
79. Гупта, Анкур; Роулингс, Джеймс Б. (апрель 2014 г.). «Сравнение методов оценки параметров в стохастических химико-кинетических моделях: примеры системной биологии». Журнал Айше . 60 (4): 1253–1268. Бибкод :2014АИЧЕ..60.1253Г. дои : 10.1002/aic.14409. ПМЦ 4946376 . ПМИД  27429455. 
80. Агиар, Р.Дж.; Колларес-Перейра, М.; Конде, JP (1988). «Простая процедура генерации последовательностей ежедневных значений радиации с использованием библиотеки матриц марковских переходов». Солнечная энергия . 40 (3): 269–279. Бибкод : 1988SoEn...40..269A. дои : 10.1016/0038-092X(88)90049-7.
81. Нгоко, БО; Сугихара, Х.; Фунаки, Т. (2014). «Синтетическая генерация данных о солнечном излучении с высоким временным разрешением с использованием марковских моделей». Солнечная энергия . 103 : 160–170. Бибкод : 2014SoEn..103..160N. doi :10.1016/j.solener.2014.02.026.
82. Брайт, Дж. М.; Смит, CI; Тейлор, П.Г.; Крук, Р. (2015). «Стохастическая генерация синтетических поминутных временных рядов освещенности, полученных на основе среднечасовых данных наблюдений за погодой». Солнечная энергия . 115 : 229–242. Бибкод : 2015SoEn..115..229B. doi : 10.1016/j.solener.2015.02.032 .
83. Мункхаммар, Дж.; Виден, Дж. (2018). «Модель распределения смеси марковской цепи N-состояний индекса ясного неба». Солнечная энергия . 173 : 487–495. Бибкод : 2018SoEn..173..487M. doi :10.1016/j.solener.2018.07.056. S2CID  125538244.
84. Морф, Х. (1998). «Стохастическая модель солнечного излучения с двумя состояниями (STSIM)». Солнечная энергия . 62 (2): 101–112. Бибкод : 1998SoEn...62..101M. дои : 10.1016/S0038-092X(98)00004-8.
85. Мункхаммар, Дж.; Виден, Дж. (2018). «Подход к индексу ясного неба, основанный на смешанном распределении вероятностей с помощью цепи Маркова». Солнечная энергия . 170 : 174–183. Бибкод : 2018SoEn..170..174M. doi :10.1016/j.solener.2018.05.055. S2CID  125867684.
86. Пратас, Д; Сильва, Р; Пиньо, А; Феррейра, П. (18 мая 2015 г.). «Метод без выравнивания для поиска и визуализации перестроек между парами последовательностей ДНК». Научные отчеты . 5 (10203): 10203. Бибкод : 2015NatSR...510203P. дои : 10.1038/srep10203. ПМЦ 4434998 . ПМИД  25984837. 
87. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Цепь Маркова», Архив истории математики MacTutor , Университет Сент-Эндрюс
88. С. П. Мейн, 2007. Методы управления сложными сетями. Архивировано 13 мая 2015 г. в Wayback Machine , Cambridge University Press, 2007.
89. Патент США 6 285 999.
90. Гупта, Бридж; Агравал, Дхарма П.; Ямагути, Синго (16 мая 2016 г.). Справочник по исследованиям современных криптографических решений для компьютерной и кибербезопасности. IGI Global. стр. 448–. ISBN 978-1-5225-0106-0. Архивировано из оригинала 23 марта 2017 года.
91. Лэнгвилл, Эми Н.; Мейер, Карл Д. (2006). «Изменение порядка решения проблемы PageRank» (PDF) . Журнал SIAM по научным вычислениям . 27 (6): 2112–2113. Бибкод : 2006SJSC...27.2112L. CiteSeerX 10.1.1.58.8652 . дои : 10.1137/040607551. ISSN  1064-8275. Архивировано (PDF) из оригинала 21 сентября 2017 г. 
92. Пейдж, Лоуренс; Брин, Сергей; Мотвани, Раджив; Виноград, Терри (1999). Рейтинг цитируемости PageRank: наведение порядка в Интернете (технический отчет). CiteSeerX 10.1.1.31.1768 . 
93. Чамперноун, Д. (1953). «Модель распределения доходов». Экономический журнал . 63 (250): 318–51. дои : 10.2307/2227127. JSTOR  2227127.
94. Саймон, Герберт; С. Бонини (1958). «Распределение коммерческих фирм по размерам». Являюсь. Экон. Преподобный . 42 : 425–40.
95. Башелье, Луи (1900). «Теория спекуляций». Annales Scientifiques de l'École Normale Supérieure . 3 : 21–86. дои : 10.24033/asens.476. hdl : 2027/coo.31924001082803 .
96. например , Фама, Э (1965). «Поведение цен на фондовом рынке». Журнал бизнеса . 38 .
97. Гамильтон, Джеймс (1989). «Новый подход к экономическому анализу нестационарных временных рядов и делового цикла». Эконометрика . 57 (2): 357–84. CiteSeerX 10.1.1.397.3582 . дои : 10.2307/1912559. JSTOR  1912559. 
98. Кальве, Лоран Э.; Фишер, Адлай Дж. (2001). «Прогнозирование мультифрактальной волатильности». Журнал эконометрики . 105 (1): 27–58. дои : 10.1016/S0304-4076(01)00069-0. S2CID  119394176.
99. Кальве, Лоран; Адлай Фишер (2004). «Как прогнозировать долгосрочную волатильность: переключение режимов и оценка мультифрактальных процессов». Журнал финансовой эконометрики . 2 : 49–83. CiteSeerX 10.1.1.536.8334 . doi : 10.1093/jjfinec/nbh003. S2CID  6020401. 
100. Бреннан, Майкл; Сяб, Ихонг. «Волатильность цен на акции и премия за акции» (PDF) . Департамент финансов Школы менеджмента Андерсона Калифорнийского университета в Лос-Анджелесе . Архивировано из оригинала (PDF) 28 декабря 2008 г.
101. «Пример цепи Маркова в моделировании кредитного риска» (PDF) . Колумбийский университет . Архивировано из оригинала (PDF) 24 марта 2016 г.
102. Аджемоглу, Дарон; Георгий Егоров; Константин Сонин (2011). «Политическая модель социальной эволюции». Труды Национальной академии наук . 108 (Приложение 4): 21292–21296. Бибкод : 2011PNAS..10821292A. CiteSeerX 10.1.1.225.6090 . дои : 10.1073/pnas.1019454108 . ПМЦ 3271566 . ПМИД  22198760.  
103. К. Макэлпайн; Э Миранда; С. Хоггар (1999). «Создание музыки с помощью алгоритмов: система тематического исследования». Компьютерный музыкальный журнал . 23 (2): 19–30. дои : 10.1162/014892699559733. S2CID  40057162.
104. Кертис Роудс, изд. (1996). Учебник по компьютерной музыке . МТИ Пресс. ISBN 978-0-262-18158-7.
105. Ксенакис, Яннис; Канах, Шэрон (1992) Формализованная музыка: математика и мысль в композиции , Pendragon Press. ISBN 1576470792 
106. «Продолжитель». Архивировано из оригинала 13 июля 2012 года.
107. Паше, Ф.; Рой, П.; Барбьери, Г. (2011) «Марковские процессы конечной длины с ограничениями». Архивировано 14 апреля 2012 г. в Wayback Machine , Труды 22-й Международной совместной конференции по искусственному интеллекту , IJCAI, страницы 635–642, Барселона, Испания, июль. 2011 год
108. Панкин, Марк Д. «МОДЕЛИ ЦЕПИ МАРКОВА: ТЕОРЕТИЧЕСКАЯ ОСНОВА». Архивировано из оригинала 9 декабря 2007 г. Проверено 26 ноября 2007 г.
109. Панкин, Марк Д. «БЕЙСБОЛ КАК ЦЕПЬ МАРКОВА». Архивировано из оригинала 13 мая 2009 г. Проверено 24 апреля 2009 г.
110. "Уголок поэта - Fieralingue" . Архивировано из оригинала 6 декабря 2010 года.
111. Кеннер, Хью; О'Рурк, Джозеф (ноябрь 1984 г.). «Генератор пародий для микро». БАЙТ . 9 (12): 129–131, 449–469.
112. Хартман, Чарльз (1996). Виртуальная муза: эксперименты в компьютерной поэзии . Ганновер, Нью-Хэмпшир: Издательство Уэслианского университета. ISBN 978-0-8195-2239-9.
113. де Соуза и Силва, EG; Леги, LFL; де Соуза и Силва, Э.А. (2010). «Прогнозирование тенденций цен на нефть с использованием вейвлетов и скрытых моделей Маркова». Экономика энергетики . 32 .
114. Карпиноне, А; Джорджио, М; Ланджелла, Р.; Теста, А. (2015). «Моделирование цепей Маркова для очень краткосрочного прогнозирования ветроэнергетики». Исследование электроэнергетических систем . 122 : 152–158. дои : 10.1016/j.epsr.2014.12.025 .
115. Мунхаммар, Дж.; ван дер Меер, DW; Виден, Дж. (2019). «Вероятностное прогнозирование временных рядов индекса ясного неба с высоким разрешением с использованием модели распределения смеси цепи Маркова». Солнечная энергия . 184 : 688–695. Бибкод : 2019SoEn..184..688M. doi :10.1016/j.solener.2019.04.014. S2CID  146076100.

Рекомендации

• А. А. Марков (1906) "Распространение закона больших долот на величины, зависящие друг от друга". Известия физико-математического общества при Казанском университете , 2-я серия, том 15, стр. 135–156.
• А. А. Марков (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, связанных в цепочку». перепечатано в Приложении B: Р. Ховард. Динамические вероятностные системы, том 1: Цепи Маркова . Джон Уайли и сыновья.
• Классический текст в переводе: Марков А.А. (2006). Перевод Линка, Дэвида. «Пример статистического исследования текста «Евгений Онегин» по поводу соединения образцов в цепочки». Наука в контексте . 19 (4): 591–600. дои : 10.1017/s0269889706001074. S2CID  144854176.
• Лео Брейман (1992) [1968] Вероятность . Оригинальное издание опубликовано Аддисон-Уэсли; перепечатано ISBN Общества промышленной и прикладной математики 0-89871-296-3 . (См. главу 7) 
• Дж. Л. Дуб (1953) Стохастические процессы . Нью-Йорк: ISBN Джона Уайли и сыновей 0-471-52369-0 . 
• С. П. Мейн и Р. Л. Твиди (1993) Марковские цепи и стохастическая устойчивость . Лондон: ISBN Springer-Verlag 0-387-19832-6 . онлайн: МЦСС. Появится второе издание, Cambridge University Press, 2009 г. 
• Дынкин, Евгений Борисович (1965) [10.03.1963, 31.03.1962]. Написано в Московском университете, Москва, Россия. Марковские процессы-I . Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Том. Я (121). Перевод Фабиуса Яапа [в Викиданных] ; Гринберг, Вида Лазарус [в Викиданных] ; Майтра, Ашок Прасад [в Викиданных] ; Маджоне, Джандоменико (1-е изд.). Нью-Йорк, США / Берлин, Германия: Springer-Verlag ( Academic Press, Inc., Publishers ). дои : 10.1007/978-3-662-00031-1. ISBN 978-3-662-00033-5. ISSN  0072-7830. LCCN  64-24812. S2CID  251691119. Номер документа. 5104 . Проверено 2 сентября 2023 г.[1] (xii+365+1 стр.); Дынкин Евгений Борисович (1965) [10.03.1963, 31.03.1962]. Написано в Московском университете, Москва, Россия. Марковские процессы-II . Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete. Том. II (122). Перевод Фабиуса Яапа [в Викиданных] ; Гринберг, Вида Лазарус [в Викиданных] ; Майтра, Ашок Прасад [в Викиданных] ; Маджоне, Джандоменико (1-е изд.). Нью-Йорк, США / Берлин, Германия: Springer-Verlag . дои : 10.1007/978-3-662-25360-1. ISBN 978-3-662-23320-7. ISSN  0072-7830. LCCN  64-24812. Название-№. 5105 . Проверено 2 сентября 2023 г.(viii+274+2 страницы) (Примечание. Первоначально это было опубликовано на русском языке под названием «Марковские процессы» ( Марковские процессы ) Физматгизом ( Физматгиз ) в 1963 году и переведено на английский язык при содействии автора.)
• ИП Мейн. Методы управления сложными сетями . Издательство Кембриджского университета, 2007. ISBN 978-0-521-88441-9 . Приложение содержит сокращенную версию книги Meyn & Tweedie. онлайн: [2] 
• Бут, Тейлор Л. (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 . 

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

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