Далее: §12. Аксиоматика теории вероятностей Вверх: Глава II. Случайные события Назад: §10. Вероятность и числовые

§11. Цепи Маркова

Пусть {$E_{1}$, $E_{2}$, ...,$E_{k}$} - множество состояний некоторой физической системы. В любой момент времени система может находиться в одном состоянии и меняет свое состояние только в моменты $t_{1}$, $t_{2}$, ..., $t_{n}$, .... Для однородных цепей Маркова вероятность $p_{ij}$ перехода системы из состояния $E_{i}$ в состояние $E_{j}$ за один шаг зависит только от того, из какого состояния в какое осуществлялся переход.

Вероятности перехода $p_{ij}$удобно располагать в виде матрицы. Обозначим ее

$${\bf P}=\left[\matrix{p_{11}&p_{12}&...&p_{1k}\cr p_{21}&p_{... ...p_{2k}\cr ...&...&&...\cr p_{k1}&p_{k2}&...&p_{kk}\cr }\right]$$

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

а) $0\le p_{ij}\le 1;$ б) $\sum\limits_{j = 1}^k {р_{ij} = 1}$ ($i$= 1, 2, ..., $k)$;

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

Вектор $a=(a_{1},a_{2},\ldots a_{k})$, где $a_{i}=P(E_{i})$ - вероятность появления состояния $E_{i}$ ($i$ = 1, 2, ..., $k)$ в начальном испытании, называется вектором начальных вероятностей.

Свойства однородных марковских цепей полностью определяются вектором начальных вероятностей и матрицей вероятностей перехода. В некоторых случаях вместо матрицы P используют ориентированный граф, вершинами которого являются состояния цепи, а стрелка, идущая от состояния $E_{i}$ в состояние $E_{j}$ с числом $p_{ij}$ рядом с ней, показывает, что из состояния $E_{i}$ возможен переход в состояние $E_{j}$ с вероятностью $p_{ij}$. В том случае, когда $p_{ij}=$0, соответствующее ребро не проводится. В случае однородных цепей Маркова с вектором начальных вероятностей появляется еще начальная вершина графа, которая соединяется с состоянием $E_{i}$ ребром с числом $a_{i}$ рядом с ним.

Можно показать, что матрица перехода P$^{(n)}$ за $n$ шагов находится как $P^{n}$.

Если из состояния $E_{i}$ система может перейти в состояние $E_{j}$ с положительной вероятностью за конечное число шагов, то говорят, что $E_{j}$ достижимо из $E_{i}$. Состояние $E_{i}$ называется существенным, если для каждого состояния $E_{j}$, достижимого из$E_{i}, E_{i}$ достижимо из $E_{j}$. В противном случае $E_{i}$ называется несущественным состоянием.

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

Пример 51. Частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты $t_{1}$, $t_{2}$, $t_{3}$, ...Частица может находиться в точках с целочисленными координатами 1, 2, 3, 4, 5; в точках 1 и 5 находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью $р$ и влево с вероятностью $q$, если частицы не находятся у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка [1,5]. Найти матрицу перехода P и ей соответствующий граф.

Решение. Пусть $E_{i}=(t)$, $i$ = 1, 2, 3, 4, 5. Тогда граф перехода выглядит следующим образом:

Рис. 33

а матрица перехода -

$$\begin{array}{@{\extracolsep{-5pt}}cccl} &&& E_{1} E_{2} E... ... \\ 0&0&q&0&p \\ 0&0&0&1&0 \\ \end{array}\right] \end{array}$$

Пример 52. Вероятности перехода за один шаг в цепях Маркова задаются матрицей:

$$\begin{array}{@{\extracolsep{-5pt}}cccl} &&& E_{1} ... ... 0&0&2/3&1/3 \\ 0&0&1/2&1/2 \\ \end{array}\right] \end{array}$$

Требуется:

а) найти число состояний;

б) установить, сколько среди них существенных и несущественных;

в) построить граф, соответствующий матрице P.

Решение.

а) 4 состояния.

б) состояния $E_{1}$, $E_{2}$ несущественны, поскольку остальные состояния достижимы из них, но $E_{1}$ недостижимо из $E_{4}$, а $E_{2}$ недостижимо из $E_{3}$; состояния $E_{3}$ и $E_{4}$ являются существенными.

в)

Рис. 34

Пример 53 (задача о скрещивании). В близко родственном скрещивании две особи, и среди их прямых потомков случайным образом выбираются две особи разного пола. Они вновь скрещиваются, и процесс этот продолжается бесконечно. Каждый родительский ген может передаваться с вероятностью $1/2$, и последовательные испытания независимые. Имея три генотипа AA, Aа, аа для каждого родителя, мы можем различать шесть комбинаций родителей, которые пометим следующим образом:

$E_{1}$=AA $\times$ AA, $E_{2}$= AA $\times$ Aа, $E_{3}$= AA $\times$ аа, $E_{4}$= Aа $\times$ Aа, $E_{5}$= Aа $\times$ аа, $E_{6}$= аа $\times$ аа. Найдите граф и матрицу перехода.

Решение. $E_1 \buildrel 1 \over \longrightarrow E_1 .$ Рассмотрим, какое потомство и с какой вероятностью может быть у особей разного пола, если они выбираются из $E_{2}$.

Пусть $B_{i}$ = {$i$-й потомок}, $i$ = 1, 2 и $B_{1}$, $B_{2}$ - разного пола, тогда варианты потомков и их вероятности можно найти по следующему графу:

Рис. 35

Получаем, что $E_2 \buildrel {4/16}\over \longrightarrow E_1 ,$ $E_2 \buildrel {4/2}\over \longrightarrow E_2 ,$ $E_2 \buildrel {4/4}\over \longrightarrow E_4 .$

Аналогично, находим и вероятности других переходов:

$$\begin{array}{l} E_3 \buildrel 1 \over \longrightarrow E_4 ... ..., E_6 \buildrel 1 \over \longrightarrow E_6 . \\ \end{array}$$

Тогда искомый граф перехода выглядит следующим образом:

Рис. 36

а матрица перехода -

$${\bf P}=\left[\matrix{1& 0& 0& 0& 0& 0 \cr 1/4&1/2&0&1/4&0&0... .../4&1/4&1/16\cr 0&0&0&1/4&1/2&1/4\cr 0&0&0&0&0&1 \cr } \right].$$

Пример 54. Матрица вероятностей перехода цепи Маркова имеет вид:

$${\bf P}=\left[\matrix{ 0,2&0,3&0,5 \cr 0,5& 0,2&0,3 \cr 0,6&0,1&0,3 \cr } \right].$$

Распределение по состояниям в момент времени $t$ = 0 определяется вектором $(0,6, 0,1, 0,3)$. Найти распределения по состояниям в момент $t$ = 2.

Решение. Построим граф, соответствующий вектору начальных вероятностей и матрице перехода:

Рис. 37

По этому графу находим распределение по состояниям в момент $t$ = 2:

$P(E_{1})$ = (0,6$\cdot$(0,2)$^{2}$ + 0,6$\cdot$ 0,3$\cdot$ 0,5+0,6$\cdot$ 0,5$\cdot$ 0,6)+(0,1$\cdot$ 0,5$\cdot$ 0,2+0,1$\cdot$ 0,2$\cdot$ 0,5 +0,1$\cdot$ 0,3$\cdot$ 0,6)+(0,3$\cdot$ 0,6$\cdot$ 0,2+(0,3)$^{2}\cdot$ 0,6)+(0,3$\cdot$ 0,1$\cdot$ 0,5)=0,437;

$P(E_{2})$ = (0,1$\cdot$ (0,2)$^{2}$+0,1$\cdot$ 0,5$\cdot$ 0,3+0,1$\cdot$ 0,3$\cdot$ 0,1)+0,6$\cdot$ 0,3$\cdot$ 0,2+0,6$\cdot$ 0,2$\cdot$ 0,3 +0,6$\cdot$ 0,5$\cdot$ 0,1)+(0,3$\cdot$ 0,1$\cdot$ 0,2+(0,3)$^{2}\cdot$0,1+0,3$\cdot$ 0,6$\cdot$ 0,3)=0,193;

$P(E_{3})$ = 0,37.

Пример 55. Доказать, что P$^{(n)}$= P$^{n}$ для двух состояний цепи Маркова.

Решение. Пусть цепь Маркова с двумя состояниями $E_{1}$ и $E_{2}$ задана своей матрицей перехода P:

$${\bf P} = \left[ {\begin{array}{cc} p_{11} & p_{12} \\ p_{21} & p_{22} \\ \end{array}} \right]$$

Докажем утверждение методом математической индукции.

Пусть $n$ = 2. Тогда

$${{\bf P}}^2 = \left[{\begin{array}{cc} p_{11} & p_{12} \\ ... ... p_{22}& p_{21}\cdot p_{12}+p^2_{22} \\ \end{array}}\right].$$

Вероятности перехода за два шага удобно находить по графу перехода:

Рис. 38

$${\bf P}^2= \begin{array}{@{\extracolsep{-5pt}}cccl} &&&\qqua... ..._{21}\cdot p_{12}+p_{22}^{2}\\ \end{array}\right]. \end{array}$$

Следовательно, P$^{(2)}$ = P$^{2}$, и первый шаг метода математической индукции выполняется. Предположим далее, что при $n = k$ проверяемое утверждение истинно, т.е. P$^{(k)}$ = P$^{k}$, тогда матрица перехода за $k$+1 шаг P$^{(k + 1)}$ = P$^{(k)} \cdot$ P = P$^{k} \cdot$ P = P$^{k + 1}$, что и требовалось доказать.

Вопросы для самоконтроля

1. Что такое цепь Маркова?
2. Какие цепи Маркова называются однородными?
3. Как задаются однородные цепи Маркова?
4. Какие матрицы называются стохастическими?
5. Граф перехода цепи Маркова.
6. Как находится матрица перехода за $n$ шагов?
7. Какое состояние системы называется существенным?
8. Вектор начальных вероятностей.

Задачи

I 101. Вероятности перехода задаются матрицей

$${{\bf P}} = \left[ {\begin{array}{ccc} 1 / 2&1 / 3&1/6 \\ 1 / 2&1 / 3&1/6 \\ 1 / 2&1 / 3&1/6 \\ \end{array}} \right].$$

Чему равно число состояний? Найти вероятности перехода из одного состояния в другое за два шага.

  102. Дана матрица вероятностей перехода

$${{\bf P}} = \left[ {\begin{array}{l} 1 / 3 \\ 1 / 5 \\ ... ... {\begin{array}{l} 2 / 3 \\ 4 / 5 \\ \end{array}} \right]$$

и вектор начальных вероятностей $\vec {a}\left( {{\displaystyle 3\over\displaystyle 4},{\displaystyle 1\over\displaystyle 4}} \right).$ Найти распределение по состояниям в момент $t$= 2.

  103. Система находится в одной из вершин правильного шестиугольника, причем в соседние вершины она переходит с вероятностью 1/6, а в противоположную - с вероятностью 2/3. Найти матрицу и граф перехода.

  104. Матрица вероятностей перехода цепи Маркова имеет вид

$${{\bf P}} = \left[ {\begin{array}{ccc} 0,4&0,5&0,1 \\ 0,2&0,3&0,5\\ 0,3&0,4&0,3 \\ \end{array}}\right].$$

Вектор начальных вероятностей $\vec {a}(0,1;0,2;0,7).$ Найти вероятность того, что через два шага система будет находиться в состоянии $E_{3}$.

  105. Частица находится в одном их трех состояний $E_{1}$, $E_{2}$, $E_{3}$, которые выбираются в начальный момент с вероятностями 1/2, 1/3, 1/6 соответственно. Под воздействием случайных толчков система переходит в другое состояние с вероятностью 1/4 и остается на месте с вероятностью 1/2. Найти вероятность того, что через два толчка система будет находиться в состоянии $E_{1}$.

  106. Вероятности перехода за один шаг в цепи Маркова задаются матрицей

$$\left[\matrix{ 0&2/5&3/5&0\cr 1/4&3/4&0&0\cr 0&2/3&0&1/3\cr 0&1/2&0&1/2\cr} \right].$$

Найти число состояний и определить среди них существенные и несущественные. Построить граф, соответствующий матрице P.

II 107. Бросаем игральную кость и условимся, что в момент $n$ система находится в состоянии E$_{i}$, если $i$ - наибольшее из чисел, выпавших в первых $n$ бросаниях. Найти матрицу перехода P и ей соответствующий граф.

  108. Рассмотрим последовательность испытаний Бернулли и определим, что в момент времени $n$ наблюдается состояние $E_{1}$, если испытания с номерами $n-1,$ $n$ привели к результату YY. Аналогично $E_{2}$, $E_{3}$, $E_{4}$ означают переходы YH, HY, HH. Найти матрицу перехода P и все ее степени.

III 109. Доказать, что для однородной цепи Маркова с матрицей вероятностей перехода P = (p$_{ij})$ имеют место следующие соотношения:

а) $p_{ij}^{(n)} = \sum\limits_{m = 1}^k {p_{im} \cdot p_{mj}^{(n - 1)} (n = 2,3,...);}$

б) P$^{(n)}$ = P$^{n}$.

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

Далее: §12. Аксиоматика теории вероятностей Вверх: Глава II. Случайные события Назад: §10. Вероятность и числовые