Цепь Маркова или Марковский процесс — это стохастическая модель , описывающая последовательность возможных событий, в которой вероятность каждого события зависит только от состояния, достигнутого в предыдущем событии. [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]
Предположим, что имеется кошелек для монет, содержащий пять четвертаков (каждая по 25 центов), пять десятицентовиков (каждая по 10 центов) и пять пятицентовых монет (каждая по 5 центов), и одна за другой монеты случайным образом вытягиваются из кошелька и поставил на стол. Если представляет собой общую стоимость монет, выставленных на столе после n розыгрышей, с , то последовательность не является марковским процессом.
Чтобы понять, почему это так, предположим, что в первых шести розыгрышах выпадают все пять пятаков с четвертью. Таким образом . Если мы знаем не только , но и предыдущие значения, то мы можем определить, какие монеты были вытянуты, и знаем, что следующая монета не будет пятицентовой монетой; поэтому мы можем определить это с вероятностью 1. Но если мы не знаем более ранние значения, то, основываясь только на значении, мы могли бы догадаться, что мы вытянули четыре десятицентовика и две пятицентовые монеты, и в этом случае, безусловно, можно было бы вытянуть еще одну пятаковую монету. следующий. Таким образом, на наши предположения о . влияют наши знания о значениях до .
Однако этот сценарий можно смоделировать как марковский процесс. Вместо определения общей стоимости монет в таблице мы могли бы определить количество монет различных типов в таблице. Например, может быть определен для обозначения состояния, в котором после 6 розыгрышей один за другим на столе находится один четвертак, ноль десятицентовиков и пять пятаков. Эта новая модель может быть представлена возможными состояниями, где каждое состояние представляет количество монет каждого типа (от 0 до 5), находящихся на столе. (Не все из этих состояний достижимы за 6 розыгрышей.) Предположим, что первый розыгрыш приводит к состоянию . Вероятность достижения теперь зависит от ; например, состояние невозможно. После второго розыгрыша третий розыгрыш зависит от того, какие монеты уже были вытянуты, а не только от монет, которые были вытянуты для первого состояния (поскольку с тех пор в сценарий была добавлена вероятностно важная информация). Таким образом, вероятность состояния зависит исключительно от исхода состояния .
Цепь Маркова с дискретным временем представляет собой последовательность случайных величин X 1 , X 2 , X 3 , ... со свойством Маркова , а именно, что вероятность перехода в следующее состояние зависит только от текущего состояния, а не от предыдущего. состояния:
Возможные значения X i образуют счетное множество S , называемое пространством состояний цепи.
Цепь Маркова с непрерывным временем ( X t ) t ≥ 0 определяется конечным или счетным пространством состояний S , матрицей скорости перехода Q с размерами, равными размерам пространства состояний, и начальным распределением вероятностей, определенным в пространстве состояний. Для i ≠ j элементы q ij неотрицательны и описывают скорость переходов процесса из состояния i в состояние j . Элементы q ii выбираются так, чтобы сумма каждой строки матрицы скорости перехода была равна нулю, а суммы строк матрицы вероятностного перехода в (дискретной) цепи Маркова были равны единице.
Существует три эквивалентных определения этого процесса. [49]
Пусть это случайная величина, описывающая состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . Тогда, зная , не зависит от предыдущих значений и при h → 0 для всех j и для всех t ,
Определите цепь Маркова Y n с дискретным временем для описания n -го скачка процесса и переменные S 1 , S 2 , S 3 , ... для описания времени удержания в каждом из состояний, где Si следует экспоненциальному распределению со скоростью параметр - q Y я Y я .
Для любого значения n = 0, 1, 2, 3, ... и времен, проиндексированных до этого значения n : t 0 , t 1 , t 2 , ... и всех состояний, записанных в эти моменты времени i 0 , i 1 , i 2 , i 3 , ... верно, что
где p ij — решение прямого уравнения ( дифференциальное уравнение первого порядка )
с начальным условием P(0) – единичная матрица .
Если пространство состояний конечно , распределение вероятностей перехода может быть представлено матрицей , называемой матрицей перехода, с ( i , j )-м элементом P , равным
Поскольку сумма каждой строки P равна одному и все элементы неотрицательны, P является правой стохастической матрицей .
Стационарное распределение π — это вектор (строка), элементы которого неотрицательны и имеют сумму, равную 1, не изменяются в результате действия на нем матрицы перехода P и поэтому определяются выражением
Сравнивая это определение с определением собственного вектора , мы видим, что эти два понятия связаны и что
является нормализованным ( ), кратным левому собственному вектору e матрицы перехода P с собственным значением 1. Если существует более одного единичного собственного вектора, то взвешенная сумма соответствующих стационарных состояний также является стационарным состоянием. Но для цепи Маркова обычно больше интересует стационарное состояние, которое является пределом последовательности распределений для некоторого начального распределения.
Значения стационарного распределения связаны с пространством состояний P , и его собственные векторы сохраняют свои относительные пропорции. Поскольку компоненты π положительны, и ограничение, согласно которому их сумма равна единице, можно переписать, поскольку мы видим, что скалярное произведение π с вектором, все компоненты которого равны 1, равно единице и что π лежит на симплексе .
Если цепь Маркова однородна во времени, то матрица перехода P одинакова после каждого шага, поэтому вероятность перехода на k -шаге может быть вычислена как k -я степень матрицы перехода, P k .
Если цепь Маркова неприводима и апериодична, то существует единственное стационарное распределение π . [50] Кроме того, в этом случае P k сходится к матрице ранга один, в которой каждая строка представляет собой стационарное распределение π :
где 1 — вектор-столбец со всеми элементами, равными 1. Это утверждается теоремой Перрона-Фробениуса . Если каким-либо образом оно найдено, то стационарное распределение рассматриваемой цепи Маркова можно легко определить для любого начального распределения, как будет объяснено ниже.
Для некоторых стохастических матриц P предел не существует, в то время как стационарное распределение существует, как показано в этом примере:
(Этот пример иллюстрирует периодическую цепь Маркова.)
Поскольку необходимо учитывать ряд различных особых случаев, процесс нахождения этого предела, если он существует, может оказаться длительной задачей. Однако существует множество методов, которые могут помочь найти этот предел. Пусть P — матрица размера n × n и определим
Это всегда правда, что
Вычитание Q из обеих сторон и факторизация дают
где 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 )] −1 существует, то [51] [50]
Следует отметить, что если P имеет элемент Pi, i на своей главной диагонали , который равен 1, а i -я строка или столбец в противном случае заполнена нулями, то эта строка или столбец останутся неизменными во всех последующих мощности P k . Следовательно, i -я строка или столбец Q будет иметь 1 и 0 в тех же позициях, что и в P .
Как говорилось ранее, из уравнения (если оно существует) стационарное (или установившееся) распределение π является левым собственным вектором стохастической матрицы строки P . Тогда, предполагая, что P диагонализуемо или, что то же самое, что P имеет n линейно независимых собственных векторов, скорость сходимости определяется следующим образом. (Для недиагонализуемых, то есть дефектных матриц , можно начать с жордановой нормальной формы P и продолжить аналогичным образом с немного более сложным набором аргументов. [52]
Пусть U — матрица собственных векторов (каждый из которых нормирован на норму L2, равную 1), где каждый столбец — левый собственный вектор P , и пусть Σ — диагональная матрица левых собственных значений P , то есть Σ = Diag( λ 1 , λ 2 , λ 3 ,..., λ n ). Тогда по собственному разложению
Пусть собственные значения пронумерованы так, что:
Поскольку P — стохастическая матрица-строка, ее наибольшее левое собственное значение равно 1. Если существует уникальное стационарное распределение, то наибольшее собственное значение и соответствующий собственный вектор также уникальны (поскольку не существует другого π , которое решает приведенное выше уравнение стационарного распределения). Пусть u i — i -й столбец матрицы U , то есть u i — левый собственный вектор матрицы P , соответствующий λ i . Также пусть x будет вектором-строкой длины n , который представляет допустимое распределение вероятностей; поскольку собственные векторы u i охватывают, мы можем написать
Если мы умножим x на P справа и продолжим эту операцию с результатами, в конце концов мы получим стационарное распределение π . Другими словами, π = a 1 u 1 ← xPP ... P = xP k при k → ∞. Это значит
Поскольку π параллелен u 1 (нормирован по норме L2) и π ( k ) — вектор вероятности, π ( k ) приближается к a 1 u 1 = π при k → ∞ со скоростью порядка λ 2 / λ 1 экспоненциально. Это следует из того, что, следовательно, λ 2 / λ 1 является доминирующим термином. Чем меньше это отношение, тем быстрее происходит сходимость. [53] Случайный шум в распределении состояний π также может ускорить сходимость к стационарному распределению. [54]
Многие результаты для цепей Маркова с конечным пространством состояний можно обобщить на цепи с несчетным пространством состояний через цепи Харриса .
Использование цепей Маркова в методах Монте-Карло с цепями Маркова охватывает случаи, когда процесс следует непрерывному пространству состояний.
Рассмотрение совокупности цепей Маркова, эволюция которых учитывает состояние других цепей Маркова, связано с понятием локально взаимодействующих цепей Маркова. Это соответствует ситуации, когда пространство состояний имеет (декартову) форму произведения. См . взаимодействующую систему частиц и стохастические клеточные автоматы (вероятностные клеточные автоматы). См., например, «Взаимодействие марковских процессов» [55] или. [56]
Говорят, что два состояния взаимодействуют друг с другом, если оба состояния достижимы друг из друга посредством последовательности переходов, имеющих положительную вероятность. Это отношение эквивалентности, которое дает набор взаимодействующих классов. Класс считается закрытым , если вероятность выхода из класса равна нулю. Цепь Маркова неприводима, если существует один взаимодействующий класс — пространство состояний.
Состояние i имеет период k , если k — наибольший общий делитель числа переходов, с помощью которых можно достичь i, начиная с i . То есть:
Состояние i называется переходным, если , начиная с i , существует ненулевая вероятность того, что цепочка никогда не вернется в i . В противном случае его называют рекуррентным (или постоянным ). [57] Для повторяющегося состояния i среднее время попадания определяется как:
Состояние i является положительно рекуррентным, если оно конечно, и нулевым рекуррентным в противном случае. Периодичность, быстротечность, повторяемость, а также положительная и нулевая повторяемость являются свойствами класса, то есть, если одно состояние обладает этим свойством, то все состояния в его взаимодействующем классе обладают этим свойством. [58]
Состояние i называется поглощающим, если из него нет исходящих переходов.
Поскольку периодичность является свойством класса, если цепь Маркова неприводима, то все ее состояния имеют одинаковый период. В частности, если одно состояние апериодично, то апериодична и вся цепь Маркова.
Если конечная цепь Маркова неприводима, то все состояния положительно рекуррентны и имеют единственное стационарное распределение, заданное формулой .
Состояние i называется эргодическим , если оно апериодично и положительно рекуррентно. Другими словами, состояние i является эргодическим, если оно рекуррентно, имеет период 1 и имеет конечное среднее время возврата.
Если все состояния неприводимой цепи Маркова эргодичны, то цепь называется эргодической. Эквивалентно, существует некоторое целое число , все элементы которого положительны.
Можно показать, что неприводимая цепь Маркова с конечным состоянием является эргодической, если она имеет апериодическое состояние. В более общем смысле, цепь Маркова является эргодической, если существует число N такое, что любое состояние может быть достигнуто из любого другого состояния за любое количество шагов, меньшее или равное числу N. В случае полносвязной матрицы переходов, где все переходы имеют ненулевую вероятность, это условие выполняется при N = 1.
Цепь Маркова с более чем одним состоянием и только одним исходящим переходом на каждое состояние либо не является неприводимой, либо не апериодической, следовательно, не может быть эргодической.
Некоторые авторы называют любые неприводимые положительные рекуррентные цепи Маркова эргодическими и даже периодическими. [59] Фактически, просто неприводимые цепи Маркова соответствуют эргодическим процессам, определенным в соответствии с эргодической теорией. [60]
Некоторые авторы называют матрицу примитивной тогда и только тогда, когда существует некоторое целое число , все элементы которого положительны. [61] Некоторые авторы называют его регулярным . [62]
Индекс примитивности , или экспонента , регулярной матрицы является наименьшим из таких, в которых все элементы положительны. Экспонента является чисто теоретико-графовым свойством, поскольку она зависит только от того, равна ли каждая запись нулю или положительному значению, и, следовательно, ее можно найти на ориентированном графе с матрицей смежности.
Есть несколько комбинаторных результатов об показателе степени, когда состояний конечное число. Пусть – число состояний, тогда [63]
Если цепь Маркова имеет стационарное распределение, то ее можно преобразовать в динамическую систему, сохраняющую меру : Пусть вероятностное пространство равно , где – множество всех состояний цепи Маркова. Пусть сигма-алгебра в вероятностном пространстве порождается цилиндрическими множествами. Пусть вероятностная мера порождается стационарным распределением и переходом цепи Маркова. Пусть – оператор сдвига: . Аналогично мы можем построить такую динамическую систему вместо этого. [65]
Поскольку неприводимые цепи Маркова с конечными пространствами состояний имеют единственное стационарное распределение, приведенная выше конструкция однозначна для неприводимых цепей Маркова.
В эргодической теории сохраняющая меру динамическая система называется «эргодической» тогда и только тогда, когда любое измеримое подмножество такое, что подразумевает или (с точностью до нулевого множества).
Терминология противоречива. Учитывая цепь Маркова со стационарным распределением, строго положительным во всех состояниях, цепь Маркова неприводима тогда и только тогда, когда соответствующая ей сохраняющая меру динамическая система эргодична . [60]
В некоторых случаях явно немарковские процессы все же могут иметь марковские представления, построенные путем расширения понятия «текущего» и «будущего» состояний. Например, пусть X — немарковский процесс. Затем определите процесс Y так, чтобы каждое состояние Y представляло временной интервал состояний X. Математически это имеет вид:
Если Y обладает марковским свойством, то это марковское представление X.
Примером немарковского процесса с марковским представлением является авторегрессионный временной ряд порядка больше единицы. [66]
Время попадания — это время, начиная с данного набора состояний и до тех пор, пока цепочка не достигнет данного состояния или набора состояний. Распределение такого периода времени имеет распределение фазового типа. Простейшим таким распределением является распределение одного экспоненциально распределенного перехода.
Для подмножества состояний A ⊆ S вектор k A времен попадания (где элемент представляет ожидаемое значение , начиная с состояния i , когда цепь входит в одно из состояний в наборе A ) является минимальным неотрицательным решением [ 67]
Для CTMC X t обращенный во времени процесс определяется как . По лемме Келли этот процесс имеет такое же стационарное распределение, как и прямой процесс.
Цепь называется обратимой, если обратный процесс аналогичен прямому процессу. Критерий Колмогорова утверждает, что необходимым и достаточным условием обратимости процесса является то, что произведение скоростей перехода по замкнутому контуру должно быть одинаковым в обоих направлениях.
Одним из методов нахождения стационарного распределения вероятностей π эргодической цепи Маркова Q с непрерывным временем является сначала нахождение ее встроенной цепи Маркова (EMC) . Строго говоря, ЭМС представляет собой регулярную цепь Маркова с дискретным временем, иногда называемую скачкообразным процессом . Каждый элемент матрицы вероятности одношагового перехода EMC, S , обозначается sij и представляет собой условную вероятность перехода из состояния i в состояние j . Эти условные вероятности можно найти с помощью
Отсюда S можно записать как
где I — единичная матрица , а Diag( Q ) — диагональная матрица , сформированная путем выбора главной диагонали из матрицы Q и установки всех остальных элементов в ноль.
Чтобы найти стационарный вектор распределения вероятностей, мы должны затем найти такое, что
будучи вектором-строкой, в котором все элементы больше 0 и = 1. Отсюда π можно найти как
( S может быть периодическим, даже если Q нет. Как только π найдено, его необходимо нормализовать на единичный вектор .)
Другой процесс с дискретным временем, который может быть получен из цепи Маркова с непрерывным временем, - это δ-скелет - цепь Маркова (с дискретным временем), образованная путем наблюдения X ( t ) с интервалами в δ единиц времени. Случайные величины X (0), X (δ), X (2δ),... задают последовательность состояний, которые посещает δ-скелет.
Марковские модели используются для моделирования изменяющихся систем. Существует 4 основных типа моделей, которые обобщают цепи Маркова в зависимости от того, является ли каждое последовательное состояние наблюдаемым или нет, и подлежит ли система корректировке на основе сделанных наблюдений:
Схема Бернулли — это частный случай цепи Маркова, где матрица вероятностей перехода имеет одинаковые строки, а это означает, что следующее состояние не зависит даже от текущего состояния (помимо независимости от прошлых состояний). Схема Бернулли, имеющая только два возможных состояния, известна как процесс Бернулли .
Однако заметим, что по теореме Орнштейна об изоморфизме каждая апериодическая и неприводимая цепь Маркова изоморфна схеме Бернулли; Таким образом, [68] можно с таким же успехом утверждать, что цепи Маркова являются «частным случаем» схем Бернулли. Изоморфизм обычно требует сложной перекодировки. Теорема об изоморфизме даже немного сильнее: она утверждает, что любой стационарный случайный процесс изоморфен схеме Бернулли; Цепь Маркова — лишь один из таких примеров.
Когда матрица Маркова заменяется матрицей смежности конечного графа , результирующий сдвиг называется топологической цепью Маркова или подсдвигом конечного типа . [68] Марковская матрица, совместимая с матрицей смежности, может затем обеспечить измерение подсдвига . Многие хаотические динамические системы изоморфны топологическим цепям Маркова; примеры включают диффеоморфизмы замкнутых многообразий , систему Пруэ-Туэ-Морса , систему Чакона, софические системы , контекстно-свободные системы и системы блочного кодирования. [68]
Исследования показали применение и полезность цепей Маркова в широком спектре тем, таких как физика, химия, биология, медицина, музыка, теория игр и спорт.
Марковские системы широко появляются в термодинамике и статистической механике всякий раз, когда вероятности используются для представления неизвестных или немоделированных деталей системы, если можно предположить, что динамика инвариантна во времени и что нет необходимости учитывать какую-либо соответствующую историю, которая еще не включена. в описании штата. [69] [70] Например, термодинамическое состояние действует в соответствии с распределением вероятностей, которое трудно или дорого получить. Следовательно, метод Монте-Карло цепи Маркова можно использовать для случайного отбора выборок из черного ящика для аппроксимации распределения вероятностей атрибутов по ряду объектов. [70]
Пути в формулировке квантовой механики с интегралом по путям представляют собой цепи Маркова. [71]
Цепи Маркова используются в решеточном моделировании КХД . [72]
Реакционная сеть — это химическая система, включающая множество реакций и химических веществ. Простейшие стохастические модели таких сетей рассматривают систему как цепь Маркова с непрерывным временем, где состояние представляет собой количество молекул каждого вида, а реакции моделируются как возможные переходы цепи. [73] Цепи Маркова и марковские процессы с непрерывным временем полезны в химии, когда физические системы близко приближаются к свойству Маркова. Например, представьте себе большое количество n молекул в растворе в состоянии А, каждая из которых может вступать в химическую реакцию с переходом в состояние Б с определенной средней скоростью. Возможно, молекула представляет собой фермент, а состояния относятся к тому, как она свернута. Состояние любого отдельного фермента следует цепи Маркова, и поскольку молекулы по существу независимы друг от друга, количество молекул в состоянии A или B одновременно в n раз превышает вероятность того, что данная молекула находится в этом состоянии.
Классическую модель активности фермента, кинетику Михаэлиса-Ментен , можно рассматривать как цепь Маркова, где на каждом временном этапе реакция протекает в определенном направлении. Хотя метод Михаэлиса-Ментена довольно прост, с помощью цепей Маркова можно смоделировать и гораздо более сложные реакционные сети. [74]
Алгоритм, основанный на цепи Маркова, также использовался для фокусировки фрагментарного роста химических веществ in silico на желаемый класс соединений, таких как лекарства или натуральные продукты. [75] По мере роста молекулы из зарождающейся молекулы выбирается фрагмент в качестве «текущего» состояния. Он не осознает своего прошлого (то есть не осознает того, что уже с ним связано). Затем он переходит в следующее состояние, когда к нему присоединяется фрагмент. Вероятности перехода обучаются на базах данных аутентичных классов соединений. [76]
Кроме того, рост (и состав) сополимеров можно моделировать с помощью цепей Маркова. На основании соотношений реакционной способности мономеров, составляющих растущую полимерную цепь, можно рассчитать состав цепи (например, имеют ли мономеры тенденцию добавляться поочередно или в виде длинных серий одного и того же мономера). Из-за стерических эффектов в росте некоторых полимерных цепей также могут играть роль эффекты Маркова второго порядка.
Точно так же было высказано предположение, что кристаллизация и рост некоторых эпитаксиальных оксидных материалов со сверхрешеткой могут быть точно описаны цепями Маркова. [77]
Цепи Маркова используются в различных областях биологии. Яркие примеры включают:
Несколько теоретиков предложили идею статистического теста цепей Маркова (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 веб-страницы, используемый Google, определяется цепью Маркова. [89] [90] [91] Это вероятность оказаться на странице в стационарном распределении следующей цепи Маркова на всех (известных) веб-страницах. Если это количество известных веб-страниц и на странице есть ссылки на нее, то существует вероятность перехода для всех страниц, на которые есть ссылки, и для всех страниц, на которые нет ссылок. Параметр принят равным примерно 0,15. [92]
Модели Маркова также использовались для анализа поведения пользователей в веб-навигации. Переход пользователя по веб-ссылке на конкретном веб-сайте можно смоделировать с использованием моделей Маркова первого или второго порядка и использовать для прогнозирования будущей навигации и персонализации веб-страницы для отдельного пользователя.
Методы цепей Маркова также стали очень важными для генерации последовательностей случайных чисел, которые точно отражают очень сложные желаемые распределения вероятностей, с помощью процесса, называемого цепью Маркова Монте-Карло (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]