П. 3. Цепь Маркова

1. Случайное блуждание. Хорошо известна задача о пьянице, стоящем между кабачками «Черный кот» (ЧК) и «Золотой дракон» (ЗД). Каждую минуту он либо передвигается на 10м в сторону ЧК с вероятностью 1/2, либо в сторону ЗД с вероятностью 1/3, либо остается на месте с вероятно­стью 1/6. Такое поведение называется случайным блужданием.

Пусть оба кабачка «поглощающие»: если пьяница попадает в один из них, то он там и остается, расстояние между кабачками 50м, и пьяница находится в 20м от ЗД. Обозначим места, где пьяница может остановиться, через E ₁­, …, E ₆ (здесь E ₁ и E ₆ — ЧК и ЗД соответственно). Тогда его начальное положение E ₄ задается вектором (строкой чисел) x = (0, 0, 0, 1, 0, 0), i -я компонента кото­рого равна вероятности того, что он сначала находится в E _i.

Легко посчитать, что по прошествию одной минуты вероятности его местоположения описываются вектором (0, 0, 1/2, 1/6, 1/3, 0).

Упр. 8. Выпишите вектор местоположения пьяницы через две минуты.

Теперь понятно, что вычисление вероятности нахождения пьяницы в заданном месте по прошествии k минут становится затруднительным.

2. Определение. Назовем вектором вероятностей вектор-строку, все компоненты которого неотрицательны и дают в сумме единицу. Тогда матрица перехода P — это квадратная матрица, т.е. квадратная таблица, в которой каждая строка является вектором вероятностей. Каждый элемент матрицы p_ij называется вероятностью перехода из позиции E_i (которой соответствует строка матрицы) в позицию E_j.

В нашем случае имеем (6 ´ 6)-матрицу P = (p_ij). Например, p ₂₃ = 1/3, p ₂₄ = 0. Заметим, что все p_ij неотрицательны и сумма элементов любой из строк равна 1.

Цепью Маркова называется пара (P, x), где P есть (n ´ n)-матрица пере­хода, а x есть (1 ´ n)-вектор-строка — начальный вектор вероятностей.

Позиции E_i (в случае с пьяницей этих позиций 6) называются состояниями цепи Маркова, и в дальнейшем будут описаны разные способы их классификации.

Нас интересует следующее: за какое наименьшее время можно попасть из одного данного состояния в другое. Например, в задаче о пьянице из E ₄ в E ₁ можно попасть за 3 минуты и вообще нельзя попасть из E ₁ в E ₄. Итак, интересны не сами вероятности p_ij, а то, положительны они или нет.

Упр. 9. За какое наименьшее время в задаче о пьянице можно попасть из E ₁ в E ₆? А из E ₂ в E ₆?