Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Анализ цепей Маркова с использованием графов

Часто решение системы уравнений для стационарных вероятностей весьма затруднительно. В этом случае можно воспользоваться методом графов (§ 5.4). На рис. 12.10 показан граф Мэзона для системы уравнений

Граф Мэзона регулярной цепи Маркова с двумя состояниями

Рис. 12.10. Граф Мэзона регулярной цепи Маркова с двумя состояниями

Финальные вероятности можно найти как функции передачи от узла С до соответствующего узла. Изображенный граф содержит один прямой путь от узла С до узла 1 — это Рх = я21, два одиночных контура Qu = яии 02| = -я21. Отсюда по формуле Мэзона определитель А = 1 — я,, + я21, а функция передачи от узла С до узла 1

Функция передачи от узла С до узла 2:

При использовании графов нам не пришлось обращать матрицу.

Среднее время перехода из одного состояния в другое рассчитаем также с помощью сигнальных графов.

Граф перехода состояний

Рис. 12.11. Граф перехода состояний

В соответствии с матрицей переходных вероятностей

граф перехода системы с двумя состояниями изображен на рис. 12.11. Если в начале процесса система находится в состоянии 1, то среднее время первого достижения состояния 2 будет равно среднему времени нахождения системы в состоянии 1 и среднему времени перехода по дуге из состояния 1 в состояние 2. Напомним, что выражение «время перехода по дуге» используется условно для упрощения изложения. В действительности система находится данное время в рассматриваемом состоянии и затем мгновенно переходит по дуге в другое состояние.

Пусть время перехода по дугам одинаково и равно 1. Среднее время нахождения системы в состоянии 1 вычисляется по (10.31), где для рассматриваемого случая Ф,х (0) = 1 - а. При Г,, = 1 получим

Результирующее время первого достижения эквивалентно переходу по последовательности двух дуг. Время перехода по последовательности N дуг вычисляется по (10.21). Поэтому с учетом времени перехода по дуге (1,2) получим среднее время первого достижения системой состояния 2 из состояния /:

Аналогично можно показать, что среднее время первого достижения системы состояния 1 из состояния 2

Теперь вычислим среднее время первого достижения системы состояния 1 из того же состояния 1. Это время равно времени перехода системы из состояния 1 в состояние 1 и времени перехода системы из состояния 1 сначала в состояние 2, а затем в 1. Этот переход можно представить как переход по параллельным дугам (рис. 12.12).

Эквивалентный граф перехода состояний

Рис. 12.12. Эквивалентный граф перехода состояний

По первой дуге переход осуществляется с вероятностью 1 — а за время Ти] 1. По второй дуге переходосуществляется с вероятностью за время

Согласно (10.28), среднее время перехода по двум дугам Аналогично можно показать, что

Полученные с помощью графов результаты соответствуют результатам, полученным с использованием матричного анализа, причем трудоемкость вычислений значительно меньше.

Согласно теореме Колмогорова, для эргодической цепи Маркова всегда существует предел

который не зависит от начального состояния. Используя эту теорему, можно заключить, что стационарные вероятности состояний

Дисперсия времени перехода. Дисперсию времени первого достижения одного состояния из другого определим с помощью сигнальных графов. Если в начале процесса (см. рис. 12.11) система находится в состоянии 7, то дисперсия времени первого достижения состояния Сбудет равна дисперсии времени нахождения системы в состоянии 7 и дисперсии времени перехода по дуге из состояния 7 в состояние 2. Пусть время перехода по дугам одинаково и равно 1. Среднее время нахождения системы в состоянии 7

Дисперсия времени нахождения системы в петле вычисляется по (10.32). Дисперсия времени прохождения дуги о2 { =0. Отсюда

Дисперсия времени первого достижения состояния 2из состояния 7 соответствует дисперсии времени перехода по последовательности двух дуг. Дисперсия времени перехода по последовательности А дуг вычисляется по (10.22). Так как время перехода по дуге

(1,2) постоянно, то дисперсия этого времени равна 0. Следовательно, дисперсия первого достижения состояния 2 из состояния 7

Аналогично можно показать, что дисперсия времени первого достижения системой состояния 1 из состояния 2

Рассчитаем дисперсию времени первого достижения системой состояния 7 из состояния 7. Эта дисперсия равна дисперсии времени перехода системы из состояния 7 в состояние 7 и дисперсии времени перехода системы из состояния 7 сначала в состояние 2, а затем в 7. Этот переход можно представить как переход по параллельным дугам (см. рис. 12.12).

Дисперсия времени перехода по N параллельным дугам вычисляется по (10.29). По первой дуге переход осуществляется с вероятностью 1 — а за время Г, =1 и дисперсией ст2,, =0. По второй дуге переход осуществляется с вероятностью а за время Г,д2 = (J3+1)/р и с дисперсией ст2, = (1 - р)/р2.

Согласно (10.29), дисперсия времени перехода

Аналогично можно показать, что

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>