Цепь Маркова с дискретным временем - Discrete-time Markov chain

Эта статья посвящена математическим свойствам цепей Маркова с дискретным временем. Для общей области исследования см. Цепь Маркова.

Цепь Маркова с двумя состояниями, А и E.

В вероятность, а (дискретное время) Цепь Маркова (DTMC) представляет собой последовательность случайных величин, известную как случайный процесс, в котором значение следующей переменной зависит только от значения текущей переменной, а не от каких-либо переменных в прошлом. Например, машина может иметь два состояния: А и E. Когда он в состоянии А, с вероятностью 40% он перейдет в состояние E и с вероятностью 60% он останется в состоянии А. Когда он в состоянии E, вероятность того, что он переместится в А и с вероятностью 30% он останется в E. Последовательность состояний машины представляет собой цепь Маркова. Если обозначить цепь через ${\displaystyle X_{0},X_{1},X_{2},...}$ тогда ${\displaystyle X_{0}}$ это состояние, в котором машина запускается и ${\displaystyle X_{10}}$ это случайная переменная описывающий его состояние после 10 переходов. Процесс продолжается вечно, индексируется натуральные числа.

Примером случайного процесса, который не является цепью Маркова, является модель машины, которая имеет состояния А и E и переезжает в А из любого штата с вероятностью 50%, если он когда-либо посещал А раньше, и шанс 20%, если он никогда не посещал А раньше (оставляя 50% или 80% вероятности, что машина переместится в E). Это потому, что поведение машины зависит от всей истории - если машина в E, у него может быть 50% или 20% шанс переехать в А, в зависимости от его прошлых значений. Следовательно, у него нет Марковская собственность.

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

Определение

Марковская цепь с дискретным временем - это последовательность случайные переменные ${\displaystyle X_{0},X_{1},X_{2},...}$ с Марковская собственность, а именно, что вероятность перехода в следующее состояние зависит только от текущего состояния, а не от предыдущих состояний:

${\displaystyle \Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),}$ если оба условные вероятности определены правильно, т. е. если ${\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}$

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

Цепи Маркова часто описываются последовательностью ориентированные графы, где ребра графа п помечены вероятностями выхода из одного состояния за раз п в другие государства во время п + 1, ${\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n}).}$ Та же информация представлена ​​матрицей переходов от времени п ко времени п + 1. Однако цепи Маркова часто считаются однородными по времени (см. Варианты ниже), и в этом случае граф и матрица не зависят от п и поэтому не представлены в виде последовательностей.

Эти описания подчеркивают структуру цепи Маркова, которая не зависит от начального распределения. ${\displaystyle \Pr(X_{1}=x_{1}).}$ Когда цепочка однородна по времени, ее можно интерпретировать как Государственный аппарат присвоение вероятности перехода от каждой вершины или состояния к соседней. Вероятность ${\displaystyle \Pr(X_{n}=x\mid X_{1}=x_{1})}$ состояния машины можно проанализировать как статистическое поведение машины с элементом ${\displaystyle x_{1}}$ пространства состояний в качестве входных данных или как поведение машины с начальным распределением ${\displaystyle \Pr(X_{1}=y)=[x_{1}=y]}$ состояний на входе, где ${\displaystyle [P]}$ это Кронштейн Айверсона.^{[нужна цитата ]}

Вариации

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

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

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

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

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

${\displaystyle {\begin{aligned}{}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\=&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}$

Другими словами, будущее состояние зависит от прошлого. м состояния. Можно построить цепочку ${\displaystyle (Y_{n})}$ из ${\displaystyle (X_{n})}$ который обладает «классическим» марковским свойством, взяв в качестве пространства состояний упорядоченный м-наборы Икс значения, т.е. ${\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}$.^{[нужна цитата ]}

п-шаговые переходы

Вероятность выхода из состояния я заявить j в п временные шаги

${\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)}$

и пошаговый переход

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

Для однородной по времени цепи Маркова:

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

и

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

В п-шаговые переходные вероятности удовлетворяют Уравнение Чепмена – Колмогорова., что для любого k такое, что 0 <k < п,

${\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}}$

куда S - пространство состояний цепи Маркова.^[1]

В предельное распределение Pr (Икс_п = Икс) - распределение по состояниям в момент времени п. Начальное распределение Pr (Икс₀ = Икс). Развитие процесса через один временной шаг описывается следующим образом:

${\displaystyle \Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).}$

(Надстрочный индекс (п) является индекс, а не показатель степени ).

Связь классов и свойств

Штат j считается доступным из состояния я (написано я → j) если система запущена в состоянии я имеет ненулевую вероятность перехода в состояние j в какой-то момент. Формально государство j доступен из состояния я если существует целое число п_ij ≥ 0 такой, что

${\displaystyle \Pr(X_{n_{ij}}=j\mid X_{0}=i)=p_{ij}^{(n_{ij})}>0.}$

Штат я говорят, что общается с государством j (написано я ↔ j) если оба я → j и j → я. Общающийся класс - это максимальный набор состояний C так что каждая пара состояний в C общается друг с другом. Общение - это отношение эквивалентности, а общающиеся классы - классы эквивалентности этого отношения.^[1]

Общающийся класс закрывается, если вероятность выхода из класса равна нулю, а именно, если я в C но j нет, тогда j недоступен изя.^[1] Набор взаимодействующих классов образует ориентированный ациклический граф путем наследования стрелок из исходного пространства состояний. Обменивающийся класс закрыт тогда и только тогда, когда у него нет исходящих стрелок на этом графе.

Штат я считается необходимым или окончательным, если для всех j такой, что я → j также верно, что j → я. Штат я несущественно, если не существенно.^[2] Состояние является окончательным тогда и только тогда, когда его связывающий класс закрыт.

Цепь Маркова называется неприводимой, если ее пространство состояний представляет собой единственный взаимодействующий класс; другими словами, если из любого состояния можно попасть в любое состояние.^[1][3]

Периодичность

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

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

(куда ${\displaystyle \gcd }$ это наибольший общий делитель ) при условии, что этот набор не пустой. В противном случае срок не определен.^[1] Обратите внимание, что даже если у состояния есть точка ${\displaystyle k}$, может быть невозможно достичь состояния в ${\displaystyle k}$ шаги. Например, предположим, что можно вернуться в состояние в ${\displaystyle \{6,~8,~10,~12,\dots \}}$ временные шаги; ${\displaystyle k}$ было бы ${\displaystyle 2}$, даже не смотря на ${\displaystyle 2}$ не появляется в этом списке.

Если ${\displaystyle k=1}$, то состояние называется апериодическим. Иначе (${\displaystyle k>1}$) состояние называется периодическим с периодом${\displaystyle k}$. Периодичность - это свойство класса, то есть, если состояние имеет период ${\displaystyle k}$ тогда каждое состояние в своем коммуникативном классе имеет период ${\displaystyle k}$.^[1]

Мимолетность и повторяемость

Штат я называется переходным, если, учитывая, что мы начинаем в состоянии я, существует ненулевая вероятность того, что мы никогда не вернемся к я. Формально пусть случайная переменная Т_я быть первым, кто вернется в состояние я («время удара»):

${\displaystyle T_{i}=\inf\{n\geq 1:X_{n}=i\}.}$

Номер

${\displaystyle f_{ii}^{(n)}=\Pr(T_{i}=n\mid X_{0}=i)}$

вероятность того, что мы вернемся в состояние я впервые после п шагов. Поэтому укажите я временно, если

${\displaystyle \Pr(T_{i}<\infty \mid X_{0}=i)=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.}$

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

Штат я повторяется если и только если ожидаемое количество посещений я бесконечно:^[1]

${\displaystyle \sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .}$

Положительное повторение

Даже если время попадания конечно с вероятностью 1, он не обязательно должен иметь конечный ожидание. Среднее время повторения в состоянии я ожидаемое время возврата M_я:

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

Состояние я является положительным рекуррентным (или непустым постоянным), если M_я конечно; в противном случае укажите я является нулевым повторяющимся (или нулевым постоянным). Положительное и нулевое повторение - это свойства классов.^[1]

Поглощающие состояния

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

${\displaystyle p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.}$

Если каждое состояние может достичь поглощающего состояния, то цепь Маркова является поглощающая цепь Маркова.^[3]

Обратимая цепь Маркова

Цепь Маркова называется обратимой, если существует распределение вероятностей π по своим состояниям таким, что

${\displaystyle \pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)}$

на все времена п и все государства я и j. Это состояние известно как подробный баланс условие (или уравнение локального баланса).

Учитывая фиксированное произвольное время п и используя сокращение

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

подробное уравнение баланса можно записать более компактно как

${\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}\,.}$^[1]

Единый временной шаг от п к п +1 можно рассматривать как каждого человека я имея π_я долларов изначально и платить каждому человеку j фракция п_ij этого. Подробное условие баланса гласит, что после каждого платежа другое лицо возвращает точно такую ​​же сумму денег.^[4] Понятно общая сумма денег π каждый человек остается тем же самым после временного шага, поскольку каждый потраченный доллар уравновешивается соответствующим полученным долларом. Более формально это можно показать равенством

${\displaystyle \sum _{i}\pi _{i}p_{ij}=\sum _{i}\pi _{j}p_{ji}=\pi _{j}\sum _{i}p_{ji}=\pi _{j}\,,}$

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

В качестве п было произвольно, это рассуждение справедливо для любых п, а значит, для обратимых цепей Маркова π всегда является стационарным распределением Pr (Икс_п+1 = j | Икс_п = я) для каждогоп.

Если цепь Маркова начинается в установившемся распределении, то есть если ${\displaystyle Pr(X_{0}=i)=\pi _{i}}$, тогда ${\displaystyle Pr(X_{n}=i)=\pi _{i}}$ для всех ${\displaystyle n}$ а подробное уравнение баланса можно записать как

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

Левая и правая части этого последнего уравнения идентичны, за исключением того, что временные индексы меняются местами. п ип + 1.

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

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

Стационарные распределения

Распределение ${\displaystyle \pi }$ - стационарное распределение цепи Маркова со стохастической матрицей ${\displaystyle P}$ если и только если ${\displaystyle \pi P=\pi }$. Это можно записать так:^[1]

${\displaystyle \forall j\in \mathbb {S} :\sum _{i\in \mathbb {S} }\pi _{i}p_{ij}=\pi _{j}}$

Из этого условия следует, что ${\displaystyle \pi P^{n}=\pi }$ а значит, если цепь Маркова ${\displaystyle (X_{n},n\in \mathbb {N} )}$ имеет начальное распространение ${\displaystyle X_{0}=\pi }$ тогда ${\displaystyle X_{n}=\pi }$ (в раздаче) для любых ${\displaystyle n\in \mathbb {N} }$.^[1]

Если цепь Маркова неприводима, то она имеет стационарное распределение тогда и только тогда, когда оно положительно рекуррентно,^[5] в этом случае единственное такое распределение дается ${\displaystyle \pi _{i}={\frac {1}{M_{i}}}}$ куда ${\displaystyle M_{i}=\mathbb {E} (T_{i})}$ среднее время повторения я.^[1]

Если цепочка имеет более одного закрытого коммуникативного класса, ее стационарные распределения не будут уникальными (рассмотрите любые закрытый коммуникационный класс ${\displaystyle C_{i}}$ в цепочке; у каждого будет свое уникальное стационарное распределение ${\displaystyle \pi _{i}}$. Расширение этих распределений на всю цепочку, установление всех значений на ноль вне класса связи, приводит к тому, что набор инвариантных мер исходной цепочки представляет собой набор всех выпуклых комбинаций ${\displaystyle \pi _{i}}$s). Однако если государство j апериодичен, то${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{jj}^{(n)}={\tfrac {C}{M_{j}}}}$и для любого другого государства я, позволять ж_ij быть вероятностью того, что цепь когда-либо посетит состояние j если он начинается вя,${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ij}^{(n)}=C{\tfrac {f_{ij}}{M_{j}}}.}$

Если государство я периодичен с периодом k > 1, то предел${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(n)}}$не существует, хотя предел${\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(kn+r)}}$существует для каждого целого числар.

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

Марковская цепь не обязательно должна быть однородной по времени, чтобы иметь равновесное распределение. Если есть распределение вероятностей по состояниям ${\displaystyle {\boldsymbol {\pi }}}$ такой, что

${\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)}$

для каждого государства j и каждый раз п тогда ${\displaystyle {\boldsymbol {\pi }}}$ является равновесным распределением цепи Маркова. Такое может происходить в методах Монте-Карло с цепью Маркова (MCMC) в ситуациях, когда используется ряд различных матриц перехода, поскольку каждая из них эффективна для определенного вида смешивания, но каждая матрица соответствует общему равновесному распределению.

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

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

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

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

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

${\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}$

Эргодическая теорема

Пример эргодическая теория, эргодическая теорема для состояний, что для неприводимой апериодической цепи Маркова с любыми двумя состояниями я и j,^[1]

${\displaystyle p_{i,j}^{(n)}\rightarrow {\frac {1}{M_{j}}}}$ в качестве ${\displaystyle n\rightarrow \infty }$

Примечания

1. Гримметт, Г.; Стирзакер, Д. Р. (1992). «6». Вероятность и случайные процессы (второе изд.). Издательство Оксфордского университета. ISBN  0198572220.
2. Ашер Левин, Дэвид (2009). Цепи Маркова и времена перемешивания. п.16. ISBN  978-0-8218-4739-8.
3. Гагнюк, Пол А. (2017). Цепи Маркова: от теории к реализации и экспериментам. США, Нью-Джерси: John Wiley & Sons. С. 1–235. ISBN  978-1-119-38755-8.
4. Ричард Дарретт (19 мая 2012 г.). Основы случайных процессов. Springer Science & Business Media. п. 37. ISBN  978-1-4614-3615-7. В архиве из оригинала от 6 февраля 2017 г.
5. Серфозо, Ричард (2009), «Основы прикладных случайных процессов», Вероятность и ее приложения: 35, Дои:10.1007/978-3-540-89332-5, ISBN  978-3-540-89331-8, МИСТЕР  2484222, в архиве из оригинала от 19.03.2015
6. Норрис, Дж. Р. (1997). «Цепи Маркова с непрерывным временем II». Цепи Маркова. С. 108–127. Дои:10.1017 / CBO9780511810633.005. ISBN  9780511810633.

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

• Марков А.А. (1971). «Распространение предельных теорем теории вероятностей на сумму переменных, соединенных в цепочку». перепечатано в Приложении B к: R. Howard. Динамические вероятностные системы, том 1: Марковские цепи. Джон Уайли и сыновья.
• Марков, А.А. (2006). Перевод Линка, Дэвид. "Пример статистического исследования текста Евгения Онегина о соединении образцов в цепочки". Наука в контексте. 19 (4): 591–600. Дои:10.1017 / s0269889706001074.
• Лео Брейман (1992) [1968] Вероятность. Оригинальное издание, опубликованное Эддисон-Уэсли; перепечатано Общество промышленной и прикладной математики ISBN  0-89871-296-3. (См. Главу 7)
• Дж. Л. Дуб (1953) Стохастические процессы. Нью-Йорк: Джон Уайли и сыновья ISBN  0-471-52369-0.
• С. П. Мейн и Р. Л. Твиди (1993) Марковские цепи и стохастическая устойчивость. Лондон: Springer-Verlag ISBN  0-387-19832-6. онлайн: MCSS . Выйдет второе издание, Cambridge University Press, 2009.
• Кемени, Джон Дж .; Хэзлтон Миркил; Дж. Лори Снелл; Джеральд Л. Томпсон (1959). Конечные математические структуры (1-е изд.). Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, Инк. Номер каталога карточек Библиотеки Конгресса 59-12841. Классический текст. cf Глава 6 Конечные цепи Маркова стр. 384ff.
• Джон Г. Кемени & Дж. Лори Снелл (1960) Конечные цепи Маркова, D. van Nostrand Company ISBN  0-442-04328-7
• Э. Нуммелин. «Общие неприводимые цепи Маркова и неотрицательные операторы». Издательство Кембриджского университета, 1984, 2004. ISBN  0-521-60494-X
• Сенета, Э. Неотрицательные матрицы и цепи Маркова. 2-е изд. изд., 1981, XVI, 288 стр., Серия Springer в мягкой обложке по статистике. (Первоначально опубликовано Allen & Unwin Ltd., Лондон, 1973 г.) ISBN  978-0-387-29765-1