Научная библиотека

2. СЛУЧАЙНЫЕ ПРОЦЕССЫ С ДИСКРЕТНЫМ И НЕПРЕРЫВНЫМ ВРЕМЕНЕМ. МАРКОВСКАЯ ЦЕПЬ

Способы математического описания марковского случайного процесса, протекающего в системе с дискретными состояниями, зависят от того, в какие моменты времени — заранее известные или случайные — могут происходить переходы («перескоки») системы из состояния в состояние.

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

Случайный процесс называется процессом с непрерывным временем, если переход системы из состояния в состояние возможен в любой, наперед неизвестный, случайный момент

Рассмотрим прежде всего марковский случайный процесс с дискретными состояниями и дискретным временем.

Пусть имеется физическая система S, которая может находиться в состояниях:

причем переходы («перескоки») системы из состояния в состояние воз можны только в моменты:

Будем называть эти моменты «шагами» или «этапами» процесса и рассматривать случайный процесс, происходящий в системе S, как функцию целочисленного аргумента: (номера шага).

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

или

В общем случае в моменты система может не только менять состояние, но и оставаться в прежнем, например:

Рис. 4.6

Условимся обозначать событие, состоящее в том, что после шагов система находится в состоянии При любом k события

образуют полную группу и несовместны.

Процесс, происходящий в системе, можно представить как последовательность (цепочку) событий, например:

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

Мы будем описывать марковскую цепь с помощью так называемых вероятностей состояний. Пусть в любой момент времени (после любого, шага) система S может быть в одном из состояний:

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

Обозначим вероятности этих событий:

— вероятности после первого шага,

— вероятности после второго шага; и вообще после шага:

Легко видеть, что для каждого номера шага к

так как это — вероятности несовместных событий, образующих полную группу.

Рис. 4.7

Будем называть вероятности

вероятностями состояний; поставим задачу: найти вероятности состояний системы для любого к.

Изобразим состояния системы в виде графа (рис. 4.6), где стрелками указаны возможные переходы системы из состояния в состояние за один шаг.

Случайный процессе (марковскую цепь) можно представить себе так, как будто точка, изображающая систему S, случайным образом перемещается (блуждает) по графу состояний, перескакивая из состояния в состояние в моменты а иногда (в общем случае) и задерживаясь какое-то число шагов в одном и том же состоянии. Например, последовательность переходов

можно изобразить на графе состояний как последовательность различных положений точки (см. пунктирные стрелки, изображающие переходы из состояния в состояние на рис. 4.7). «Задержка» системы в состоянии на третьем шаге изображена стрелкой, выходящей из состояния и в него же возвращающейся.

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

Будем называть эти вероятности переходными вероятностями марковской цепи.

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

Рис. 4.8

Рассмотрим сначала однородную марковскую цепь. Пусть система S имеет возможных состояний Предположим, что для каждого состояния нам известна вероятность перехода в любое другое состояние за один шаг (в том числе и вероятность задержки в данном состоянии). Обозначим вероятность перехода за один шаг из состояния S, в состояние будет вероятность задержки системы в состоянии Запишем переходные вероятности в виде прямоугольной таблицы (матрицы):

Некоторые из переходных вероятностей могут быть равны нулю: это означает, что за один шаг переход системы из состояния в невозможен. По главной диагонали матрицы переходных вероятностей стоят вероятности того, что система не выйдет из состояния а останется в нем.

Пользуясь введенными выше событиями переходные вероятности можно записать как условные вероятности:

Отсюда следует, что сумма членов, стоящих в каждой строке матрицы (2.3), должна быть равна единице, так как, в каком бы состоянии система ни была перед шагом, события несовместны и образуют полную группу.

При рассмотрении марковских цепей часто бывает удобно пользоваться графом состояний, на котором у стрелок проставлены соответствующие переходные вероятности (см. рис. 4.8). Такой граф мы будем называть «размеченным графом состояний».

Заметим, что на рис. 4.8 проставлены не все переходные вероятности, а только те из них, которые не равны нулю и меняют состояние системы, т. е. при «вероятности задержки» проставлять на графе излишне, так как каждая из них дополняет до единицы сумму переходных вероятностей, соответствующих всем стрелкам, исходящим из данного состояния. Например, для графа рис. 4.8

Если из состояния S; не исходит ни одной стрелки (переход из него ни в какое другое состояние невозможен), соответствующая вероятность задержки равна единице.

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

после любого шага.

Покажем, как это делается.

Предположим, что в начальный момент (перед первым шагом) система находится в каком-то определенном состоянии, например, Тогда, для начального момента (0) будем иметь:

т. е. вероятности всех состояний равны нулю, кроме вероятности начального состояния которая равна единице.

Найдем вероятности состояний после первого шага. Мы знаем, что перед первым шагом система заведомо находится в состоянии

Значит, за первый шаг она перейдет в состояния с вероятностями

записанными в строке матрицы переходных вероятностей. Таким образом, вероятности состояний после первого шага будут:

Найдем вероятности состояний после второго шага:

Будем вычислять их по формуле полной вероятности, с гипотезами:

— после первого шага система была в состоянии

— после первого шага система была в состоянии

— после первого шага система была в состоянии

— после первого шага система была в состоянии

Вероятности гипотез известны (см. (2.4)); условные вероятности перехода в состояние при каждой гипотезе тоже известны и записаны в матрице переходных вероятностей. По формуле полной вероятности получим:

или, гораздо короче,

В формуле (2.6) суммирование распространяется формально на все состояния фактически учитывать надо только те из них, для которых переходные вероятности отличны от нуля, то есть те состояния, из которых может совершиться переход в состояние (или задержка в нем).

Таким образом, вероятности состояний после второго шага известны. Очевидно, после третьего шага они определяются аналогично:

и вообще после шага:

Итак, вероятности состояний после шага определяются рекуррентной формулой (2.8) через вероятности состояний после шага; те, в свою очередь через вероятности состояний после шага, и т. д.

Пример 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени

Возможные состояния цели (системы ):

— цель невредима;

— цель незначительно повреждена;

— цель получила существенные повреждения;

— цель полностью поражена (не может функционировать). Размеченный граф состояний системы показан на рис. 4.9.

В начальный момент цель находится в состоянии (не повреждена). Определить вероятности состояний цели после четырех выстрелов Решение. Из графа состояний имеем;

Рис. 4.9

Аналогично находим;

Таким образом, матрица переходных вероятностей имеет вид;

Так как в начальный момент цель S находится в состоянии , то

Вероятности состояний после первого шага (выстрела) берутся из первой строки матрицы:

Вероятности состояний после второго шага:

Вероятности состояний после третьего шага:

Вероятности состояний после четвертого шага:

Таким образом, нами получены вероятности всех исходов обстрела цели (четырех выстрелов):

— цель не повреждена:

— цель получила незначительные повреждения:

— цель получила существенные повреждения:

— цель поражена полностью: .

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

Рассмотрим теперь общий случай — неоднородную марковскую цепь, для которой вероятности перехода меняются от шага к шагу. Обозначим — вероятность перехода системы из состояния в состояние на шаге, то есть условную вероятность

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

которая отличается от аналогичной формулы (2.8) для однородной цепи Маркова только тем, что в ней фигурируют вероятности перехода, зависящие от номера шага k. Вычисления по формуле (2.9) ничуть не сложнее, чем в случае однородной цепи.

Пример 2. Производится три выстрела по цели, которая может быть в тех же четырех состояниях что и в предыдущем примере, но вероятности перехода для трех последовательных выстрелов различны и заданы тремя матрицами:

В начальный момент цель находится в состоянии Найти вероятности состояний после трех выстрелов.

Решение. Имеем:

Итак, вероятности состояний после трех выстрелов: