Марковские процессы с дискретным множеством состояний.Цепи Маркова

Марковские процессы с дискретным множеством состояний. Цепи Маркова Случайным процессом называется семейство случайных величин , зависящих от параметра , который пробегает некоторое множество значений . Предполагается, что все эти случайные величины определены на одном и том же вероятностном пространстве и принимают действительные значения. Множество значений будем называть пространством состояний, а под параметром будем понимать время. Так что величина указывает состояние системы в момент времени . Множество значений может быть дискретным , или непрерывным .Иногда вместо будем использовать обозначение . Определение. Случайный процесс называется марковским, если для любого момента времени развитие процесса в последующие моменты времени (при) зависит только от состояния процесса в момент времени и не зависит от того, когда и как процесс пришел в это состояние. Пусть некоторый физический объект в каждый момент времени может находиться в одном из своих возможных состояний, число которых конечно или счетно. В этом случае иногда говорят о дискретном множестве состояний. Состояния могут быть качественными и описываться словами, или количественными и характеризоваться некоторыми числами. Представление о множестве состояний и о структуре переходов из состояния в состояние дает схема, которая называется графом состояний. Будем стрелками обозначать возможные переходы, а через – возможные состояния. Рис. 1 Например, в графе состояний (рис.1) означает, что устройство новое и не включено в работу, – устройство работает, – устройство неисправно, – происходит поиск причин неисправности, – производится ремонт, – устройство признано не подлежащим ремонту и утилизировано. Если ремонт удался, то происходит переход в состояние . Взаимное расположение состояний в графе позволяет их классифицировать следующим образом: • Состояние называется источником, если объект может выйти из него, но попасть вновь в него не может (в приведенном примере состояние ). • Состояние называется поглощающим (или концевым), если в него можно войти, но из него выйти нельзя (в приведенном примере состояние). • Состояние называется соседним к состоянию , если возможен непосредственный переход из состояния в состояние . В приведенном примере соседнее состояние по отношению к , но не соседнее состояние по отношению к . • Подмножество состояний называется эргодическим (или связным), если из каждого состояния этого подмножества можно попасть в любое другое состояние этого подмножества. Рис. 2 Например, в графе (см. рис.2) два эргодических подмножества состояний: и . Случайный процесс изменения состояний объекта можно понимать как процесс блуждания по множеству состояний графа. С точки зрения описания объекта первостепенный интерес представляют вероятности состояний этого объекта. Обозначим через –вероятность того, что в момент времени объект находится в состоянии . Очевидно, что . Часто интерес представляет лишь установившийся режим работы (или стационарный режим), в который объект входит после достаточно долгого времени работы. При стационарном режиме процесс перехода из состояния в состояние продолжается, но вероятности состояний не изменяются. Обозначим эти вероятности через . Так что. Величину можно понимать как среднюю долю времени, в течение которой объект находится в состоянии . В общем случае зависят от всей предыстории переходов из состояния в состояние до момента времени . Это чрезвычайно усложняет математическую модель такого процесса. В математическом плане наиболее просты марковские процессы, не обладающие «памятью» о прошлом. Еще раз повторим, что случайный процесс с дискретным множеством состояний называется марковским, если для любого момента времени вероятность каждого из его состояний в будущем (при ) зависит только от его состояния в настоящий момент и не зависит от того, когда и как процесс пришел в это состояние. Если переходы из состояния в состояние могут происходить только в определенные моменты времени , , , …, то процесс называют цепью Маркова. Моменты переходов из состояния в состояние называют шагами процесса. Наглядным примером марковской цепи могут служить детские игры, в которых продвижение фишки зависит от выпадения той или иной грани игрального кубика. Важными характеристиками Марковской цепи являются условные вероятности перехода системы на -м шаге в состояние , если на предыдущем -м шаге она была в состоянии . Обозначим эти вероятности через и назовем их переходными вероятностями. Вероятность можно понимать, как вероятность сохранить свое состояние на -м шаге. Переходные вероятности удобно записывать в виде прямоугольной таблицы (квадратной матрицы): . Эту матрицу называют матрицей переходных вероятностей или просто переходной матрицей. Так как на каждом шаге система находится в одном из своих возможных состояний, то для любой строки матрицы сумма ее элементов равна единице. Матрицы, обладающие этим свойством, называют стохастическими. Для однозначного в вероятностном смысле описания процесса переходов из состояния в состояние нужно, помимо переходных матриц, указать начальное распределение состояний, т.е. вероятности , , , …, . Обычно процесс начинается из определенного состояния . Тогда , а при . Цепь Маркова называется однородной, если переходные вероятности не меняются от шага к шагу, т.е. , и мы имеем одну и ту же матрицу перехода на каждом шаге. Заметим, что каждому графу состояний для однородной цепи соответствует определенная переходная матрица. Рис. 3 Графу состояний (рис. 3)соответствует переходная матрица , где , , , , (это вероятности сохранить свое состояние на очередном шаге). Пусть задано распределение состояний в начальный момент времени: , , , …, . По формуле полной вероятности получаем распределение состояний после первого шага: , . Используя полученные вероятности, можно по формуле полной вероятности вычислить вероятности состояний на втором шаге: , . Продолжение этих рассуждений приводит к рекуррентному соотношению , (1) При определенных условиях цепи Маркова входят в стационарный режим, при котором переходы из состояния в состояние продолжаются, но вероятности переходов не изменяются и не зависят от номера шага. Эти вероятности называют финальными или предельными. Будем обозначать финальные вероятности через . Условия существования финальных вероятностей: 1. Множество всех состояний должно быть эргодическим. 2. Цепь должна быть однородной (во всяком случае, переходные вероятности должны удовлетворять условию ). 3. Должно быть хорошее перемешивание состояний (не должно быть периодических циклов). Например, для цепи с графом состояний условие 3) не выполняется, так как при начале из состояния на нечетном шаге цепь будет находиться в состоянии , а на четном – в состоянии . Если для однородной цепи финальное распределение существует, то , , и равенства (1) имеют вид , . Иногда в этой записи выделяют слагаемые в правой части с . Тогда или , . (2) Для определения финальных вероятностей нужно решить систему линейных однородных уравнений (2). Такая система всегда совместна, (имеет тривиальное решение при всех i). Если же есть нетривиальные решения, то их бесконечно много. Для выбора необходимого единственного решения следует добавить условие нормировки . Это равенство можно добавить вместо одного из уравнений системы (2). Итак, для нахождения финальных вероятностей состояний Марковской цепи нужно решить систему уравнений , ; . (3) Пример 30. Граф состояний марковской цепи изображен на рис. 4. При начальном распределении , , найти наименее вероятное состояние на третьем шаге. Найти финальные вероятности состояний цепи. Рис. 4. Решение. Переходная матрица этой цепи имеет вид . Найдем вероятности состояний цепи на первом шаге. Воспользуемся формулой (1), но учтем, что переходные вероятности на каждом шаге одинаковы (цепь однородная) и поэтому : ; ; . На втором шаге имеем вероятности состояний: ; ; . Для третьего шага получаем вероятности: ; ; . По наименьшей из вероятностей , , , заключаем, что наименее вероятное состояние на третьем шаге – состояние . Для определения финальных вероятностей записываем систему равенств (3): . Решая систему по правилу Крамера, получим , , . Эти результаты означают, что примерно 20% времени цепь проведет в состоянии , 10% времени – в состоянии , 70% времени – в состоянии . Пример 31. В городе N каждый житель имел одну из профессий A, B или C. Дети в следующем поколении сохраняли профессию отцов с вероятностями соответственно 0,6, 0,2 и 0,4 и с равными вероятностями выбирали любую из двух других профессий. Если в данный момент профессию A имеет 20% жителей города, профессию B – 30%, а профессию C – 50%жителей, то 1. каково распределение по профессиям будет в следующем поколении; 2. каким будет распределение по профессиям через много поколений (финальное распределение)? Решение. Смену поколений будем считать шагом Марковской цепи. Имеем начальное распределение (на нулевом шаге): Переходная матрица имеет вид: A B C A 0,6 0,2 0,2 B 0,4 0,2 0,4 C 0,3 0,3 0,4 В соответствии с формулами (1) получаем распределение вероятностей на первом шаге (в первом поколении): ; ; . Для вычисления финальных вероятностей составляем систему уравнений (2) ; ; . Эта система уравнений при условии нормировки имеет решение , , . Пример 32. Устройство состоит из двух блоков (например, двигатель и ходовая часть). Пусть A означает безотказную работу первого блока, B – безотказную работу второго блока. По истечении каждой единицы времени проверяется состояние этих блоков, и в случае неисправности производится их ремонт. Вероятность безотказной работы блоков в течение единицы времени равны соответственно 0,9 и 0,8. Если неисправность блока обнаружена, то вероятность отремонтировать блок в течение единицы времени равна соответственно 0,3 и 0,4. Найти предельные вероятности для состояний устройства: , , , . Замечание. В сформулированном примере по умолчанию предполагается, что распределение времени безотказной работы и распределение времени ремонта каждого блока не имеют «памяти» о прошлом. Единственным распределением такого сорта является показательное распределение. Если, например, время ремонта распределено по показательному закону и ремонт уже продолжается некоторое время, то оставшаяся часть времени ремонта имеет то же самое распределение, что и в начале ремонта. Решение. Поскольку состояния блоков наблюдаются в конце каждой единицы времени, то моменты наблюдения можно считать шагами однородной марковской цепи. Учитывая независимость времени безотказной работы и времени ремонта узлов, определим переходные вероятности: 0,9·0,8 0,9·0,2 0,1·0,8 0,2·0,1 0,9·0,4 0,9·0,6 0,1·0,4 0,1·0,6 0,3·0,8 0,3·0,2 0,7·0,8 0,7·0,2 0,3·0,4 0,3·0,6 0,7·0,4 0,7·0,6 В итоге переходная матрица имеет вид . Составим систему уравнений для определения финальных вероятностей: , , , . Это система линейных однородных уравнений, она имеет бесконечно много решений. Для получения единственного нужного нам решения вместо любого из уравнений запишем условие нормировки . Решая систему по формулам Крамера, получим , , , . Пример 33. В зоне обслуживания бригады ремонтников находится три прибора, работающих в автоматическом режиме. В конце каждого месяца ремонтники проводят профилактический осмотр приборов и, в случае обнаружения неисправных, забирают их для ремонта или замены на новые. Отремонтированный (или новый) прибор возвращают на место при очередном профилактическом осмотре, т.е. через месяц. Вероятность выхода из строя в течение месяца работающего прибора равна 1/3. Требуется найти стационарное распределение вероятностей числа исправных приборов в начале каждого месяца. Решение. Рассмотрим марковскую цепь, состояния которой будем различать по числу работоспособных приборов. Пусть – означает, что работоспособны i приборов. Всего имеется четыре возможных состояния: , , , . Составим переходную матрицу этой цепи. Если на данном шаге цепь находится в состоянии , то на очередном шаге будут доставлены три работоспособных прибора и цепь с вероятностью 1 перейдет в состояние . Поэтому , а . Если на данном шаге цепи имеется только один работоспособный прибор, то на следующем шаге будет поставлено два новых прибора и вероятность перехода равна вероятности того, что имеющийся в наличии прибор сохранит свою работоспособность, т.е. . Вероятность же перехода равна вероятности выхода из строя имеющегося прибора, т.е. , а . При наличии на данном шаге двух годных приборов в соответствии с формулой Бернулли, имеем переходные вероятности: , , , . Наконец, при трех годных приборах на данном шаге , , , . Запишем переходную матрицу: . Этой переходной матрице соответствует система уравнений (2) для вычисления стационарных вероятностей: . Решая эту систему уравнений, с учетом условия нормировки , получаем , , , .