Марковская цепь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Классификация цепей и состояний)
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Цепь  Маркова''' {{---}} последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.
+
'''Цепь  Маркова''' (англ. ''Markov chain'') {{---}} последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем, что при фиксированном настоящем будущее независимо от прошлого.
  
 
Процесс в каждый момент времени находится в одном из <tex> n </tex> состояний.  
 
Процесс в каждый момент времени находится в одном из <tex> n </tex> состояний.  
Строка 7: Строка 7:
 
При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>.
 
При этом, если он находится в состоянии с номером <tex> i </tex>, то он перейдет в состояние <tex> j </tex> с вероятностью <tex> p_{ij} </tex>.
  
Матрицу <tex> P = ||p_{ij}|| </tex> называют '''матрицей переходов'''.
+
Матрицу <tex> P = ||p_{ij}|| </tex> называют '''матрицей переходов''' (англ. ''transition matrix'').
 
}}
 
}}
  
Строка 31: Строка 31:
 
<tex> c_{i + t} = c_{i} \times P^t </tex>.
 
<tex> c_{i + t} = c_{i} \times P^t </tex>.
  
Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным''').
+
Для марковской цепи иногда задают начальное распределение <tex> c_0 </tex>, хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют '''предельным''' (англ. ''limiting distribution'')).
  
 
== Достижимость и сообщаемость ==
 
== Достижимость и сообщаемость ==
Строка 55: Строка 55:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Неразложимая цепь''' (англ. ''ireducible chain'') — цепь Маркова, в которой все состояния образуют один неразложимый класс.
+
'''Неразложимая цепь''' (англ. ''irreducible chain'') — цепь Маркова, в которой все состояния образуют один неразложимый класс.
 
}}
 
}}
  
Строка 62: Строка 62:
 
|id = sort_def
 
|id = sort_def
 
|definition=
 
|definition=
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами'''. Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными'''. Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными'''.
+
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются '''эргодическими классами''' (англ. ''ergodic classes''). Состояния в эргодических классах называются '''эргодическими''' (англ. ''ergodic''), '''возвратными''', или '''существенными''' (англ. ''essential''). Все остальные неразложимые классы называются '''невозвратными классами'''. Состояния, входящие в них, называются '''невозвратными''' или '''несущественными''' (англ. ''inessential'').
 
}}
 
}}
  
Строка 69: Строка 69:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Эргодическая''' марковская цепь — марковская цепь, целиком состоящая из одного эргодического класса.
+
'''Эргодическая''' марковская цепь (англ. ''ergodic Markov chain'') — марковская цепь, целиком состоящая из одного эргодического класса.
 
}}
 
}}
  
Строка 76: Строка 76:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Для <tex> i </tex> и <tex> j </tex>, принадлежащих одному классу эквивалентности, <tex> d_i = d_j = d </tex> и числа из множества <tex> N_{i, j} </tex> сравнимы между собой по модулю <tex> d </tex>.
+
Для <tex> i </tex> и <tex> j </tex>, принадлежащих одному классу эквивалентности по отношению достижимости, <tex> d_i = d_j = d </tex> и числа из множества <tex> N_{i, j} </tex> сравнимы между собой по модулю <tex> d </tex>.
 
|proof=
 
|proof=
 
Пусть <tex> a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} </tex>. Из <tex> i </tex> можно попасть в <tex> j </tex> и обратно, значит, <tex> a + c \in N_{i, i} </tex>. Также после попадания в <tex> j </tex> можно сколько угодно раз перейти из него в самого себя, и только потом перейти в <tex> i </tex>, для этого понадобится <tex> a + k \cdot d_j + c </tex>  шагов при любом достаточно большом <tex> k </tex>. Значит, <tex> d_j </tex> должно делиться на <tex> d_i </tex>. Но аналогично можно доказать, что <tex> d_i </tex> делится на <tex> d_j </tex>, поэтому <tex> d_i = d_j = d </tex>. Также можно перейти за <tex> b </tex> шагов в <tex> j </tex>, а потом попасть в <tex> i </tex>, поэтому <tex> b + c \in N_{i, i} </tex>. Значит, <tex> a + c </tex> и <tex> b + c </tex> оба делятся на <tex> d </tex>, то есть <tex> a </tex> и <tex> b </tex> сравнимы между собой по модулю <tex> d </tex>.
 
Пусть <tex> a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} </tex>. Из <tex> i </tex> можно попасть в <tex> j </tex> и обратно, значит, <tex> a + c \in N_{i, i} </tex>. Также после попадания в <tex> j </tex> можно сколько угодно раз перейти из него в самого себя, и только потом перейти в <tex> i </tex>, для этого понадобится <tex> a + k \cdot d_j + c </tex>  шагов при любом достаточно большом <tex> k </tex>. Значит, <tex> d_j </tex> должно делиться на <tex> d_i </tex>. Но аналогично можно доказать, что <tex> d_i </tex> делится на <tex> d_j </tex>, поэтому <tex> d_i = d_j = d </tex>. Также можно перейти за <tex> b </tex> шагов в <tex> j </tex>, а потом попасть в <tex> i </tex>, поэтому <tex> b + c \in N_{i, i} </tex>. Значит, <tex> a + c </tex> и <tex> b + c </tex> оба делятся на <tex> d </tex>, то есть <tex> a </tex> и <tex> b </tex> сравнимы между собой по модулю <tex> d </tex>.
Строка 86: Строка 86:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Циклический класс''' класс, для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <tex> t_{i, j} = 0 </tex>.
+
'''Циклический класс''' (англ. ''cyclic class'') {{---}} класс, для любых элементов <tex> i </tex> и <tex> j </tex> которого верно равенство <tex> t_{i, j} = 0 </tex>.
 
}}
 
}}
  
Строка 94: Строка 94:
 
}}
 
}}
  
Если цепь циклическая, у неё есть некоторый период <tex> d > 1 </tex>, а её состояния подразделяются на <tex> d </tex> циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через <tex> d </tex> шагов.
+
Если цепь циклическая, у неё есть некоторый период <tex> d > 1 </tex>, а её состояния подразделяются на <tex> d </tex> циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через <tex> d </tex> шагов.  
 +
 
 +
Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из <tex> n </tex> состояний и, следовательно, содержащий <tex> n </tex> циклический классов. Более сложный случай – простые циклы. Простой цикл состоит из
 +
нескольких циклов, пересекающихся по вершинам, но не пересекающихся по
 +
ребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длин
 +
этих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа.
 +
 
 +
==== Примеры циклических цепей ====
 +
 
 +
{| class = "wikitable"
 +
! Изображение !! Матрица переходов !! Описание
 +
|-
 +
|style="background-color:#FFF" |[[Файл:N steps chain.png|400px|center|Элементарный цикл]]
 +
|<tex>\begin{pmatrix}
 +
0 & 1 & 0 & \cdots & 0 & 0 & 0 \\
 +
0 & 0 & 1 & \cdots & 0 & 0 & 0 \\       
 +
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
 +
0 & 0 & 0 & \cdots & 0 & 0 & 1 \\
 +
1 & 0 & 0 & \cdots & 0 & 0 & 0
 +
\end{pmatrix}_N
 +
</tex>
 +
| Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно <tex> n </tex> шагов, проходящих через все вершины, чтобы попасть из вершины <tex> j </tex> в неё же.
 +
|-
 +
|style="background-color:#FFF" |[[Файл:Prime cyclic chain.png|200px|center|Простой цикл]]
 +
|<tex>\begin{pmatrix}
 +
0 & 0 & 0,5 & 0,5 & 0 & 0 \\
 +
1 & 0 & 0 & 0 & 0 & 0 \\       
 +
0 & 1 & 0 & 0 & 0 & 0 \\
 +
0 & 0 & 0 & 0 & 1 & 0 \\
 +
0 & 0 & 0 & 0 & 0 & 1 \\
 +
1 & 0 & 0 & 0 & 0 & 0
 +
\end{pmatrix}
 +
</tex>
 +
|Этот простой цикл состоит из двух элементарных, пересекающихся в вершине <tex> 1 </tex>. НОД длин всех путей из вершины <tex> 1 </tex> в вершину <tex> 1 </tex> равен <tex> 1 </tex>, поэтому можно получить предельное распределение.
 +
|-
 +
|}
  
 
=== Поглощающая цепь ===
 
=== Поглощающая цепь ===
 
{{Определение
 
{{Определение
|definition='''Поглощающее состояние''' — состояние, из которого нельзя попасть ни в какое другое, то есть <tex> i </tex> — поглощающее состояние, если <tex> p_{ii} = 1 </tex>.
+
|definition='''Поглощающее состояние''' (англ. ''absorbing state'') — состояние, из которого нельзя попасть ни в какое другое, то есть <tex> i </tex> — поглощающее состояние, если <tex> p_{ii} = 1 </tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 104: Строка 139:
 
}}
 
}}
  
В примере на рисунке поглощающими являются состояния 3 и 4, а непоглощающими — 1 и 2.
+
В примере на рисунке поглощающими являются состояния <tex>3</tex> и <tex>4</tex>, а непоглощающими — <tex>1</tex> и <tex>2</tex>.
  
 
=== Пример ===
 
=== Пример ===
Строка 122: Строка 157:
  
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если i — посглощающее состояние absorbing[i] = true
+
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если <tex>i</tex> — посглощающее состояние, то <tex>\mathtt{absorbing[i]} = true</tex>
 
*<tex>\mathtt{n}</tex> — количество состояний
 
*<tex>\mathtt{n}</tex> — количество состояний
 
*<tex>\mathtt{m}</tex> — количество переходов
 
*<tex>\mathtt{m}</tex> — количество переходов
Строка 132: Строка 167:
 
         absorbing[transition[i][0]] = ''true''
 
         absorbing[transition[i][0]] = ''true''
 
     '''return''' absorbing
 
     '''return''' absorbing
 +
 +
== См. также ==
 +
*[[Эргодическая марковская цепь]]
 +
*[[Регулярная марковская цепь]]
 +
*[[Отношение связности, компоненты связности]]
  
 
== Источники информации ==
 
== Источники информации ==

Текущая версия на 19:17, 4 сентября 2022

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

Процесс в каждый момент времени находится в одном из [math] n [/math] состояний.

При этом, если он находится в состоянии с номером [math] i [/math], то он перейдет в состояние [math] j [/math] с вероятностью [math] p_{ij} [/math].

Матрицу [math] P = ||p_{ij}|| [/math] называют матрицей переходов (англ. transition matrix).


На матрицу переходов накладываются следующие условия:

  1. [math] p_{ij} \geqslant 0 [/math]
  2. [math] \forall i\ \ \sum\limits_{j} p_{ij} = 1 [/math]

Такая матрица называется стохастической.

Марковскую цепь можно представить в виде графа, в котором вершины — это состояния процесса, а ребра — переходы между состояниями, и на ребре из [math] i [/math] в [math] j [/math] написана вероятность перехода из [math] i [/math] в [math] j [/math], то есть [math] p_{ij} [/math].

Распределение вероятностей

Марковскую цепь в любой момент времени [math] t [/math] можно охарактеризовать вектором-строкой [math] c_t [/math] — распределением вероятностей по состояниям цепи ([math] c_{ti} [/math] — вероятность цепи в момент времени [math] t [/math] быть в состоянии [math] i [/math]).

Если [math] c_i [/math] — текущее распределение вероятностей, то можно узнать распределение на следующем шаге, умножив вектор на матрицу перехода:

[math] c_{i + 1} = c_{i} \times P [/math].

Из ассоциативности произведения матриц следует, что для того, чтобы узнать распределение вероятностей через [math] t [/math] шагов, нужно умножить [math] c_i [/math] на матрицу перехода, возведённую в степень [math] t [/math]:

[math] c_{i + t} = c_{i} \times P^t [/math].

Для марковской цепи иногда задают начальное распределение [math] c_0 [/math], хотя во многих классах марковских цепей распределение по прошествии большого периода времени от него не зависит (такое распределение называют предельным (англ. limiting distribution)).

Достижимость и сообщаемость

Обозначим вероятность попасть из состояния [math] i [/math] в состояние [math] j [/math] за [math] n [/math] переходов как [math] p_{ij}^{(n)} [/math].


Определение:
Состояние [math] j [/math] достижимо (англ. accesible) из состояния [math] i [/math], если существует такое [math] n [/math], что [math] p_{ij}^{(n)} \gt 0 [/math]. Достижимость [math] j [/math] из [math] i [/math] обозначается [math] i \rightarrow j [/math].


Определение:
Состояния [math] i [/math] и [math] j [/math] сообщаются (англ. communicate), если они достижимы друг из друга. Сообщаемость [math] i [/math] и [math] j [/math] обозначается [math] i \leftrightarrow j [/math].


Классификация цепей и состояний

Неразложимая цепь

Определение:
Неразложимый класс (англ. communicating class) — класс эквивалентности множества состояний по отношению сообщаемости. Если представить марковскую цепь как граф, неразложимый класс будет аналогичен компоненте сильной связности.


Определение:
Неразложимая цепь (англ. irreducible chain) — цепь Маркова, в которой все состояния образуют один неразложимый класс.


Эргодическая цепь

Определение:
Упорядочим (очевидно, упорядочение будет частичным) неразложимые классы отношением достижимости. Минимальные элементы в таком упорядочении называются эргодическими классами (англ. ergodic classes). Состояния в эргодических классах называются эргодическими (англ. ergodic), возвратными, или существенными (англ. essential). Все остальные неразложимые классы называются невозвратными классами. Состояния, входящие в них, называются невозвратными или несущественными (англ. inessential).


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


Определение:
Эргодическая марковская цепь (англ. ergodic Markov chain) — марковская цепь, целиком состоящая из одного эргодического класса.


Пусть [math] N_{i, j} [/math] — множество таких [math] n [/math], что находясь в состоянии [math] i [/math], можно оказаться в состоянии [math] j [/math] через [math] n [/math] шагов. [math] d_i [/math] — наибольший общий делитель чисел из множества [math] N_{i, i} [/math].

Лемма:
Для [math] i [/math] и [math] j [/math], принадлежащих одному классу эквивалентности по отношению достижимости, [math] d_i = d_j = d [/math] и числа из множества [math] N_{i, j} [/math] сравнимы между собой по модулю [math] d [/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math] a \in N_{i, j}, \ b \in N_{i, j}, \ c \in N_{j, i} [/math]. Из [math] i [/math] можно попасть в [math] j [/math] и обратно, значит, [math] a + c \in N_{i, i} [/math]. Также после попадания в [math] j [/math] можно сколько угодно раз перейти из него в самого себя, и только потом перейти в [math] i [/math], для этого понадобится [math] a + k \cdot d_j + c [/math] шагов при любом достаточно большом [math] k [/math]. Значит, [math] d_j [/math] должно делиться на [math] d_i [/math]. Но аналогично можно доказать, что [math] d_i [/math] делится на [math] d_j [/math], поэтому [math] d_i = d_j = d [/math]. Также можно перейти за [math] b [/math] шагов в [math] j [/math], а потом попасть в [math] i [/math], поэтому [math] b + c \in N_{i, i} [/math]. Значит, [math] a + c [/math] и [math] b + c [/math] оба делятся на [math] d [/math], то есть [math] a [/math] и [math] b [/math] сравнимы между собой по модулю [math] d [/math].
[math]\triangleleft[/math]

Введём числа [math] t_{i, j}, 0 \leqslant t_{i, j} \lt d [/math], так, что любой элемент из [math] N_{i, j} [/math] сравним с [math] t_{i, j} [/math] по модулю [math] d [/math].

Циклический класс

Определение:
Циклический класс (англ. cyclic class) — класс, для любых элементов [math] i [/math] и [math] j [/math] которого верно равенство [math] t_{i, j} = 0 [/math].


Определение:
Если цепь состоит целиком из одного циклического класса, её называют регулярной, иначе — циклической.


Если цепь циклическая, у неё есть некоторый период [math] d \gt 1 [/math], а её состояния подразделяются на [math] d [/math] циклических классов. Цепь движется по циклическим классам в определённом порядке, возвращаясь в класс с начальным состоянием через [math] d [/math] шагов.

Топология циклических цепей разнообразна. Самым тривиальным случаем является элементарный цикл из [math] n [/math] состояний и, следовательно, содержащий [math] n [/math] циклический классов. Более сложный случай – простые циклы. Простой цикл состоит из нескольких циклов, пересекающихся по вершинам, но не пересекающихся по ребрам. Все эти циклы обязаны не быть взаимно простыми. Иначе НОД длин этих циклов равен единице, и цепь регулярна. Общий случай циклической цепи – цепь, состоящая из циклов, пересекающихся по вершинам и ребрам в представлении цепи как графа.

Примеры циклических цепей

Изображение Матрица переходов Описание
Элементарный цикл
[math]\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \end{pmatrix}_N [/math] Стохастическая матрица элементарного цикла всегда имеет по одной единице в каждом столбце и каждой строке. Таким образом, нужно ровно [math] n [/math] шагов, проходящих через все вершины, чтобы попасть из вершины [math] j [/math] в неё же.
Простой цикл
[math]\begin{pmatrix} 0 & 0 & 0,5 & 0,5 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} [/math] Этот простой цикл состоит из двух элементарных, пересекающихся в вершине [math] 1 [/math]. НОД длин всех путей из вершины [math] 1 [/math] в вершину [math] 1 [/math] равен [math] 1 [/math], поэтому можно получить предельное распределение.

Поглощающая цепь

Определение:
Поглощающее состояние (англ. absorbing state) — состояние, из которого нельзя попасть ни в какое другое, то есть [math] i [/math] — поглощающее состояние, если [math] p_{ii} = 1 [/math].


Определение:
Поглощающей (англ. absorbing chain) называется марковская цепь, в которой есть хотя бы одно поглощающее состояние и из любого состояния достижимо хотя бы одно поглощающее.


В примере на рисунке поглощающими являются состояния [math]3[/math] и [math]4[/math], а непоглощающими — [math]1[/math] и [math]2[/math].

Пример

Пример марковской цепи

На рисунке:

  • достижимыми состояниями являются: [math] 2 [/math] из [math] 1 [/math] (непосредственно), [math] 3 [/math] из [math] 1 [/math] (непосредственно), [math] 6 [/math] из [math] 3 [/math] (к примеру, через цепочку состояний [math] 3 \rightarrow 2 \rightarrow 4 \rightarrow 6 [/math]) и т.д.
  • сообщаются состояния [math] 1 [/math] и [math] 2 [/math] (непосредственно), [math] 6 [/math] и [math] 7 [/math] (непосредственно), [math] 1 [/math] и [math] 3 [/math] (достижимы друг из друга) и т. д.
  • неразложимыми классами являются множества вершин [math] \left \{ 1, 2, 3 \right \} [/math], [math] \left \{ 4 \right \} [/math], [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
  • эргодическими классами являются множества вершин [math] \left \{ 5 \right \} [/math], [math] \left \{ 6, 7 \right \} [/math];
  • поглощающим состоянием является состояние [math] 5 [/math].
  • если расматривать [math] \{6, 7\} [/math] отдельно, можно выделить два циклических класса [math] \{6\} [/math] и [math] \{7\} [/math] (на каждом шаге цепь переходит из одного состояния в другое, а через [math] d = 2 [/math] шага возвращается в одно и то же состояние.

Подсчет количества поглощащих состояний

Пусть [math]\mathtt{transition}[/math] — массив переходов марковской цепи, где [math]\mathtt{transition[i][2]}[/math] — вероятность перехода из состояния [math]\mathtt{transition[i][0]}[/math] в [math]\mathtt{transition[i][1]}[/math]. Тогда, по определению поглощающего состояния, если [math]\mathtt{j}[/math] — поглощающее состояние, то [math]\mathtt{transition[j][2] = 1}[/math]. По этому признаку помно определить все поглощающие состояния в цепи.

Псевдокод

  • [math]\mathtt{absorbing}: boolean:[\mathtt{n}][/math] — массив состояний. Если [math]i[/math] — посглощающее состояние, то [math]\mathtt{absorbing[i]} = true[/math]
  • [math]\mathtt{n}[/math] — количество состояний
  • [math]\mathtt{m}[/math] — количество переходов
function findAbsorbings(transition: int[m][2]):
   boolean absorbing[m]
   for i = 0 to m - 1
      if transition[i][0] == transition[i][1] and transition[i][2] == 1
        absorbing[transition[i][0]] = true
   return absorbing

См. также

Источники информации