ВУЗ:
Составители:
Рубрика:
78
что для любых состояний s
i
и s
j
в графе существует путь из вершины s
i
в
вершину s
j
длиной t для всех t ≥ t
0
.
Рассматриваемая цепь Маркова не является эргодической. Цепь
Маркова, соответствующая графу на рис. 42, а, эргодическая, но не регу-
лярная. В отличие от последней, цепь, представленная графом на рис. 42, б,
является регулярной.
Отметим, что если граф эргодической цепи Маркова имеет по край-
ней мере одну петлю, то цепь регулярна.
Задачи и упражнения
1. Шесть человек, сидящих за круглым столом, играют в кости. Ес-
ли у игрока, бросающего кость, выпадает 1, 3 или 5 очков, то он отдаёт
кость своему соседу слева; если выпадает 2 или 4 очка, то он отдаёт кость
игроку, сидящему справа от него через одного игрока; если выпадает
6 очков, то он оставляет кость у себя и бросает её снова.
Представьте эту игру цепью Маркова: задайте множество состояний,
приведите матрицу переходов и изобразите соответствующий этой цепи
граф. Проанализируйте, является ли эта цепь эргодической.
Определите вероятности нахождения кости у каждого из игроков
после одного, двух и трёх бросаний, если изначально кость находилась у
игрока номер 3.
2. Найдите минимальное значение t
0
, которое удовлетворяет усло-
вию регулярности цепи, представленной графом на рис. 42, б.
16. КРАТЧАЙШИЕ ПУТИ В ГРАФАХ
Рассмотрим взвешенный ориентированный граф G = <V, U> с мно-
жеством вершин V и множеством дуг U.
Пусть вес каждой дуги u
∈
U является некоторым действительным
числом, называемым длиной дуги. Тогда длина пути из некоторой верши-
s
1
s
2
s
3
s
4
Рис. 42
s
1
s
2
s
3
s
4
а)
б)
Страницы
- « первая
- ‹ предыдущая
- …
- 76
- 77
- 78
- 79
- 80
- …
- следующая ›
- последняя »
