Схема Бернулли. Цепи Маркова (стр. 6 из 11)
Другой пример: если цепь Маркова имеет матрицу перехода, приведенную на рис. 4, то ассоциированный орграф этой цепи выглядит так, как показано на (рис. 5).
Рис. 3
Рис. 4
Рис. 5
Теперь ясно, что в цепи Маркова из состояния
в состояние 
можно попасть в том и только в том случае, если в ассоциированном орграфе существует орцепь из 
в 
, и что наименьшее возможное время попадания равно длине кратчайшей из таких орцепей. Цепь Маркова, в которой из любого состояния можно попасть в любое другое, называется неприводимой. Ясно, что цепь Маркова неприводима тогда и только тогда, если ее ассоциированный орграф сильно связан. Заметим, что ни одна из описанных выше цепей не является неприводимой.При дальнейших исследованиях принято различать те состояния, в которые мы продолжаем возвращаться независимо от продолжительности процесса, и те, в которые мы попадаем несколько раз и никогда не возвращаемся. Более точно это выглядит так: если начальное состояние есть
и вероятность возвращения в на некотором более позднем шаге равна единице, то называется возвратным (или рекурсивным) состоянием. В противном случае состояние называется невозвратным. В задаче об осле, например, очевидно, что состояния 
и 
являются возвратными, тогда как все другие состояния — невозвратными. В более сложных примерах вычисление нужных вероятностей становится очень хитрым делом, и поэтому проще бывает классифицировать состояния, анализируя ассоциированный орграф цепи. Нетрудно понять, что состояние возвратно тогда и только тогда, если существование простой орцепи из в в ассоциированном орграфе влечет за собой существование простой орцепи из в . В орграфе, изображенном на (рис. 3), существует простая орцепь из 
в 
, но нет ни одной орцепи из в . Следовательно, состояния и, аналогично, 
невозвратны ( 
возвратны). Состояние (такое, как 
), из которого нельзя попасть ни в какое другое, называется поглощающим состоянием.Другой прием классификации состояний опирается на понятие периодичности состояний. Состояние
цепи Маркова называется периодическим с периодом 
, если в можно вернуться только по истечении времени, кратного . Если такого не существует, то состояние называется непериодическим. Очевидно, что каждое состояние , для которого 
, непериодическое. Следовательно, каждое поглощающее состояние — непериодическое. В задаче об осле не только поглощающее состояние 
, но и все остальные являются непериодическими. С другой стороны, во втором примере (рис. 5) поглощающее состояние — единственное непериодическое состояние, поскольку 
имеют период два, а 
— период три. Используя терминологию орграфов, легко показать, что состояние является периодическим с периодом тогда и только тогда, если в ассоциированном орграфе длина каждой замкнутой орцепи, проходящей через , кратна .И, наконец, для полноты изложения введем еще одно понятие: назовем состояние цепи Маркова эргодическим, если оно одновременно возвратно и непериодично. Если любое состояние цепи Маркова является эргодическим, то назовем ее эргодической цепью.
Пример 8. Частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты t1, t2, t3, ...Частица может находиться в точках с целочисленными координатами 1, 2, 3, 4, 5; в точках 1 и 5 находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью q, если частицы не находятся у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка [1,5]. Найти матрицу перехода P и ей соответствующий граф.
Решение. Пусть Ei=(t) ,i= 1, 2, 3, 4, 5. Тогда граф перехода выглядит следующим образом:
Рис. 6
а матрица перехода –
Пример 9. Вероятности перехода за один шаг в цепях Маркова задаются матрицей:
Требуется:
а) найти число состояний;
б) установить, сколько среди них существенных и несущественных;
в) построить граф, соответствующий матрице P.
Решение.
а) 4 состояния.
б) состояния E1, E2 несущественны, поскольку остальные состояния достижимы из них, но E1 недостижимо из E4, а E2 недостижимо из E3; состояния E3 и E4 являются существенными.
Рис. 7. в)
Пример 10 (задача о скрещивании). В близко родственном скрещивании две особи, и среди их прямых потомков случайным образом выбираются две особи разного пола. Они вновь скрещиваются, и процесс этот продолжается бесконечно. Каждый родительский ген может передаваться с вероятностью 1/2, и последовательные испытания независимые. Имея три генотипа AA, Aа, аа для каждого родителя, мы можем различать шесть комбинаций родителей, которые пометим следующим образом: