Математическая культура. Мациевский С.В. - 46 стр.

UptoLike

ВУЗ: 

БФУ им. Канта | Калининград

Составители: 

Рубрика: 

45
п. 3. Цепь Маркова
1. Случайное блуждание. Хорошо известна задача о пьянице, стоящем
между кабачками «Черный кот» (ЧК) и «Золотой дракон» (ЗД). Каждую
минуту он либо передвигается на 10м в сторону ЧК с вероятностью 1/2,
либо в сторону ЗД с вероятностью 1/3, либо остается на месте с вероятно-
стью 1/6. Такое поведение называется
случайным блужданием.
Пусть оба кабачка «поглощающие»: если пьяница попадает в один из
них, то он там и остается, расстояние между кабачками 50м, и пьяница нахо-
дится в 20м от ЗД. Обозначим места, где пьяница может остановиться, через
E
1
, …, E
6
(здесь E
1
и E
6
— ЧК и ЗД соответственно). Тогда его начальное по-
ложение
E
4
задается вектором (строкой чисел) 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
23
= 1/3, p
24
= 0. Заметим,
что все
p
ij
неотрицательны и сумма элементов
любой из строк равна 1.
Цепью Маркова называется пара (P, x), где P есть (n × n)-матрица пере-
хода, а
x есть (1 × n)-вектор-строка — начальный вектор вероятностей.
Позиции
E
i
(в случае с пьяницей этих позиций 6) называются состоя-
ниями
цепи Маркова, и в дальнейшем будут описаны разные способы их
классификации.
Нас интересует следующее: за какое наименьшее время можно попасть
из одного данного состояния в другое. Например, в задаче о пьянице из
E
4
в
E
1
можно попасть за 3 минуты и вообще нельзя попасть из E
1
в E
4
. Итак,
интересны не сами вероятности
p
ij
, а то, положительны они или нет.
Упр. 9. За какое наименьшее время в задаче о пьянице можно попасть
из E
1
в E
6
? А из E
2
в E
6
?
п. 4. Ассоциированный орграф
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
100000
3/16/12/1000
03/16/12/100
003/16/12/10
0003/16/12/1
000001
                            п. 3. Цепь Маркова
    1. Случайное блуждание. Хорошо известна задача о пьянице, стоящем
между кабачками «Черный кот» (ЧК) и «Золотой дракон» (ЗД). Каждую
минуту он либо передвигается на 10м в сторону ЧК с вероятностью 1/2,
либо в сторону ЗД с вероятностью 1/3, либо остается на месте с вероятно-
стью 1/6. Такое поведение называется случайным блужданием.
    Пусть оба кабачка «поглощающие»: если пьяница попадает в один из
них, то он там и остается, расстояние между кабачками 50м, и пьяница нахо-
дится в 20м от ЗД. Обозначим места, где пьяница может остановиться, через
E1, , E6 (здесь E1 и E6 — ЧК и ЗД соответственно). Тогда его начальное по-
ложение E4 задается вектором (строкой чисел) x = (0, 0, 0, 1, 0, 0), i-я компо-
нента которого равна вероятности того, что он сначала находится в Ei.
    Легко посчитать, что по прошествию одной минуты вероятности его
местоположения описываются вектором (0, 0, 1/2, 1/6, 1/3, 0).
    Упр. 8. Выпишите вектор местоположения пьяницы через две минуты.
    Теперь понятно, что вычисление вероятности нахождения пьяницы в
заданном месте по прошествии k минут становится затруднительным.
    2. Определение. Назовем вектором вероятностей вектор-строку, все
компоненты которого неотрицательны и дают в сумме единицу. Тогда
матрица перехода P — это квадратная матрица, т.е. квадратная таблица, в
которой каждая строка является вектором вероятностей. Каждый элемент
матрицы pij называется вероятностью перехода
из позиции Ei (которой соответствует строка ⎛ 1 0 0 0 0 0 ⎞
                                                  ⎜1 / 2 1 / 6 1 / 3 0 0 0 ⎟
матрицы) в позицию Ej.                            ⎜                                ⎟
    В нашем случае имеем (6 × 6)-матрицу ⎜           0   1 / 2 1 / 6 1 / 3  0    0 ⎟
P = (pij). Например, p23 = 1/3, p24 = 0. Заметим, ⎜  0     0   1 / 2 1 / 6 1 / 3 0 ⎟
                                                  ⎜ 0 0 0 1/ 2 1/ 6 1/ 3 ⎟
что все pij неотрицательны и сумма элементов ⎜                                     ⎟
любой из строк равна 1.                           ⎝ 0 0 0 0 0 1 ⎠
    Цепью Маркова называется пара (P, x), где P есть (n × n)-матрица пере-
хода, а x есть (1 × n)-вектор-строка — начальный вектор вероятностей.
    Позиции Ei (в случае с пьяницей этих позиций 6) называются состоя-
ниями цепи Маркова, и в дальнейшем будут описаны разные способы их
классификации.
    Нас интересует следующее: за какое наименьшее время можно попасть
из одного данного состояния в другое. Например, в задаче о пьянице из E4
в E1 можно попасть за 3 минуты и вообще нельзя попасть из E1 в E4. Итак,
интересны не сами вероятности pij, а то, положительны они или нет.
    Упр. 9. За какое наименьшее время в задаче о пьянице можно попасть
из E1 в E6? А из E2 в E6?
                    п. 4. Ассоциированный орграф
                                        45

Страницы