Цепь Маркова - Markov chain

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

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

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

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

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

Введение

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

Определение

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

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

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

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

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

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

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

Переходы

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

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

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

История

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Возможные значения Икс_я сформировать счетный набор S называется пространством состояний цепи.

Вариации

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

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

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

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

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

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

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

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

Цепь Маркова с непрерывным временем (Икс_т)_т ≥ 0 определяется конечным или счетным пространством состояний S, а матрица скорости перехода Q с размерностями, равными размерам пространства состояний, и начальное распределение вероятностей, определенное в пространстве состояний. Для я ≠ j, элементы q_ij неотрицательны и описывают скорость перехода процесса из состояния я заявить j. Элементы q_ii выбираются таким образом, чтобы каждая строка матрицы скорости перехода была равна нулю, в то время как суммы строк матрицы вероятности перехода в (дискретной) цепи Маркова были равны единице.

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

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

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

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

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

где ${\displaystyle \delta _{ij}}$ это Дельта Кронекера, с использованием маленькая нотация. ${\displaystyle q_{ij}}$ можно рассматривать как измерение скорости перехода от я к j бывает.

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

Определите цепь Маркова с дискретным временем Y_п описать пскачок процесса и переменных S₁, S₂, S₃, ... для описания времени выдержки в каждом из состояний, где S_я следует экспоненциальному распределению с параметром скорости -q_YяYя.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот один из способов сделать это: сначала определите функцию ж(А), чтобы вернуть матрицу А с заменой крайнего правого столбца на все единицы. Если [ж(п − я_п)]⁻¹ существует тогда^[50][49]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цепи Харриса

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

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

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

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

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

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

Свойства

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

Штат я есть период ${\displaystyle k}$ если ${\displaystyle k}$ это наибольший общий делитель количества переходов, на которые я можно добраться, начиная с я. Это:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Время попадания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Марковская модель

Основная статья: Марковская модель

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

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

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

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

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

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

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

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

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

Приложения

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

Физика

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

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

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

Химия

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

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

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

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

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

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

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

Биология

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

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

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

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

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

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

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

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

Информация и информатика

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

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

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

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

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

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

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

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

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

В PageRank веб-страницы, используемой Google определяется цепью Маркова.^[78][79][80] Вероятность оказаться на странице ${\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 }$ принимается равным около 0,15.^[81]

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

Статистика

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

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

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

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

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

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

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

Игры

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

Музыка

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

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

Заметка	А	C♯	E♭
А	0.1	0.6	0.3
C♯	0.25	0.05	0.7
E♭	0.7	0.3	0

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

Заметки	А	D	г
AA	0.18	0.6	0.22
ОБЪЯВЛЕНИЕ	0.5	0.5	0
AG	0.15	0.75	0.1
DD	0	0	1
DA	0.25	0	0.75
DG	0.9	0.1	0
GG	0.4	0.4	0.2
GA	0.5	0.25	0.25
GD	1	0	0

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

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

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

Бейсбол

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

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

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

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

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

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

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

Заметки

1. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 1–235. ISBN  978-1-119-38755-8.
2. "Цепь Маркова | Определение цепи Маркова в английском языке по Оксфордским словарям". Оксфордские словари | английский. Получено 2017-12-14.
3. Определение на Brilliant.org "Brilliant Math and Science Wiki". Проверено 12 мая 2019 г.
4. Сэмюэл Карлин; Ховард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. п. 47. ISBN  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. ISBN  978-1-118-21052-9. В архиве из оригинала от 23 марта 2017 г.
9. Дэни Геймерман; Хедиберт Ф. Лопес (10 мая 2006 г.). Цепь Маркова Монте-Карло: стохастическое моделирование для байесовского вывода, второе издание. CRC Press. ISBN  978-1-58488-587-0. В архиве из оригинала от 23 марта 2017 г.
10. «Марковский». Оксфордский словарь английского языка (Интернет-ред.). Издательство Оксфордского университета. (Подписка или членство участвующего учреждения требуется.)
11. Эксендал, Б. К. (Бернт Карстен) (2003). Стохастические дифференциальные уравнения: введение с приложениями (6-е изд.). Берлин: Springer. ISBN  3540047581. OCLC  52203046.
12. Сорен Асмуссен (15 мая 2003 г.). Прикладная вероятность и очереди. Springer Science & Business Media. п. 7. ISBN  978-0-387-00211-8. В архиве из оригинала от 23 марта 2017 г.
13. Эмануэль Парзен (17 июня 2015 г.). Стохастические процессы. Courier Dover Publications. п. 188. ISBN  978-0-486-79688-8. В архиве с оригинала от 20 ноября 2017 г.
14. Сэмюэл Карлин; Ховард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. С. 29 и 30. ISBN  978-0-08-057041-9. В архиве из оригинала от 23 марта 2017 г.
15. Джон Ламперти (1977). Стохастические процессы: обзор математической теории. Springer-Verlag. С. 106–121. ISBN  978-3-540-90275-1. В архиве из оригинала от 23.03.2017.
16. Шелдон М. Росс (1996). Стохастические процессы. Вайли. С. 174 и 231. ISBN  978-0-471-12062-9. В архиве из оригинала от 23.03.2017.
17. Эверитт, Б.С. (2002) Кембриджский статистический словарь. КРУЖКА. ISBN  0-521-81099-X
18. Парзен, Э. (1962) Стохастические процессы, Холден-Дэй. ISBN  0-8162-6664-6 (Таблица 6.1)
19. Додж, Ю. (2003) Оксфордский словарь статистических терминов, ОУП. ISBN  0-19-920613-9 (запись для «цепи Маркова»)
20. Додж, Ю. Оксфордский словарь статистических терминов, ОУП. ISBN  0-19-920613-9
21. Мейн, С. Шон П. и Ричард Л. Твиди. (2009) Цепи Маркова и стохастическая устойчивость. Издательство Кембриджского университета. (Предисловие, стр. Iii)
22. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 159–163. ISBN  978-1-119-38755-8.
23. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 2–8. ISBN  978-1-119-38755-8.
24. Чарльз Миллер Гринстед; Джеймс Лори Снелл (1997). Введение в вероятность. American Mathematical Soc. стр.464 –466. ISBN  978-0-8218-0749-1.
25. Пьер Бремо (9 марта 2013 г.). Цепи Маркова: поля Гиббса, моделирование методом Монте-Карло и очереди. Springer Science & Business Media. п. ix. ISBN  978-1-4757-3124-8. В архиве из оригинала от 23 марта 2017 г.
26. Хейс, Брайан (2013). «Первые звенья в цепи Маркова». Американский ученый. 101 (2): 92–96. Дои:10.1511/2013.101.92.
27. Шелдон М. Росс (1996). Стохастические процессы. Вайли. С. 235 и 358. ISBN  978-0-471-12062-9. В архиве из оригинала от 23.03.2017.
28. Джарроу, Роберт; Проттер, Филипп (2004). «Краткая история стохастической интеграции и математических финансов: первые годы, 1880–1970». Festschrift для Германа Рубина. Конспект лекций Института математической статистики - Серия монографий. С. 75–91. CiteSeerX  10.1.1.114.632. Дои:10.1214 / lnms / 1196285381. ISBN  978-0-940600-61-4. ISSN  0749-2170.
29. Гутторп, Питер; Тораринсдоттир, Тордис Л. (2012). «Что случилось с дискретным хаосом, процессом Кенуй и резким марковским свойством? Некоторая история стохастических точечных процессов». Международный статистический обзор. 80 (2): 253–268. Дои:10.1111 / j.1751-5823.2012.00181.x. ISSN  0306-7734.
30. Сенета, Э. (1996). «Марков и рождение теории цепной зависимости». Международный статистический обзор / Revue Internationale de Statistique. 64 (3): 255–257. Дои:10.2307/1403785. ISSN  0306-7734. JSTOR  1403785.
31. Сенета, Э. (1998). «I.J. Bienaymé [1796–1878]: критичность, неравенство и интернационализация». Международный статистический обзор / Revue Internationale de Statistique. 66 (3): 291–292. Дои:10.2307/1403518. ISSN  0306-7734. JSTOR  1403518.
32. Бру Б, Герц С (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.
33. Kendall, D.G .; Бэтчелор, Г. К .; Bingham, N.H .; Hayman, W. K .; Hyland, J.M.E .; Lorentz, G.G .; Moffatt, H.K .; Парри, W .; Разборов, А. А .; Robinson, C.A .; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества. 22 (1): 33. Дои:10.1112 / blms / 22.1.31. ISSN  0024-6093.
34. Крамер, Харальд (1976). "Полвека теории вероятностей: некоторые личные воспоминания". Анналы вероятности. 4 (4): 509–546. Дои:10.1214 / aop / 1176996025. ISSN  0091-1798.
35. Марк Барбут; Бернард Локер; Лоран Мазляк (23 августа 2016 г.). Поль Леви и Морис Фреше: 50 лет переписки в 107 письмах. Springer London. п. 5. ISBN  978-1-4471-7262-8. В архиве из оригинала от 23 марта 2017 г.
36. Валерий Скороход (5 декабря 2005 г.). Основные принципы и приложения теории вероятностей. Springer Science & Business Media. п. 146. ISBN  978-3-540-26312-8. В архиве из оригинала от 23 марта 2017 г.
37. Бернштейн, Джереми (2005). «Башелье». Американский журнал физики. 73 (5): 395–398. Bibcode:2005AmJPh..73..395B. Дои:10.1119/1.1848117. ISSN  0002-9505.
38. Уильям Дж. Андерсон (6 декабря 2012 г.). Марковские цепи с непрерывным временем: подход, ориентированный на приложения. Springer Science & Business Media. п. vii. ISBN  978-1-4612-3038-0. В архиве из оригинала от 23 марта 2017 г.
39. Kendall, D.G .; Бэтчелор, Г. К .; Bingham, N.H .; Hayman, W. K .; Hyland, J.M.E .; Lorentz, G.G .; Moffatt, H.K .; Парри, W .; Разборов, А. А .; Robinson, C.A .; Уиттл, П. (1990). «Андрей Николаевич Колмогоров (1903–1987)». Бюллетень Лондонского математического общества. 22 (1): 57. Дои:10.1112 / blms / 22.1.31. ISSN  0024-6093.
40. Ионут Флореску (7 ноября 2014 г.). Вероятность и случайные процессы. Джон Вили и сыновья. С. 373 и 374. ISBN  978-1-118-59320-2. В архиве из оригинала от 23 марта 2017 г.
41. Сэмюэл Карлин; Ховард Э. Тейлор (2 декабря 2012 г.). Первый курс случайных процессов. Академическая пресса. п. 49. ISBN  978-0-08-057041-9. В архиве из оригинала от 23 марта 2017 г.
42. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 1–2. ISBN  978-1-119-38755-8.
43. Вайс, Джордж Х. (2006). «Случайные прогулки». Энциклопедия статистических наук. п. 1. Дои:10.1002 / 0471667196.ess2180.pub2. ISBN  978-0471667193.
44. Майкл Ф. Шлезингер (1985). Чудесный мир стохастики: дань уважения Эллиоту В. Монтроллю. Северная Голландия. С. 8–10. ISBN  978-0-444-86937-1. В архиве из оригинала от 23.03.2017.
45. Эмануэль Парзен (17 июня 2015 г.). Стохастические процессы. Courier Dover Publications. п. 7 и 8. ISBN  978-0-486-79688-8. В архиве из оригинала от 20 ноября 2017 г.
46. Джозеф Л. Дуб (1990). Стохастипоические процессы. Вайли. п. 46 и 47. В архиве из оригинала от 20.11.2017.
47. Дональд Л. Снайдер; Майкл И. Миллер (6 декабря 2012 г.). Случайные точечные процессы во времени и пространстве. Springer Science & Business Media. п. 32. ISBN  978-1-4612-3166-0. В архиве из оригинала от 20 ноября 2017 г.
48. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем I». Цепи Маркова. С. 60–107. Дои:10.1017 / CBO9780511810633.004. ISBN  9780511810633.
49. Серфозо, Ричард (2009). «Основы прикладных случайных процессов». Вероятность и ее приложения. Дои:10.1007/978-3-540-89332-5. ISBN  978-3-540-89331-8. ISSN  1431-7028.
50. "Глава 11" Цепи Маркова"" (PDF). В архиве (PDF) из оригинала на 2017-02-15. Получено 2017-06-02.
51. Шмитт, Флориан; Ротлауф, Франц (2001). «О важности второго по величине собственного значения для скорости сходимости генетических алгоритмов». Материалы 14-го симпозиума по надежным распределенным системам. CiteSeerX  10.1.1.28.6191.
52. Францке, Брэндон; Коско, Барт (1 октября 2011 г.). «Шум может ускорить сходимость в цепях Маркова». Физический обзор E. 84 (4): 041112. Bibcode:2011PhRvE..84d1112F. Дои:10.1103 / PhysRevE.84.041112. PMID  22181092.
53. Спитцер, Франк (1970). «Взаимодействие марковских процессов». Успехи в математике. 5 (2): 246–290. Дои:10.1016/0001-8708(70)90034-4.
54. Р. Л. Добрушин; В. И. Крилюков; А. Л. Тоом (1978). Стохастические клеточные системы: эргодичность, память, морфогенез. ISBN  9780719022067. В архиве из оригинала на 2017-02-05. Получено 2016-03-04.
55. Доблингер, Г. (сентябрь 1998 г.). «Сглаживание зашумленных сигналов AR с помощью адаптивного фильтра Калмана» (PDF). 9-я Европейская конференция по обработке сигналов (EUSIPCO 1998): 781–784.
56. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем II». Цепи Маркова. С. 108–127. Дои:10.1017 / CBO9780511810633.005. ISBN  9780511810633.
57. Мэтью Николь и Карл Петерсен, (2009) "Эргодическая теория: основные примеры и конструкции ",Энциклопедия сложности и системологии, Springer https://doi.org/10.1007/978-0-387-30440-3_177
58. Фитцпатрик, Ричард. «Термодинамика и статистическая механика» (PDF). В архиве (PDF) из оригинала на 30.11.2016. Получено 2017-06-02.
59. ван Равензваай, Дон; Кэсси, Пит; Браун, Скотт Д. (2016-03-11). "Простое введение в выборку методом Монте – Карло цепи Маркова". Психономический бюллетень и обзор. 25 (1): 143–154. Дои:10.3758 / s13423-016-1015-8. ISSN  1069-9384. ЧВК  5862921. PMID  26968853.
60. Райдер, Льюис Х. (1985). Квантовая теория поля. Кембридж [Кембриджшир]: Издательство Кембриджского университета. стр.160. ISBN  978-0521338592. OCLC  10533049.
61. Гаттрингер, Кристоф; Ланг, Кристиан Б. (2010). Квантовая хромодинамика на решетке.. Конспект лекций по физике. 788. Springer-Verlag Berlin Heidelberg. Дои:10.1007/978-3-642-01850-3. ISBN  978-3-642-01849-7. В архиве из оригинала от 01.08.2017.
62. Андерсон, Дэвид Ф .; Курц, Томас Г. (2011), "Модели цепей Маркова с непрерывным временем для сетей химических реакций", Дизайн и анализ биомолекулярных цепей, Springer New York, стр. 3–42, Дои:10.1007/978-1-4419-6766-4_1, ISBN  9781441967657
63. Ду, Чао; Коу, С.С. (сентябрь 2012 г.). «Корреляционный анализ ферментативной реакции отдельной белковой молекулы». Летопись прикладной статистики. 6 (3): 950–976. arXiv:1209.6210. Bibcode:2012arXiv1209.6210D. Дои:10.1214 / 12-aoas541. ISSN  1932-6157. ЧВК  3568780. PMID  23408514.
64. Кучукян, Петр; Лу, Дэвид; Шахнович, Евгений (2009). "FOG: Оптимизированный по фрагментам алгоритм роста для de Novo генерации молекул, содержащих лекарственные вещества". Журнал химической информации и моделирования. 49 (7): 1630–1642. Дои:10.1021 / ci9000458. PMID  19527020.
65. Кучукян, Петр С .; Лу, Дэвид; Шахнович, Евгений Иванович (15.06.2009). "FOG: Оптимизированный по фрагментам алгоритм роста для создания de Novo молекул, занимающих химическое пространство, подобное лекарству". Журнал химической информации и моделирования. 49 (7): 1630–1642. Дои:10.1021 / ci9000458. ISSN  1549-9596. PMID  19527020.
66. Копп, В. С .; Каганер, В. М .; Schwarzkopf, J .; Waidick, F .; Реммеле, Т .; Квасьневский, А .; Шмидбауэр, М. (2011). «Дифракция рентгеновских лучей от непериодических слоистых структур с корреляциями: Аналитический расчет и эксперимент на смешанных пленках Ауривиллиуса». Acta Crystallographica Раздел A. 68 (Pt 1): 148–155. Bibcode:2012AcCrA..68..148K. Дои:10.1107 / S0108767311044874. PMID  22186291.
67. Джордж, Дилип; Хокинс, Джефф (2009). Фристон, Карл Дж. (Ред.). «К математической теории корковых микросхем». PLOS Comput Biol. 5 (10): e1000532. Bibcode:2009PLSCB ... 5E0532G. Дои:10.1371 / journal.pcbi.1000532. ЧВК  2749218. PMID  19816557.
68. Гупта, Анкур; Роулингс, Джеймс Б. (апрель 2014 г.). «Сравнение методов оценки параметров в стохастических химических кинетических моделях: примеры в системной биологии». Журнал Айше. 60 (4): 1253–1268. Дои:10.1002 / aic.14409. ЧВК  4946376. PMID  27429455.
69. Aguiar, R.J .; Collares-Pereira, M .; Конде, Дж. П. (1988). «Простая процедура генерации последовательностей суточных значений радиации с использованием библиотеки матриц марковских переходов». Солнечная энергия. 40 (3): 269–279. Bibcode:1988Соэн ... 40..269A. Дои:10.1016 / 0038-092X (88) 90049-7.
70. Ngoko, B.O .; Sugihara, H .; Фунаки, Т. (2014). «Синтетическая генерация данных солнечного излучения с высоким временным разрешением с использованием марковских моделей». Солнечная энергия. 103: 160–170. Bibcode:2014СоЭн..103..160N. Дои:10.1016 / j.solener.2014.02.026.
71. Bright, J.M .; Smith, C.I .; Taylor, P.G .; Крук, Р. (2015). «Стохастическая генерация синтетических временных рядов минутной освещенности, полученных из среднечасовых данных наблюдений за погодой». Солнечная энергия. 115: 229–242. Bibcode:2015СоЭн..115..229B. Дои:10.1016 / j.solener.2015.02.032.
72. Munkhammar, J .; Виден, Дж. (2018). "Модель распределения N-состояний смеси марковских цепей индекса ясности". Солнечная энергия. 173: 487–495. Bibcode:2018СоЭн..173..487 млн. Дои:10.1016 / j.solener.2018.07.056.
73. Морф, Х. (1998). «Стохастическая двухуровневая модель солнечного излучения (STSIM)». Солнечная энергия. 62 (2): 101–112. Bibcode:1998SoEn ... 62..101M. Дои:10.1016 / S0038-092X (98) 00004-8.
74. Munkhammar, J .; Виден, Дж. (2018). "Подход смеси распределения вероятностей цепи Маркова к индексу ясного неба". Солнечная энергия. 170: 174–183. Bibcode:2018СоЭн..170..174 млн. Дои:10.1016 / j.solener.2018.05.055.
75. Пратас, Д; Silva, R; Пинхо, А; Феррейра, П. (18 мая 2015 г.). «Метод без выравнивания для поиска и визуализации перестроек между парами последовательностей ДНК». Научные отчеты. 5 (10203): 10203. Bibcode:2015НатСР ... 510203П. Дои:10.1038 / srep10203. ЧВК  4434998. PMID  25984837.
76. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф., «Марковская цепь», Архив истории математики MacTutor, Сент-Эндрюсский университет.
77. С. П. Мейн, 2007. Методы управления сложными сетями В архиве 2015-05-13 на Wayback Machine, Издательство Кембриджского университета, 2007.
78. Патент США 6,285,999
79. Гупта, Бридж; Agrawal, Dharma P .; Ямагути, Синго (16 мая 2016 г.). Справочник по исследованиям современных криптографических решений для компьютерной и кибербезопасности. IGI Global. С. 448–. ISBN  978-1-5225-0106-0. В архиве из оригинала от 23 марта 2017 г.
80. Langville, Amy N .; Мейер, Карл Д. (2006). "Переупорядочение проблемы PageRank" (PDF). Журнал SIAM по научным вычислениям. 27 (6): 2112–2113. CiteSeerX  10.1.1.58.8652. Дои:10.1137/040607551. ISSN  1064-8275. В архиве (PDF) из оригинала от 21.09.2017.
81. Пейдж, Лоуренс; Брин, Сергей; Мотвани, Раджив; Виноград, Терри (1999). Рейтинг цитирования PageRank: наведение порядка в Интернете (Технический отчет). CiteSeerX  10.1.1.31.1768.
82. Prasad, NR; RC Ender; ST Reilly; Г. Несгос (1974). «Распределение ресурсов по минимальной стоимости». 1974 Конференция IEEE по принятию решений и контролю, включая 13-й симпозиум по адаптивным процессам. 13: 402–3. Дои:10.1109 / CDC.1974.270470.
83. Гамильтон, Джеймс (1989). «Новый подход к экономическому анализу нестационарных временных рядов и бизнес-цикла». Econometrica. 57 (2): 357–84. CiteSeerX  10.1.1.397.3582. Дои:10.2307/1912559. JSTOR  1912559.
84. Calvet, Laurent E .; Фишер, Адлай Дж. (2001). «Прогнозирование мультифрактальной волатильности». Журнал эконометрики. 105 (1): 27–58. Дои:10.1016 / S0304-4076 (01) 00069-0. S2CID  119394176.
85. Кальве, Лоран; Адлай Фишер (2004). «Как прогнозировать долгосрочную волатильность: переключение режимов и оценка мультифрактальных процессов». Журнал финансовой эконометрики. 2: 49–83. CiteSeerX  10.1.1.536.8334. Дои:10.1093 / jjfinec / nbh003. S2CID  6020401.
86. Бреннан, Майкл; Сяб, Ихонг. «Волатильность курса акций и премия за акции» (PDF). Департамент финансов, Школа менеджмента Андерсона, Калифорнийский университет в Лос-Анджелесе. Архивировано из оригинал (PDF) на 2008-12-28.
87. «Пример цепи Маркова в моделировании кредитного риска, лекции Колумбийского университета» (PDF). Архивировано из оригинал (PDF) 24 марта 2016 г.
88. Аджемоглу, Дарон; Георгий Егоров; Константин Сонин (2011). «Политическая модель социальной эволюции». Труды Национальной академии наук. 108: 21292–21296. Bibcode:2011PNAS..10821292A. CiteSeerX  10.1.1.225.6090. Дои:10.1073 / pnas.1019454108. ЧВК  3271566. PMID  22198760. Архивировано из оригинал 15 апреля 2013 г.
89. К. Макальпайн; Э. Миранда; С. Хоггар (1999). «Создание музыки с помощью алгоритмов: система изучения конкретного случая». Компьютерный музыкальный журнал. 23 (2): 19–30. Дои:10.1162/014892699559733. S2CID  40057162.
90. Curtis Roads (редактор) (1996). Учебник компьютерной музыки. MIT Press. ISBN  978-0-262-18158-7.
91. Ксенакис, Яннис; Канач, Шарон (1992) Формализованная музыка: математика и мысль в композиции, Pendragon Press. ISBN  1576470792
92. «Континуатор». Архивировано из оригинал 13 июля 2012 г.
93. Pachet, F .; Рой, П .; Барбьери, Г. (2011) «Конечные марковские процессы с ограничениями» В архиве 2012-04-14 в Wayback Machine, Материалы 22-й Международной совместной конференции по искусственному интеллекту, IJCAI, страницы 635–642, Барселона, Испания, июль 2011 г.
94. Панкин, Марк Д. «МАРКОВСКИЕ ЦЕПНЫЕ МОДЕЛИ: ТЕОРЕТИЧЕСКИЕ ОСНОВЫ». Архивировано из оригинал на 2007-12-09. Получено 2007-11-26.
95. Панкин, Марк Д. "БЕЙСБОЛ КАК МАРКОВСКАЯ ЦЕПЬ". В архиве из оригинала 13.05.2009. Получено 2009-04-24.
96. "Уголок поэта - Фьералинг". Архивировано из оригинал 6 декабря 2010 г.
97. Кеннер, Хью; О'Рурк, Джозеф (Ноябрь 1984 г.). «Генератор пародий на микросхемы». БАЙТ. 9 (12): 129–131, 449–469.
98. Хартман, Чарльз (1996). Виртуальная муза: эксперименты в компьютерной поэзии. Ганновер, Нью-Хэмпшир: издательство Уэслианского университета. ISBN  978-0-8195-2239-9.
99. de Souza e Silva, E.G .; Legey, L.F.L .; де Соуза и Сильва, Э.А. (2010). «Прогнозирование динамики цен на нефть с использованием вейвлетов и скрытых марковских моделей». Экономика энергетики. 32.
100. Карпинон, А; Джорджио, М; Langella, R .; Теста, А. (2015). «Моделирование цепей Маркова для краткосрочного прогнозирования ветроэнергетики». Исследование электроэнергетических систем. 122: 152–158. Дои:10.1016 / j.epsr.2014.12.025.
101. Munkhammar, J .; van der Meer, D.W .; Виден, Дж. (2019). «Вероятностное прогнозирование временных рядов индекса ясного неба с высоким разрешением с использованием модели распределения смеси цепей Маркова». Солнечная энергия. 184: 688–695. Bibcode:2019СоЭн..184..688M. Дои:10.1016 / j.solener.2019.04.014.

использованная литература

• Марков А.А. (1906) "Распространение закона больших зубил на величины, зависящие от других наркотиков". Известия Физико-математического общества при Казанском университете., 2-я серия, том 15, с. 135–156.
• Марков А.А. (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, соединенных в цепочку». перепечатано в Приложении B к: R. Howard. Динамические вероятностные системы, том 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) Марковские цепи и стохастическая устойчивость. Лондон: Springer-Verlag ISBN  0-387-19832-6. онлайн: MCSS . Выйдет второе издание, Cambridge University Press, 2009.
• С. П. Мейн. Методы управления сложными сетями. Издательство Кембриджского университета, 2007. ISBN  978-0-521-88441-9. Приложение содержит сокращенную версию Meyn & Tweedie. онлайн: [1]
• Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов (1-е изд.). Нью-Йорк, штат Нью-Йорк: John Wiley and Sons, Inc., Каталог карточек Библиотеки Конгресса, номер 67-25924. ] Обширная, обширная книга, предназначенная для специалистов, написанная как для теоретиков информатики, так и для инженеров-электриков. С подробным объяснением методов минимизации состояний, автоматов Тьюринга, марковских процессов и неразрешимости. Отличная обработка марковских процессов с. 449ff. Обсуждает Z-преобразования, D-преобразования в их контексте.
• Кемени, Джон Дж .; Хэзлтон Миркил; Дж. Лори Снелл; Джеральд Л. Томпсон (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, Инк. Номер каталога карточек Библиотеки Конгресса 59-12841. Классический текст. cf Глава 6 Конечные цепи Маркова стр. 384ff.
• Джон Г. Кемени & Дж. Лори Снелл (1960) Конечные цепи Маркова, D. van Nostrand Company 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.
• К. С. Триведи и Р. А. Санер, ШАРП в возрасте двадцати двух лет, т. 36, нет. 4, стр. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
• Р. А. Санер, К. С. Триведи и А. Пулиафито, Анализ производительности и надежности компьютерных систем: подход на основе примеров с использованием программного пакета SHARPE, Kluwer Academic Publishers, 1996. ISBN  0-7923-9650-2.
• Г. Болч, С. Грейнер, Х. де Меер и К. С. Триведи, Сети массового обслуживания и цепи Маркова, Джон Вили, 2-е издание, 2006 г. ISBN  978-0-7923-9650-5.

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

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