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

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

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

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

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

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

Вступление

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

Определение

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

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

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

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

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

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

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

Переходы

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

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

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

История

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

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

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

Примеры

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

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

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

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

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

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

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

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

Чтобы понять, почему это так, предположим, что в первых шести розыгрышах разыгрываются все пять пятак и четверть. Итак . Если мы знаем не только , но и более ранние значения, то мы можем определить, какие монеты были вытянуты, и мы знаем, что следующая монета не будет никелем; так что мы можем определить это с вероятностью 1. Но если мы не знаем более ранние значения, то, основываясь только на этом значении, мы можем предположить, что мы вытащили четыре цента и два цента, и в этом случае, безусловно, можно было бы взять еще один никель. следующий. Таким образом, на наши предположения влияет наше знание ценностей до .

Однако можно смоделировать этот сценарий как марковский процесс. Вместо определения , чтобы представить общую стоимость монет на столе, мы могли бы определить , чтобы представить количество различных типов монет на столе. Например, можно определить состояние, в котором на столе остается одна четверть, ноль десятицентовиков и пять пятак после 6 розыгрышей по одному. Эта новая модель будет представлена ​​216 возможными состояниями (то есть состояниями 6x6x6, поскольку каждый из трех типов монет может иметь от нуля до пяти монет на столе к концу 6 розыгрышей). Предположим, что первый розыгрыш приводит к состоянию . Вероятность достижения сейчас зависит от ; например, состояние невозможно. После второго розыгрыша третий розыгрыш зависит от того, какие монеты были разыграны на данный момент, но уже не только от монет, которые были разыграны для первого состояния (поскольку с тех пор в сценарий была добавлена ​​вероятностно важная информация). Таким образом, вероятность состояния зависит исключительно от результата состояния.

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

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

Марковская цепь с дискретным временем - это последовательность случайных величин X 1 , X 2 , X 3 , ... со свойством Маркова , а именно, что вероятность перехода к следующему состоянию зависит только от текущего состояния, а не от предыдущего. состояния:

если обе условные вероятности хорошо определены, то есть если

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

Вариации

  • Однородные по времени цепи Маркова - это процессы, в которых
    для всех п . Вероятность перехода не зависит от n .
  • Стационарные цепи Маркова - это процессы, в которых
    для всех n и k . Каждую стационарную цепь можно доказать однородностью по времени с помощью правила Байеса.
    Необходимым и достаточным условием стационарности однородной по времени цепи Маркова является то, что распределение является стационарным распределением цепи Маркова.
  • Цепь Маркова с памятью (или цепь Маркова порядка m ), где m конечно, - это процесс, удовлетворяющий
    Другими словами, будущее состояние зависит от прошлых m состояний. Можно построить цепочку из которых имеет «классическое» марковское свойство, взяв в качестве пространства состояний упорядоченных м -грамм из X значений, то есть .

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

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

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

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

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

Пусть будет случайной величиной, описывающей состояние процесса в момент времени t , и предположим, что процесс находится в состоянии i в момент времени t . Тогда, зная , не зависит от предыдущих значений , и при h → 0 для всех j и всех t ,

,

где - дельта Кронекера , используя обозначение small-o . Можно рассматривать как измерения , как быстро переход от I к J происходит.

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

Задайте цепь Маркова Y n с дискретным временем для описания n- го скачка процесса и переменные S 1 , S 2 , S 3 , ... для описания времени удержания в каждом из состояний, где S i следует экспоненциальному распределению со скоростью параметр - q Y i Y i .

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

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

где p ij - решение прямого уравнения ( дифференциального уравнения первого порядка )

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

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

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

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

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

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

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

является нормированным ( ) кратным левого собственного вектора e матрицы перехода P с собственным значением 1. Если имеется более одного единичного собственного вектора, то взвешенная сумма соответствующих стационарных состояний также является стационарным состоянием. Но для цепи Маркова обычно больше интересует стационарное состояние, которое является пределом последовательности распределений для некоторого начального распределения.

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

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

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

Если цепь Маркова неприводима и апериодична, то существует единственное стационарное распределение π . Кроме того, в этом случае 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, то

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

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

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

Как отмечалось ранее, из уравнения (если существует) стационарное (или стационарное состояние) распределение π является левым собственным вектором строки стохастической матрицы Р . Затем, предполагая, что P диагонализуем, или, что то же самое, что P имеет n линейно независимых собственных векторов, скорость сходимости определяется следующим образом. (Для недиагонализуемого, то есть дефектные матрицы , то можно начать с нормальной формой Жордана из P и продолжить немного сложнее набор аргументов в аналогичном образе.

Пусть 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 справа и продолжим эту операцию с результатами, в итоге мы получим стационарное распределение π . Другими словами, π = u ixPP ... P = xP k при k → ∞. Это означает

Поскольку π = u 1 , π ( k ) приближается к π при k → ∞ со скоростью порядка λ 2 / λ 1 экспоненциально. Это следует потому, что, следовательно, λ 2 / λ 1 - доминирующий член. Чем меньше соотношение, тем быстрее сходимость. Случайный шум в распределении состояний π также может ускорить эту сходимость к стационарному распределению.

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

Цепи Харриса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обратное время

Для CTMC X t обратный во времени процесс определяется как . По лемме Келли этот процесс имеет такое же стационарное распределение, что и прямой процесс.

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

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

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

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

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

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

с вектор-строкой, так что все элементы в больше 0 и = 1. Отсюда π может быть найдено как

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Физика

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

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

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

Химия

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

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

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

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

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

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

Биология

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Диаграмма состояний, представляющая алгоритм PageRank с переходной вероятностью M, или .

PageRank веб - страницы, которые используются в Google определяется цепью Маркова. Это вероятность оказаться на странице в стационарном распределении следующей цепи Маркова на всех (известных) веб-страницах. Если - количество известных веб-страниц, и у страницы есть ссылки на нее, то вероятность перехода будет для всех страниц, на которые есть ссылки, и для всех страниц, на которые нет ссылок . Параметр принят около 0,15.

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

Статистика

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

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

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

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

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

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

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

Игры

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

Музыка

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

Матрица 1-го порядка
Примечание А C E
А 0,1 0,6 0,3
C 0,25 0,05 0,7
E 0,7 0,3 0
Матрица 2-го порядка
Примечания А 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

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

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

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

Бейсбол

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

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

Марковские процессы также можно использовать для генерации текста, внешне выглядящего реалистично, на основе образца документа. Марковские процессы используются во множестве развлекательных программ- генераторов пародий (см. Диссоциированную прессу , Джеффа Харрисона, Марка В. Шейни и Academias Neutronium ). Существует несколько библиотек генерации текста с открытым исходным кодом с использованием цепей Маркова, в том числе The RiTa Toolkit .

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

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

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

Примечания

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

  • Марков А.А. (1906) "Распространение закона больших долот на величины, зависящие от других наркотиков". Известия Физико-математического общества при Казанском университете , 2-я серия, том 15, с. 135–156.
  • Марков А.А. (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, соединенных в цепочку». перепечатано в Приложении B: R. Howard. Динамические вероятностные системы, том 1: Марковские цепи . Джон Уайли и сыновья.
  • Классический текст в переводе: Марков А.А. (2006). Перевод Link, Дэвид. «Пример статистического исследования текста Евгения Онегина о соединении выборок в цепочки» . Наука в контексте . 19 (4): 591–600. DOI : 10.1017 / s0269889706001074 . S2CID  144854176 .
  • Лео Брейман (1992) [1968] Вероятность . Оригинальное издание, опубликованное Эддисон-Уэсли; перепечатано Обществом промышленной и прикладной математики ISBN  0-89871-296-3 . (См. Главу 7)
  • JL Doob (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) Конечные цепи Маркова , ISBN  Д. ван Ностранда 0-442-04328-7
  • Э. Нуммелин. «Общие неприводимые цепи Маркова и неотрицательные операторы». Cambridge University Press, 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 .
  • К.С. Триведи и РАСанер, SHARPE в возрасте двадцати двух лет , т. 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 .

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