Марковские процессы. Основные понятия и задачи, решаемые с помощью Марковских процессов

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

1. Степени при стремятся к стохастической матрице .
2. Каждая строка матрицы представляет один и тот же вероятностный вектор все компоненты которого положительны.

    Вектор в теории ДМЦ занимает особое место из-за наличия многих приложений и называется вектором предельных или финальных вероятностей (иногда - стационарным вектором). Финальные вероятности определяют с помощью векторно-матричного уравнения

которое в развернутом виде будет выглядеть  так:

     Так же, как и в случае поглощения ДМЦ многие характеристики эргодических цепей определяются с помощью фундаментальной матрицы, которая в этом случае будет иметь вид:

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

где

- фундаментальная матрица (15);

- диагональная матрица, образованная  из фундаментальной заменой всех  элементов, кроме диагональных, нулями;

D - диагональная  матрица с диагональными элементами, ;

Е - матрица, все элементы которой равны единице.

 

5. Управляемые Марковские цепи

 

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

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

1. конечное множество решений (альтернатив) , где - номер состояния системы;
2. матрицы переходов соответствующие тому или иному принятому k-му решению;
3. матрицы доходов (расходов) , также отражающие эффективность данного решения.

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

     Таким образом, процесс функционирования системы, описываемой УЦМ, выглядит следующим образом:

        если система находится в состоянии и принимается решение , то она получает доход ;

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

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

       Стратегией p называется последовательность решений:

где

- вектор управления.

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

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

        Оптимальной будет такая стратегия, которая максимизирует полный ожидаемый доход для всех i и n. В теории УМЦ разработаны два метода определения оптимальных стратегий: рекуррентный и итерационный.

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

где

- полный ожидаемый доход;

шагов, если система находится в состоянии i;

- непосредственно ожидаемый доход,  т.е. доход на одном шаге, если  процесс начался с i-го состояния;

- величина полного ожидаемого  дохода за n прошедших шагов, если  процесс начинался с j-го состояния  (i¹ j).

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

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

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

 

 

6. Марковские случайные процессы с непрерывным временем

       Итак, снова модель Марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i-го состояния в j-е состояние), см. рис. 3.1..

          Теперь каждый переход характеризуется плотностью вероятности перехода λ_ij. По определению:

       При этом плотность понимают как распределение вероятности во времени.

       Переход из i-го состояния в j-е происходит в случайные моменты времени, которые определяются интенсивностью перехода λ_ij.

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

     Зная интенсивность λ_ij появления событий, порождаемых потоком, можно сымитировать случайный интервал между двумя событиями в этом потоке.

где τ_ij — интервал времени между нахождением системы в i-ом и j-ом состоянии.

       Далее, очевидно, система из любого i-го состояния может перейти в одно из нескольких состояний j, j + 1, j + 2, …, связанных с ним переходами λ_ij, λ_ij + 1, λ_ij + 2, ….

       В j-е состояние она перейдет через τ_ij; в (j + 1)-е состояние она перейдет через τ_ij + 1; в (j + 2)-е состояние она перейдет через τ_ij + 2 и т. д.

       Ясно, что система может перейти из i-го состояния только в одно из этих состояний, причем в то, переход в которое наступит раньше.

       Поэтому из последовательности времен: τ_ij, τ_ij + 1, τ_ij + 2 и т. д. надо выбрать минимальное и определить индекс j, указывающий, в какое именно состояние произойдет переход.

       Рассмотрим пример. Моделирование работы станка. Промоделируем работу станка (см. рис. 3.2.), который может находиться в следующих состояниях: S₀ — станок исправен, свободен (простой); S₁ — станок исправен, занят (обработка); S₂ — станок исправен, замена инструмента (переналадка) λ₀₂ < λ₂₁; S₃ — станок неисправен, идет ремонт λ₁₃ < λ₃₀.

      Зададим значения параметров λ, используя экспериментальные данные, получаемые в производственных условиях: λ₀₁ — поток на обработку (без переналадки); λ₁₀ — поток обслуживания; λ₁₃ — поток отказов оборудования; λ₃₀ — поток восстановлений.

       Реализация будет иметь следующий вид (рис. 3.2.).