Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

3.14. Марковские процессы - с дошкольных лет

Как это ни парадоксально звучит, но с марковскими процессами мы знакомы еще с дошкольного возраста. Каждому известна детская игра, в которой фишки участников должны переместиться из начального пункта A0 ("старт") в конечный Ak ("финиш"). Попав в тот или иной промежуточный пункт Aj, фишка может либо приблизиться к финишу (за счет "льготы", предусмотренной условиями

"игры), либо удалиться от него (за счет "штрафа"). Число шагов, на которое фишка перемещается из занимаемого ею пункта Ai в пункт Aj, определяется числом очков, выпавшим на брошенной игральной кости. Поэтому вероятность того, что фишка из пункта Ai переместится в Aj, не зависит от того, каким путем фишка оказалась в позиции Ai,а определяется лишь вероятностью pij выпадения соответствующего числа очков на грани кости. Возникает ситуация, в точности характерная для марковского процесса с дискретным (конечным) множеством состояний A0, A1,..., Ai,.., Aj,..., Ak и дискретным временем. Счет моментов переходов из одного состояния в другое заменяется счетом числа самих переходов. Позиции Ai (i = 0, ..., k) ассоциируются с состояниями системы S игры. Тогда карту игры с изображенными на ней позициями и вероятностями переходов из каждой позиции в последующие можно считать графом соответствующей цепи. Граф этот, как правило, куда сложнее изменения счета в гейме или сете.

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

В таких процессах "будущее зависит от прошлого только через настоящее". Или иначе: случайный процесс называют марковским, если при любом его состоянии S0 вероятностные характеристики процесса в последующем зависят только от настоящего состояния S0 и не зависят от того, когда и каким образом система пришла в это состояние.

Уточним данное определение. Рассмотрим некоторую систему S, которая в любой момент времени может находиться только в одном из n несовместных состояний S1,..., Sn. В нашем примере - это состояния счета в процессе игры в теннис. Пусть состояние системы меняется в зависимости от некоторого параметра t, причем переход из состояния в состояние зависит от вмешательства случая. Параметр t можно условно назвать временем и считать, что он изменяется либо непрерывно, либо принимает некоторую последовательность t1, t2, ..., tn значений (в нашем примере - это моменты завершения розыгрыша очередного мяча).

Процесс, описывающий поведение такой системы, называют конечной цепью Маркова при выполнении следующего условия: если в данный момент времени τ система находится в состоянии Si, то в следующий момент i>τ система будет находиться в состоянии Sj с некоторой вероятностью Pij(τ, t), которая не зависит от поведения системы до момента τ.

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

Если принять τ = 0 и в процессах с дискретным временем моменты t1, ..., tn, ... отождествить с индексами 1, 2, ..., и, ..., то можно упростить обозначения: Pij (τ, tk) = Pij(0,k) = Pij(k) и Pij(ti, tk) = pij(k - l). В частности, для любых соседних моментов времени l и l + 1 имеем Pij(t1, tl+1) = Pij(1). Эти величины и есть вероятности перехода из любого состояния Si в другое Sj (включая вероятность Pii(1) задержки в состоянии Si) за один шаг. Переходные вероятности Pij(1) = Pij образуют матрицу переходов конечной марковской цепи:


В каждой i-й строке матрицы находятся вероятности переходов из одного и того же состояния Si в любое возможное Sj. Естественно, что сумма переходных вероятностей в каждой строке равна единице:

Pi1 + Pi2 + ... + Pin = 1 (i = 1, 2, ..., n).

Примером такой матрицы может служить матрица T переходных вероятностей для периода случайного блуждания при завершении гейма (см. с. 35). Зная матрицу переходов , можно подсчитать вероятности переходов системы из состояния Si в состояние Sj за n шагов. Так, в частности, переходные вероятности Pij(2) за два шага составляют матрицу 2, которая получается возведением в квадрат матрицы :2 = 2. Переходные вероятности Pij(n) за n шагов образуют матрицу, равную n-й степени :n = n. Именно так мы поступали, рассматривая завершающую фазу розыгрыша гейма, а также тай-брейка.

Итак, на примере моделирования игры в теннис мы познакомились со случайным марковским процессом с дискретными состояниями; переход из состояния в состояние в таких процессах происходит мгновенно. Если же система не скачком (мгновенно), а постепенно, с течением времени переходит из одного состояния в другое, то говорят о процессе с непрерывными состояниями. В том случае, когда переходы реализуются в заранее фиксированные моменты времени t1, t2, ..., tn, ..., говорят о процессе с дискретным временем; при возможности переходов в случайные моменты времени - о процессах с непрерывным временем*.

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

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

Некоторые из процессов могут протекать весьма длительно и при неограниченном возрастании времени t приобретать стационарный характер. В этом режиме вероятности состояний оказываются постоянными (не зависящими от времени) и называются финальными. Финальные вероятности находят уже из системы линейных алгебраических уравнений, в которые превращаются в этом случае дифференциальные. Обширное приложение марковские процессы нашли в теории массового обслуживания - одного из разделов теории исследования операций. Заинтересовавшегося читателя отсылаем к уже упомянутым монографиям [1; 25].

предыдущая главасодержаниеследующая глава



ИНТЕРЕСНО:

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru