Вероятностно-временные характеристики цепи Маркова

Распределение вероятностей состояний цепи Маркова является наиболее важной её характеристикой. Но также представляют интерес и некоторые другие её характеристики.

Вероятность перехода из несущественного состояния в замкнутый класс.

Обозначим P _i (S_k) вероятность перехода цепи Маркова из несущественного состояния i в замкнутый класс S_k, p_ij - вероятности перехода из i -го состояния в j -ое. Тогда P _i (S_k) является решением неоднородной системой линейных алгебраических уравнений следующего вида.

,

где T - множество несущественных состояний.

Среднее время перехода из несущественного состояния в замкнутый класс.

Пусть для цепи Маркова единственный замкнутый класс S. Обозначим m_i (S) – среднее значение времени перехода цепи Маркова из несущественного состояния i в замкнутый класс S. Учитывая, что если из состояния i можно сразу попасть в класс S_k, то время перехода равно единице, а если этот переход выполняется в несущественное состояние j, тогда суммарное время перехода составляет 1+ m_j (S), где первое слагаемое, равное единице, определяет первый шаг, а второе: m_j (S) – среднее значение времени перехода из состояния j в класс S.

В силу формулы полной вероятности для условных математических ожиданий, можно записать систему линейных неоднородных уравнений для определения m_i (S):

.

Пример 2.7. Студент может перейти на следующий курс с вероятностью p, с вероятностью q может остаться на повторное обучение, а с вероятностью r может быть отчислен (p+q+r=1). Восстановление невозможно, но с вероятностью pможно вновь поступить на первый курс. Записать матрицу вероятностей переходов за один шаг и найти среднее время перехода в эргодическое множество.

Решение: Будем считать, что образование занимает 5 лет, тогда состояния S ₁, S ₂, S ₃, S ₄, S ₅– соответствуют обучению с первого по пятый курс, S ₀, – абитуриент, S ₆ – специалист. По определению S ₀, S ₁, S ₂, S ₃, S ₄, S ₅ – несущественные состояния, S ₆ – эргодическое множество из одного состояния.

Тогда матрица переходов за один шаг в каноническом виде может быть записана

Через m_i обозначим среднее время перехода из несущественного состояния S_i, в эргодическое состояние S ₆. Тогда можно записать систему уравнений:

Будем решать систему методом Крамера. Найдем определитель системы:

,

Найдем D _i:

,

,

,

,

,

.

Следовательно, .

Аналогично находим для остальных состояний, и записываем ответ в общем виде.

Ответ: , .

Если цепь Маркова содержит k замкнутых классов, то для нахождения среднего времени перехода из несущественного состояния в k -ый замкнутый класс S_k, необходимо учитывать вероятность перехода в этот замкнутый класс, то есть находить условное время перехода m_i (S_k/H_k), где H_k – событие, состоящее в том, что из i -го состояния мы перешли в k -ый замкнутый класс. Это время перехода определяется равенством:

,

где m_i (S_k/H_k) определяется аналогично m_i (S) для цепи Маркова с единственным замкнутым классом состояний.

Пример 2.8. Найдите вероятность и условное среднее время перехода из несущественного состояния в замкнутый класс для цепи Маркова, заданных матрицей переходов за один шаг систем

.

Решение: Граф состояний для заданной цепи Маркова имеет вид

Очевидно, что у рассматриваемой цепи состояние 3 – несущественное и есть два неразложимых класса S ₁ = {1}, S ₂ = {2}.

Следовательно, рассмотри две гипотезы:

H₁ - произошел переход в замкнутый S₁;

H₂ - произошел переход в замкнутый S₂.

Тогда условное среднее время перехода из несущественного состояния в замкнутые классы S ₁ и S ₂ определяется по формулам:

,

,

где P₃(H_i) – вероятность события H_i, то есть вероятность перехода из несущественного состояния 3 в i -ый замкнутый класс.

Вероятности перехода из несущественного состояния 3 в замкнутые классы S ₁и S ₂ определяем по формулам

,

.

Откуда получаем: , .

Для m ₃(S ₁, H ₁) и m ₃(S ₂, H ₂) имеем систему уравнений:

, ;

, .

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

,

.

Среднее время перехода из состояния в состояние внутри замкнутого класса

Рассмотрим некоторый замкнутый класс S. Обозначим m_ij – среднее значение времени перехода из состояния i в состояние j внутри замкнутого класса для " i, j Î S.

Тогда можно получить систему линейных неоднородных алгебраических уравнений, определяющих значения m_ij:

.

Из полученной системы можно найти следующие соотношения:

, , (2.4)

из которых следует, что среднее время возвращения в возвратное состояние j обратно пропорционально финальной вероятности этого состояния, поэтому для положительных состояний оно конечно, а для нулевых – бесконечно.

Распределение вероятностей времени пребывания в j-м состоянии

Обозначим n _j – время (число тактов) пребывания системы в состоянии j. Достаточно очевидны следующие равенства

,

,

,

то есть время пребывания системы в любом состоянии имеет геометрическое распределение с параметром равным p_jj – вероятности остаться в этом состоянии на следующем шаге.

Среднее значение времени пребывания в j -м состоянии составляет

.

Статистический смысл стационарных (финальных) вероятностей

Обозначим T_j – среднее число шагов от момента выхода из j -го состояния до момента возвращения цепи Маркова в это состояние, тогда по формуле полной вероятности можно записать

,

тогда, равенство (2.4) перепишем следующим образом

.

Здесь числитель равен среднему значению времени, проведённому системой в j -ом состоянии, а знаменатель равен сумме этого значения и среднему значению длины интервала от момента выхода цепи из j -го состояния до момента возвращения в него. Следовательно, стационарные (финальные) вероятности для цепи Маркова можно интерпретировать как среднее значение доли времени, проведённого цепью в j -ом состоянии.

Задачи для самостоятельного решения

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

2. На окружности отмечено 5 точек. Процесс попадает из любой данной точки в одну из соседних с вероятностью 0, 5. Записать матрицу переходов за один шаг. Найти матрицу переходов за 2, 3 шага.

3. В учениях участвуют два корабля, которые одновременно производят выстрелы друг в друга через равные промежутки времени. При каждом выстреле корабль А поражает корабль Б с вероятностью 1/2, а корабль Б поражает корабль А с вероятностью 3/8. Предполагается, что при любом попадании корабль выходит из строя. Рассматриваются результаты серии выстрелов. Найти матрицу перехода, если состояниями цепи являются комбинации кораблей, оставшихся в строю: Е₁ – оба корабля в строю, Е₂ – в строю только корабль А, Е₃ – в строю только корабль Б, Е₄ – оба корабля поражены.

4. В сказочной стране Оз никогда не бывает двух солнечных дней подряд. Если сегодня ясно, то завтра будет плохая погода – снег или дождь с равной вероятностью. Если сегодня дождь, то завтра погода изменится с вероятностью 0, 5. Если она изменится, то в половине случаев будет ясно. Записать матрицу переходов за один шаг. Найти вероятность того, что послезавтра будет ясно, если сегодня ясно.

5. N -черных и N -белых шаров размещены по двум урнам так, что в каждой из них по N шаров. Число черных шаров первой урны определяет состояние системы. На каждом шаге случайно выбираются по одному шару из каждой урны и меняются местами. Записать матрицу вероятностей переходов за один шаг. И найти финальные вероятности.

6. Пусть целые числа M > 0 и N > 0 (M+N=L) – начальные капиталы соответственно первого и второго игроков. Проводятся последовательно игры, в результате каждой из которых с вероятностью капитал первого игрока увеличивается на 1 и с вероятностью q =1– p капитал первого игрока уменьшается на 1. Результаты любой игры не зависят от результатов любых других игр. Пусть S_n – капитал первого игрока после n игр. Предполагается, что в случае S_n =0 или S_n = N + M игра прекращается (ситуация разорения одного игрока). Построить стохастический граф цепи, провести классификацию состояний и найти переходную матрицу. Найти вероятность разорения первого игрока. Рассмотреть случай, когда один из игроков бесконечно богат. Указание: граф переходов имеет вид:

7. Через фиксированные промежутки времени проводится контроль технического состояния банкомата, который может находиться в одном из трех состояний: S ₁ – работает, S ₂ – не работает и ожидает ремонта, S ₃ – ремонтируется. Предполагается, что процесс, характеризующий состояние прибора является однородной цепью Маркова с переходной матрицей

.

Найти неизвестные элементы матрицы P и вычислить P (2) при условии, что в начальный момент времени банкомат был исправен. Найти среднее время перехода внутри замкнутого класса.

8. Классифицировать состояния для марковской цепи, заданной матрицей вероятностей переходов P ₁, записать ее в каноническом виде и найти среднее время перехода из одного состояния в другое внутри замкнутого класса (все возможные варианты).

; ;

; ;

; .

9. Две автомашины A и B сдаются в аренду по одной и той же цене. Каждая из них может находиться в одном из двух состояний: i₁ – машина работает хорошо, i₂ – машина требует ремонта, которые образуют цепь Маркова. Матрицы вероятностей переходов между состояниями за сутки для этих машин равны соответственно:

.

Определить финальные вероятности состояний для обеих автомашин. Какую автомашину стоит арендовать?

10. Цепь Маркова задана графом (рис.4). Найти стационарное распределение вероятностей, если оно существует.

Рис. 4.

11. Цепь Маркова имеет множество допустимых состояний E={0, 1, 2, …, N} и описывается графом (рис.5), где 0< p< 1, q=1–p. Доказать, что цепь является эргодической, и найти стационарное распределение вероятностей.

Рис. 5.

12. Провести классификации состояний и записать матрицы переходов в каноническом виде для следующих цепей Маркова

a) ; б) ;

в) ; г) ;

е) , .

13. Цепь Маркова имеет множество состояний {-6, -5, …, 0, 1, …, 6}. Переходные вероятности определяются соотношениями

Провести классификацию состояний цепи Маркова и множества ее состояний, если выполняются равенства:

а) ;

б) ;

в) .

14. Цепь Маркова задана матрицей переходов за один шаг. Найдите финальные вероятности состояний цепи Маркова.

a) ; б) ;

в) ; г) .

15. Найдите вероятность и условное, при условии попадания в S_k, среднее время перехода из несущественного состояния в замкнутый класс для цепи Маркова, заданных матрицей вероятностей переходов за один шаг.

a) ; в) ;

б) ; г) .

16. Найдите вероятность и среднее время перехода из несущественного состояния в замкнутый класс для цепи Маркова, заданных графом вероятностей переходов за один шаг:

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

17. Найдите вероятность и условное среднее время перехода из несущественного состояния в замкнутый класс для цепи Маркова, заданных графом вероятностей переходов за один шаг:

Найдите среднее время перехода внутри замкнутых классов.

18. В процессе эксплуатации ЭВМ может рассматриваться как физическая система, которая в результате проверки может оказаться в одном из следующих состояний: x₁ – ЭВМ полностью исправна; x₂ – ЭВМ имеет незначительные неисправности в ОП, но может решать задачи; x₃ – ЭВМ имеет существенные неисправности, может решать ограниченный класс задач; x₄ – ЭВМ полностью вышла из строя. В начальный момент ЭВМ полностью исправна. Проверка ЭВМ производится в фиксированные моменты времени t₁, t₂, t₃. Процесс, протекающий в системе, можно рассматривать как цепь Маркова. Матрица перехода за один шаг имеет вид:

.

Определить вероятности состояний после трех проверок.

19. Автомашина может находиться в двух состояниях: i ₁ – работает хорошо, i ₂ – требует ремонта. На следующий день работы она меняет свое состояние в соответствии с матрицей вероятностей переходов

.

Пусть

– если машина работает нормально, мы имеем прибыль $40;

– когда она начинает работу в нормальном состоянии, а затем требует ремонта (либо наоборот), прибыль равна $20;

– если машина требует ремонта, то потери составляют $20.

Найдите ожидаемую прибыль за два перехода между состояниями (за два шага).

Указание.Пусть матрица доходов за один шаг, тогда – вектор прибыли за один шаг.

20. В городе N каждый житель имеет одну из трех профессий А, В, С. Дети отцов, имеющих профессии А, В, С сохраняют профессии отцов с вероятностями 3/5, 2/3, 1/4 соответственно, а если не сохраняют, то с равными вероятностями выбирают любую из двух других профессий. Найти:

1) распределение по профессиям в следующем поколении, если в данном поколении профессию А имело 20%, профессию В – 30%, профессию С – 50%;

2) распределение по профессиям, не меняющееся при смене поколений.

21. Найдите среднее время перехода внутри замкнутых классов, если матрица вероятностей переходов имеет вид

а) ; б) ;

в) ; г) .

22. Цепь Маркова задана матрицей вероятностей перехода P за один шаг и вектором начального распределения

, .

Найти:

а) несущественные состояния;

б) среднее время выхода иp множества несущественных состояний;

в) вероятности попадания в замкнутые классы и из несущественных состояний.

23. Из таблицы случайных чисел, содержащей все целые числа от 1 до m включительно, по одному выбираются числа наудачу. Система находится в состоянии Q_j, если наибольшее из выбранных чисел равно j (j =1, 2, …, m). Найти вероятности того, что после выбора n чисел наибольшее будет k, если раньше было i.

Указание. Найдите матрицу переходов за один шаг P, тогда p _ik (n) – элементы матрицы P_n.

24. M молекул, распределенных в двух резервуарах, случайно по одной перемещаются из своего резервуара в другой. Найти финальные вероятности числа молекул в первом резервуаре.

25. Независимые испытания проводятся до тех пор, пока не будет получена серия из m последовательных появлений события A, вероятность появления которого при каждом испытании равна p. Определить среднее число испытаний t_k, которые нужно провести для получения требуемой серии, если уже имеется серия из k последовательных появлений этого события (k =0, 1, 2, …, m -1).. Рассчитать t_k при m =3, p =0, 5 и k =0, 1, 2.

26. Из урны содержащей N черных и N белых шаров одновременно извлекаются m шаров, вместо которых кладут m черных шаров. Число белых шаров определяет состояние системы. Определите вероятности того, что после n извлечений в урне останется k белых шаров. Рассчитать вероятности при N =6, m =3.

27. Отрезок АВ разделен на m равных интервалов. Частица может находиться только в серединах интервалов, перемещаясь скачками на величину интервала по направлению к точке А с вероятностью p, а по направлению к точке В с вероятностью q =1– p. В крайних точках отрезка имеются отражающие экраны, которые при достижении частицей точки А или В возвращают ее в исходное положение. Определить финальные вероятности нахождения частицы в каждом интервале.

28. Вероятности перехода для цепи Маркова с бесконечным числом состояний определяются равенствами. Определить финальные вероятности, если они существуют.

а) , ;

б) , ;

в) , , , .

29. Цепь Маркова задана графом вероятностей переходов

где 0< p < 1, q =1– p. Докажите, что цепь является эргодической, и найдите стационарное распределение вероятностей состояний

30. Эргодическая цепь Маркова с двумя состояниями имеет стационарное распределение p₀= p, p₁=1– p. Найдите матрицу вероятностей переходов за один шаг.