http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=81.24.126.202&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T18:53:58ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%22%D0%92%D0%BF%D0%B5%D1%80%D0%B5%D0%B4-%D0%9D%D0%B0%D0%B7%D0%B0%D0%B4%22&diff=64162Алгоритм "Вперед-Назад"2018-03-11T16:18:48Z<p>81.24.126.202: /* Псевдокод */</p>
<hr />
<div>'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.<br />
<br />
== Вычисление ==<br />
Пусть дана скрытая Марковская модель <tex>\lambda = \{S, \Omega, \Pi, A, B\}</tex>, где <tex>S = \{s_1,\ldots, s_n\}</tex> {{---}} состояния, <tex>\Omega = \{\omega_1,\ldots, \omega_m\}</tex> {{---}} возможные события, <tex>\Pi = \{\pi_1,\ldots, \pi_n\}</tex> {{---}} начальные вероятности, <tex>A = \{a_{ij}\}</tex> {{---}} матрица переходов, а <tex>B = \{b_{i\omega_k}\}</tex> {{---}} вероятность наблюдения события <tex>\omega_k</tex> после перехода в состояние <tex>s_i</tex>.<br />
За <tex>T</tex> шагов в этой модели получилась последовательность наблюдений <tex>O_{1,T} = {o_1,\ldots, o_T}</tex>.<br />
<br />
Пусть в момент <tex>t</tex> мы оказались в состоянии <tex>i</tex>: <tex>X_t = i</tex>. Назовем <tex>\alpha_{i}(t)</tex> вероятность того, что при этом во время переходов образовалась последовательность наблюдений <tex>O_{1,t-1}</tex>, а <tex>\beta_{i}(t)</tex> {{---}} вероятность того, что после этого состояния мы будем наблюдать последовательность наблюдений <tex>O_{t,T}</tex>:<br />
<br />
<tex>\alpha_{i}(t) \overset{def}{=} P(O_{1, t-1} \mid X_t = i) \\<br />
\beta_i(t) \overset{def}{=} P(O_{t,T} \mid X_t = i)</tex><br />
<br />
Нам требуется найти <tex>P(X_t = i \mid O) = P(X_t = i \mid O_{1,t-1} \cap O_{t,T})</tex>. Поскольку будущее Марковской цепи не зависит от прошлого, мы можем утверждать, что вероятность того, что мы будем наблюдать события <tex>O_{t,T}</tex> не зависит от того, что в прошлом мы наблюдали последовательность <tex>O_{1,t-1}</tex>, и, следовательно:<br />
<br />
<tex>P(X_t = i \mid O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\dfrac{P(X_t = i \mid O_{1,t-1}) \cdot P(X_t = i \mid O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{i}(t) \cdot \beta_{i}(t)}{P(O)}</tex><br />
<br />
=== Проход вперед ===<br />
Заметим, что в <tex>\{\alpha_s(1)\}</tex> нужно считать равной <tex>\pi_s b_{so_1}</tex>, как вероятность получить первое событие из начального распределения.<br />
<br />
Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex> рекуррентно:<br />
<br />
<tex>\alpha_{s}(t) = P(O_{1, t} \mid X_t = s_i) = \\<br />
= \displaystyle\sum\limits_{j \in S} P(O_{1, t} \mid X_t = s \cap X_{t-1} = j) = \\<br />
= \displaystyle\sum\limits_{j \in S} P(O_{1, t-1} \mid X_{t-1} = j) \cdot P(X_t = s \mid X_{t-1} = j) \cdot P(O_t = o_t \mid X_t = s) = \\<br />
= \displaystyle\sum\limits_{j \in S} \alpha_{j}(t-1) \cdot a_{js} \cdot b_{so_t} = \\<br />
= b_{so_t} \cdot \displaystyle\sum\limits_{j \in S} \alpha_{j}(t-1) \cdot a_{js}</tex><br />
<br />
Итак, вероятность попасть в состояние <tex>s</tex> на <tex>t</tex>-ом шаге, учитывая, что после перехода произойдет событие <tex>o_t</tex> будет равна вероятности быть в состоянии <tex>j</tex> на <tex>(t - 1)</tex>-ом шаге, умноженной на вероятность перейти из состояния <tex>j</tex> в <tex>s</tex>, произведя событие <tex>o_t</tex> для всех <tex>j \in S</tex>.<br />
<br />
=== Проход назад ===<br />
Аналогично, <tex>\beta_s(T+1) = 1</tex>, так как произвольная цепочка наблюдений будет произведена, какими бы ни были состояния.<br />
<br />
Предыдущие <tex>\beta_s(t)</tex> считаются рекуррентно:<br />
<br />
<tex>\beta_s(t) = P(O_{t, T} \mid X_t = s) = \\<br />
= \displaystyle\sum\limits_{j \in S} P(O_{t+1,T} \mid X_{t+1} = j) \cdot P(X_{t+1} = j \mid X_t = s) \cdot P(o_{t+1} \mid X_t = s) = \\<br />
= \displaystyle\sum\limits_{j \in S} \beta_j(t+1) \cdot a_{sj} \cdot b_{jo_{t+1}}</tex><br />
<br />
=== Сглаживание вероятности ===<br />
Итак, для произвольного состояния <tex>s</tex> в произвольный шаг <tex>t</tex> теперь известна вероятность того, что на пути к нему была произведена последовательность <tex>O_{1,t}</tex> и вероятность того, что после него будет произведена последовательность <tex>O_{t+1,T}</tex>. Чтобы найти вероятность того, что будет произведена цепочка событий, найти <tex>P(O)</tex>, нужно просуммировать произведение обеих вероятностей для всех состояний при произвольном шаге t: <tex>P(O) = \sum_{s \in S} \alpha_s(t)\beta_s(t)</tex>.<br />
<br />
Теперь найдем вероятность того, что в момент <tex>t</tex> цепь будет в состоянии <tex>s</tex>:<br />
<br />
<tex>P(X_t = s \mid O) = P(X_t = s \mid O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\dfrac{P(X_t = s \mid O_{1,t-1}) \cdot P(X_t = s \mid O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{s}(t) \cdot \beta_{s}(t)}{P(O)}</tex> <tex>=</tex><br />
<br />
<tex>=</tex> <tex dpi="160">\dfrac{\alpha_s(t)\cdot \beta_s(t)}{\sum_{i \in S}\alpha_s(t)\cdot \beta_s(t)}</tex><br />
<br />
== Пример ==<br />
[[Файл:HMM-Forward-Backward-Example.png|thumb|right|Пример СММ]]<br />
Пусть ваша жизнь не удалась и вам пришлось работать охранником в холле офисного здания. Каждое утро вы наблюдали за тем, как один и тот же мужчина либо приносил, либо не приносил зонтик в зависимости от погоды. Увлекаясь статистикой, вы выяснили, что за день погода может поменяться с вероятностью <tex>0.3</tex>; если на улице идет дождь, то мужчина приносит зонтик с вероятностью <tex>0.9</tex>, а если солнечно {{---}} то с вероятностью <tex>0.2</tex> (пример справа).<br />
<br />
Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь?<br />
<br />
По вышесказанному, <tex>P(X_2 = Rain \mid \{umbrella, umbrella, no, umbrella, umbrella\}) = </tex> <br />
<br />
<tex>=</tex> <tex dpi="160">\dfrac{\alpha_{Rain}(2)\cdot \beta_{Rain}(2)}{\sum_{i \in \{Rain, Sun\}}\alpha_i(2)\cdot \beta_i(2)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{Rain}(2)\cdot \beta_{Rain}(2)}{\alpha_{Rain}(2)\cdot \beta_{Rain}(2) + \alpha_{Sun}(2)\cdot \beta_{Sun}(2)}</tex> <tex>\approx 0.820</tex>.<br />
<br />
Итак, с вероятностью <tex>\approx 82\%</tex> во вторник шел дождь.<br />
<br />
== Псевдокод ==<br />
<br />
<font color=darkgreen><br />
// fwd, bkw {{---}} матрицы размера |S|*T, которым во время работы присваиваются промежуточные результаты alpha и beta <br />
// probabilities {{---}} матрица размера |S|*T, в которую заносится ответ<br />
// S - массив состояний, П - массив начальных вероятностей, O - последовательность наблюдений </font><br />
<br />
'''fun''' alpha(s: '''int''', t: '''int'''): '''int'''<br />
'''if''' (s, t) '''in''' fwd<br />
'''return''' fwd[s, t]<br />
f = 0<br />
'''for''' j '''in''' S<br />
f += alpha(j, t - 1) * transitionProbability[j][s]<br />
f *= emitProbability[s][observations[t]]<br />
fwd[s, t] = f<br />
'''return''' fwd[s, t]<br />
<br />
'''fun''' beta(s: '''int''', t: '''int'''): '''int'''<br />
'''if''' (s, t) '''in''' bkw<br />
'''return''' bkw[s, t]<br />
b = 0<br />
'''for''' j '''in''' S<br />
b += beta(j, t + 1) * transitionProbability[s][j] * emitProbability[j][O[t + 1]]<br />
bkw[s, t] = b<br />
'''return''' bkw[s, t]<br />
<br />
'''fun''' forward_backward():<br />
'''for''' s '''in''' S<br />
fwd[s, 1] = emitProbability[s][observations[1]] * П[s]<br />
bkw[s, observations.length - 1] = 1<br />
chainProbability = 0<br />
'''for''' j '''in''' S<br />
chainProbability += alpha(j, 1) * beta(j, 1)<br />
'''for''' s '''in''' S<br />
'''for''' t '''in''' [1, T]<br />
probabilities[s, t] = (alpha(s, t) * beta(s, t)) / chainProbability<br />
<br />
== См. также ==<br />
<br />
*[[Скрытые Марковские модели]]<br />
*[[Алгоритм Баума-Велша]]<br />
*[[Алгоритм Витерби]]<br />
<br />
== Источники информации ==<br />
* [[wikipedia:Forward–backward_algorithm|Wikipedia {{---}} Forward–backward algorithm]]<br />
* [http://web.cecs.pdx.edu/~mperkows/JUNE1a/010.Intorduction-to-HMM.ppt Forward/Backward Algorithms for Hidden Markov Models]<br />
* [http://faculty.washington.edu/fxia/courses/LING572/forward_backward.ppt Forward-backward algorithm, Fei Xia, University of Washington]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Марковские цепи]]</div>81.24.126.202http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B8%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F_%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D1%85_%D1%86%D0%B5%D0%BF%D0%B5%D0%B9&diff=64161Примеры использования Марковских цепей2018-03-11T16:15:05Z<p>81.24.126.202: /* См. также */</p>
<hr />
<div>== Обозначения ==<br />
<br />
Предположим, что проводится серия экспериментов с возможными исходами <tex>s_1,s_2,s_3,...s_n</tex>. Назовём эти исходы '''состояниями'''. <br />
*<tex>p_i^{(0)} </tex> — вероятность того, что мы начинаем в состоянии <tex>s_i</tex>;<br />
*<tex>p_{ij} </tex> — вероятность того, что в результате эксперимента состояние было изменено от состояния <tex>s_i</tex> к состоянию <tex>s_j</tex>; <br />
Если <tex>p_i^{(1)}</tex> вероятность того, что исходом эксперимента будет состояние <tex>s_i</tex>. Тогда<br />
<br />
<tex>p_i^{(1)} = p_1^{(0)}p_{1i} + p_2^{(0)}p_{2i} + p_3^{(0)}p_{3i} + ... +p_n^{(0)}p_{ni}</tex> . <tex> (*) </tex><br />
<br />
<br />
Это означает, что вероятность исхода в состоянии <tex>s_i</tex> равна сумме вероятностей начать эксперимент в некотором другом состоянии и окончить в <tex>s_i</tex>.<br />
Также заметим, что:<br />
<br />
<tex>p_{j1}+p_{j2}+p_{j3}+ ... +p_{jn} = 1</tex>.<br />
*Матрица <tex>T</tex> называется матрицей перехода. В общем случае она имеет вид:<br />
<br />
<tex><br />
\begin{bmatrix}<br />
p_{11} & p_{12} & p_{13} & ... & p_{1n} \\<br />
p_{21} & p_{22} & p_{23} & ... & p_{2n} \\<br />
p_{31} & p_{32} & p_{33} & ... & p_{3n} \\<br />
p_{41} & p_{42} & p_{43} & ... & p_{4n} \\<br />
. & . & . & ... & .\\<br />
. & . & . & ... & .\\<br />
. & . & . & ... & .\\<br />
p_{n1} & p_{n2} & p_{n3} & ... & p_{nn} \\<br />
<br />
<br />
\end{bmatrix}<br />
</tex>.<br />
<br />
<br />
Пусть <br />
<tex> p^{(0)}=</tex> <tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)},... ,p_n^{(0)})</tex> и <br />
<tex> p^{(1)}=</tex> <tex>(p_1^{(1)},p_2^{(1)},p_3^{(1)},...,p_n^{(1)}),</tex><br />
<br />
тогда <br />
<tex> (p_1^{(1)},p_2^{(1)},p_3^{(1)}... ,p_n^{(1)})=</tex><br />
<tex>(p_1^{(0)},p_2^{(0)},p_3^{(0)}.. ,p_n^{(0)})</tex><br />
<tex><br />
\begin{bmatrix}<br />
p_{11} & p_{12} & p_{13} & ... & p_{1n} \\<br />
p_{21} & p_{22} & p_{23} & ... & p_{2n} \\<br />
p_{31} & p_{32} & p_{33} & ... & p_{3n} \\<br />
p_{41} & p_{42} & p_{43} & ... & p_{4n} \\<br />
. & . & . & ... & .\\<br />
. & . & . & ... & .\\<br />
. & . & . & ... & .\\<br />
p_{n1} & p_{n2} & p_{n3} & ... & p_{nn} \\<br />
\end{bmatrix}<br />
</tex>.<br />
<br />
Использование матриц приводит к более компактной записи условий. По своей сути, перемножение строки <tex> p_i^{(0)} </tex> с матрицей <tex> T </tex> эквивалентно уравнению <tex> (*) </tex>, рассмотренному ранее.<br />
<br />
== Прогноз погоды ==<br />
=== Условие ===<br />
Погода классифицируется в прогнозах как ясная, умеренно пасмурная и пасмурная. <br />
<br />
#Если погода ясная, то вероятность, что она будет ясной на следующий день, составляет <tex>0.5</tex>; вероятность, что она будет умеренно пасмурной, равна <tex>0.4</tex>; а вероятность пасмурной погоды на следующий день составляет <tex>0.1</tex>. <br />
#Если погода умеренно пасмурная, то вероятность, что на следующий день она будет ясной, равна <tex>0.3</tex>; вероятность, что погода останется умеренно пасмурной, равна <tex>0.5</tex>; а вероятность пасмурной погоды на следующий день составляет <tex>0.2</tex>.<br />
#Если же погода пасмурная, то вероятность, что она будет ясной на следующий день составляет <tex>0.2</tex>; вероятность что она станет умеренно пасмурной, равна <tex>0.4</tex>; вероятность что на следующий день она останется пасмурной, равна <tex>0.4</tex>.<br />
<br />
<br />
Вопрос 1 : Если вероятность ясной погоды в воскресенье равна <tex>0.6</tex>, а вероятность умеренно пасмурной — <tex>0.4</tex>, то какова вероятность, что погода в понедельник будет ясной?<br />
<br />
Вопрос 2 : Какова вероятность, что во вторник погода будет умеренно пасмурной?<br />
<br />
=== Решение ===<br />
<br />
Если порядок, в котором перечисляются погодные условия, таков: ясно, умеренно пасмурно и <br />
пасмурно, то:<br />
<br />
<tex>p^{(0)} =</tex> <tex>(0.6,0.4,0)</tex>,<br />
<br />
<tex><br />
T = \begin{bmatrix}<br />
0.5 & 0.4 & 0.1 \\<br />
0.3 & 0.5 & 0.2 \\<br />
0.2 & 0.4 & 0.4<br />
\end{bmatrix}<br />
</tex>.<br />
<br />
Следовательно,<br />
<tex>p^{(1)} = </tex> <tex>(0.6,0.4,0) \times</tex><br />
<tex><br />
\begin{bmatrix}<br />
0.5 & 0.4 & 0.1 \\<br />
0.3 & 0.5 & 0.2 \\<br />
0.2 & 0.4 & 0.4<br />
\end{bmatrix}<br />
</tex><br />
<tex> = </tex><br />
<tex>(0.42,0.44,0.14)</tex> <br />
и вероятность, что в понедельник будет ясная погода, равна <tex>0.42</tex>. <br />
<br />
Пусть <tex>p_1^{(2)} </tex> — вероятность того, что во вторник будет ясная погода, <tex>p_2^{(2)} </tex> — вероятность того, что во вторник будет умеренно пасмурно и <tex>p_3^{(2)} </tex> — вероятность того, что во вторник будет пасмурно.<br />
<br />
Пусть <tex>p^{(2)} = </tex> <tex> (p_1^{(2)},p_2^{(2)},p_3^{(2)})</tex>.<br />
<br />
Тогда<br />
<tex>p^{(2)} = </tex> <tex> (0.42,0.44,0.14) \times</tex><br />
<tex><br />
\begin{bmatrix}<br />
0.5 & 0.4 & 0.1 \\<br />
0.3 & 0.5 & 0.2 \\<br />
0.2 & 0.4 & 0.4<br />
\end{bmatrix}<br />
</tex><br />
<tex> = </tex><br />
<tex>(0.37,0.444,0.186)</tex>.<br />
<br />
Следовательно, вероятность того, что во вторник будет умеренно пасмурная погода равна <tex>0.444</tex>. <br />
<br />
<br />
Пусть <tex>p_i^{(m)} </tex> — вероятность, что исходом m-го проведения эксперимента будет состояние <tex>s_i</tex> и <br />
<br />
<tex>p^{(m)} =</tex> <tex>(p_1^{(m)},p_2^{(m)},p_3^{(m)},...,p_n^{(m)}).</tex><br />
<br />
{{Теорема<br />
|id=идентификатор (необязательно), пример: th1. <br />
<br />
|statement=Для любого положительного целого числа <tex>m</tex> выполняется <tex>p^{(m)} =</tex> <tex>p^{(0)} \times T^{(m)}</tex>.<br />
|proof=Докажем теорему, используя индукцию. Было показано (в примере про погоду), что для <tex> m = 1 </tex> утверждение справедливо. Предположим, что оно справедливо для <tex>n=k</tex> , так что <tex>p^{(k)} =</tex> <tex>p^{(0)} \times T^{(k)}.</tex>Поскольку<br />
<br />
<tex>p_j^{(k+1)} = </tex> <tex>p_1^{(k)}p_{1j} +</tex> <tex>p_2^{(k)}p_{2j} +</tex> <tex>p_3^{(k)}p_{3j} +</tex> <tex>p_n^{(k)}p_{nj} </tex> <br />
, то<br />
<tex>p^{(k+1)} = </tex> <tex>p^{(k)} T =</tex> <tex>p^{(0)} T^k T =</tex> <tex>p^{(0)} T^{k+1}.</tex><br />
<br />
<br />
}}<br />
<br />
== Оценка будущих продаж ==<br />
<br />
[[Марковская цепь|Цепи Маркова]] также применяются при оценке будущих продаж. Например, сделав опрос среди покупателей той или иной марки автомобиля о их следующем выборе, можно составить матрицу <tex> T </tex>. <br />
=== Условие ===<br />
В процессе опроса владельцев автомобилей трех американских марок: марки <tex>A</tex>, марки <tex>B</tex>, марки <tex>C</tex>, им был задан вопрос о том, какую торговую марку они бы выбрали для следующей покупки.<br />
<br />
#Среди владельцев автомобилей марки <tex>A</tex> <tex>20 \%</tex> сказали что выберут опять эту же марку, <tex>50 \%</tex> сказали, что они бы перешли на марку <tex>B \%</tex>, а <tex>30 \%</tex> заявили, что предпочли бы марку <tex>C</tex>. <br />
#Среди владельцев автомобилей марки <tex>B</tex> <tex>20 \%</tex> сказали, что перейдут на марку <tex>A</tex>, в то время как <tex>70 \%</tex> заявили, что приобрели бы опять автомобиль марки <tex>B</tex>, а <tex>10 \%</tex> заявили, что в следующий раз предпочли бы марку <tex>C</tex>. <br />
#Среди владельцев автомобилей <tex>C</tex> <tex>30 \%</tex> ответили, что перешли бы на марку <tex>A</tex>, <tex>30 \%</tex> сказали, что перешли бы на марку <tex>B</tex>, а <tex>40 \%</tex> заявили, что остались бы верны той же марке <tex>C</tex>.<br />
<br />
Вопрос 1 : Если некто приобрел автомобиль марки <tex>A</tex>, то какова вероятность, что его второй машиной будет автомобиль марки <tex>C ?</tex><br />
<br />
Вопрос 2 : Если при покупке первой машины покупатель подбросил монету, выбирая между автомобилями марки <tex>B</tex> и <tex>C</tex>, то какова вероятность, что его третьей машиной станет автомобиль марки <tex>B ?</tex><br />
<br />
=== Решение ===<br />
<br />
Матрица перехода для этого события имеет вид:<br />
<br />
<tex><br />
\begin{bmatrix}<br />
0.2 & 0.5 & 0.3 \\<br />
0.2 & 0.7 & 0.1 \\<br />
0.3 & 0.3 & 0.4<br />
\end{bmatrix}<br />
</tex>.<br />
<br />
Для ответа на первый вопрос имеем: <tex>p^{(0)} =</tex> <tex>(1,0,0)</tex> , поэтому <br />
<br />
<tex>p^{(1)} = </tex> <tex>(1,0,0) \times</tex><br />
<tex><br />
\begin{bmatrix}<br />
0.2 & 0.5 & 0.3 \\<br />
0.2 & 0.7 & 0.1 \\<br />
0.3 & 0.3 & 0.4<br />
\end{bmatrix}<br />
</tex><br />
<tex> = </tex><br />
<tex>(0.2,0.5,0.3)</tex>.<br />
<br />
Вероятность того, что вторая машина будет марки <tex>C</tex>, равна <tex>0.3</tex>. Для ответа на второй вопрос требуется найти <br />
<br />
<tex>T^{(2)} = </tex><br />
<tex><br />
\begin{bmatrix}<br />
0.23 & 0.54 & 0.23 \\<br />
0.21 & 0.62 & 0.17 \\<br />
0.24 & 0.48 & 0.28<br />
\end{bmatrix}<br />
</tex>.<br />
<br />
Для <tex>(2)</tex> имеем <tex>p^{(2)} = </tex> <tex> (0,0.5,0.5) </tex> и<br />
<br />
<tex>p^{(2)} = </tex> <tex>(0,0.5,0.5) \times</tex><br />
<tex><br />
\begin{bmatrix}<br />
0.23 & 0.54 & 0.23 \\<br />
0.21 & 0.62 & 0.17 \\<br />
0.24 & 0.48 & 0.28<br />
\end{bmatrix}<br />
</tex><br />
<tex> = </tex><br />
<tex>(0.225,0.55,0.225)</tex><br />
поэтому вероятность того, что второй автомобиль будет марки <tex>A</tex> равна <tex>0.225</tex>.<br />
<br />
==См. также== <br />
*[[Марковская цепь]]<br />
*[[Эргодическая марковская цепь]]<br />
*[[Регулярная марковская цепь]]<br />
*[[Фундаментальная матрица]]<br />
<br />
== Источники информации ==<br />
* ''Марков А. А.'', Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.<br />
* ''Kemeny J. G., Snell J. L.'', Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960 (перевод: ''Кемени Дж. Дж., Снелл Дж. Л.'' Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.)<br />
<br />
[[Категория:Дискретная математика, алгоритмы и структуры данных]]<br />
[[Категория:Марковские цепи ]]</div>81.24.126.202http://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D1%80%D0%B3%D0%BE%D0%B4%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C&diff=64160Эргодическая марковская цепь2018-03-11T16:12:05Z<p>81.24.126.202: /* Классификация эргодических цепей */</p>
<hr />
<div>{{Определение<br />
|definition=<br />
'''Эргодическая''' [[Марковская цепь|марковская цепь]] (англ. ''ergodic Markov chain'') {{---}} марковская цепь, целиком состоящая из одного [[Марковская цепь#sort_def| эргодического класса]].<br />
}}<br />
<br />
==Стационарный режим==<br />
Эргодические марковские цепи описываются [[Отношение связности, компоненты связности|сильно связным графом]]. Это означает, что в такой системе возможен переход из любого состояния <tex>S_i</tex> в любое состояние <tex>S_{j}, (i,j = 1,2,\ldots,n)</tex> за конечное число шагов.<br />
<br />
Для эргодических цепей при достаточно большом времени функционирования (<tex>t \to \infty</tex>) наступает '''стационарный режим''', при котором вероятности <tex>\alpha_i</tex> состояний системы не зависят от времени и не зависят от распределения вероятностей в начальный момент времени, то есть: <tex>\alpha_i = const</tex>.<br />
<br />
== Классификация эргодических цепей ==<br />
<br />
{{Определение<br />
|definition=<br />
В эргодической цепи можно выделить '''циклические классы''' (англ. ''cyclic classes''). Количество циклических классов <tex> d </tex> называют '''периодом цепи''' (англ. ''period of Markov chain''), если цепь состоит целиком из одного циклического класса, её называют [[Регулярная марковская цепь|регулярной]]. С течением времени текущее состояние движется по циклическим классам в определенном порядке, причем каждые <tex>d</tex> шагов она оказывается в одном и том же циклическом классе.<br />
}}<br />
<br />
Таким образом, эргодические цепи делятся на [[Регулярная марковская цепь|регулярные]] и '''циклические'''.<br />
<br />
== Эргодическая теорема ==<br />
{{Определение<br />
|definition=<br />
'''Эргодическое (стационарное) распределение''' (англ. ''stationary distribution'') {{---}} распределение <tex>\alpha = (\alpha_1 \ldots \alpha_n )</tex>, такое что <tex>\alpha_i > 0</tex> и<br />
<tex>\lim\limits_{n \to \infty} p_{ij}^{(n)} = \alpha_j</tex> (где <tex>p_{ij}^{(n)}</tex> {{---}} вероятность оказаться в <tex>j</tex>-ом состоянии, выйдя из <tex>i</tex>-ого, через <tex>n</tex> переходов).<br />
}}<br />
<br />
=== Для регулярных цепей ===<br />
Доказательство теоремы для случая регулярных цепей приведено в конспекте про [[Регулярная марковская цепь#Эргодическая теорема для регулярных цепей | регулярные цепи]].<br />
<br />
=== Для циклических цепей ===<br />
{{<br />
Теорема<br />
|about=Эргодическая теорема<br />
|statement=<br />
Для любой эргодической цепи последовательность степеней <tex>P^{n}</tex> [http://en.wikipedia.org/wiki/Euler_summation суммируется по Эйлеру] к предельной матрице <tex>A</tex>, и эта предельная матрица имеет вид <tex>A = \xi\alpha</tex>, где <tex>\alpha</tex> {{---}} положительный вероятностный вектор, <tex>\xi</tex> - вектор-столбец из единиц.<br />
|proof=<br />
<br />
<br />
В случае циклической цепи переходы из одного циклического класса в другой возможны только при определенных значениях <tex> n </tex>, которые периодически повторяются. Таким образом, никакая степень матрицы переходов <tex>P</tex> не является положительной матрицей, и различные степени содержат нули на различных местах. С увеличением степени расположение этих нулей периодически повторяется. Следовательно, последовательность <tex>P^{n}</tex> не может сходиться в обычном смысле, для нее требуется так называемая суммируемость по Эйлеру.<br />
<br />
Рассмотрим матрицу <tex>(kI + (1 - k)P)</tex> при некотором <tex>k, ~ 0 < k < 1</tex>. Эта матрица является ''переходной матрицей''. Она имеет положительные элементы на всех тех же местах, что и <tex>P</tex>, следовательно, она также ''задает эргодическую цепь''. Также диагональные элементы этой матрицы положительны. Значит, в каждое состояние можно возвратиться за один шаг, а это значит, что <tex>d = 1</tex>. Таким образом, новая цепь является регулярной.<br />
<br />
Из [[Регулярная марковская цепь#Эргодическая теорема для регулярных цепей | эргодической теоремы для регулярных цепей]] следует, что <tex>(kI + (1 - k)P)^{n}</tex> стремится к матрице <tex>A = \xi\alpha</tex>, где <tex>\alpha</tex> {{---}} положительный вероятностный вектор. Таким образом:<br />
: <tex> A = \lim\limits_{x\to \infty} (kI + (1 - k)P)^{n}</tex><br />
: <tex> A = \lim\limits_{x\to \infty} \sum\limits_{i = 0}^{n} {n\choose i} k^{n - i} (1 - k)^{i} P^{i} ~~~~~ (1)</tex><br />
Но последнее равенство в точности означает, что последовательность <tex>P^{n}</tex> суммируема по Эйлеру к <tex>A</tex>, причем суммируема при каждом значении <tex>k</tex>.<br />
}}<br />
<br />
==== Следствия ====<br />
<br />
{{Теорема<br />
|statement=Если <tex>P, A, \alpha</tex> {{---}} объекты из предыдущей теоремы. Тогда справедливы факты:<br />
<br />
* Для любого вероятностного вектора <tex>\pi</tex> последовательность <tex>\pi P^{n}</tex> суммируема по Эйлеру к <tex>\alpha</tex><br />
* Вектор <tex>\alpha</tex> является единственным неподвижным вектором матрицы <tex>P</tex><br />
* <tex>PA = AP = A</tex><br />
|proof=<br />
Домножим <tex>(1)</tex> на <tex>\pi</tex>. Таким образом, мы получим, что предел последовательности <tex>\pi P^{n}</tex> в смысле Эйлера равен <tex>\pi A = \pi \xi \alpha</tex>. Значит, '''первый факт''' доказан.<br />
<br />
<br />
Так как вектор <tex>\alpha</tex> был получен из предельной матрицы для <tex>(kI + (1 - k)P)</tex>, являющейся регулярной переходной матрицей, то он будет её единственным неподвижным вероятностным вектором. Но матрица <tex>(kI + (1 - k)P)</tex> должна иметь те же неподвижные векторы, что и <tex>P</tex>, так как из соотношения <br />
:<tex>\pi (kI + (1 - k)P) = \pi</tex>, <br />
следует, что <br />
:<tex>\pi (1 - k) P = \pi (1 - k)</tex><br />
и поскольку <tex>k \ne 1</tex>, то <tex>\pi P = \pi</tex>. Получается, что '''второй факт''' доказан.<br />
<br />
<br />
'''Третий факт''' следует из того, что <tex>P \xi = \xi</tex> для любой переходной матрицы и что <tex>\alpha P = \alpha</tex>.<br />
}}<br />
<br />
==Пример==<br />
[[File:Ergo.jpg|thumb|250px|Пример циклической цепи]]<br />
Самым простым примером циклической цепи является цепь из двух состояний, с переходной матрицей:<br />
:<tex>P = \begin{pmatrix}<br />
0 & 1 \\ <br />
1 & 0<br />
\end{pmatrix}</tex> .<br />
<br />
Стационарным распределением этой цепи будет <tex> \alpha = (0.5, 0.5) </tex>.<br />
<br />
==Ссылки==<br />
*[http://ru.wikipedia.org/wiki/Эргодическое_распределение Эргодическое распределение {{---}} Википедия]<br />
<br />
*[http://ru.wikipedia.org/wiki/Дискретное_распределение#.D0.94.D0.B8.D1.81.D0.BA.D1.80.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D1.80.D0.B0.D1.81.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F Дискретное распределение {{---}} Википедия]<br />
<br />
*[http://en.wikipedia.org/wiki/Euler_summation Суммируемость по Эйлеру {{---}} Википедия]<br />
<br />
== Источники информации ==<br />
*Дж. Кемени, Дж. Снелл "Конечные цепи Маркова" - Издательство "Наука", 1970 г - 129 c.<br />
<br />
[[Категория:Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Марковские цепи]]</div>81.24.126.202