Добавить в избранное

Например, полностью граф может выглядеть так, как показано на рис. 33.3 .

Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4 ). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.

Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал на подынтервалы величиной P i 1 , P i 2 , P i 3 , … (P i 1 + P i 2 + P i 3 + … = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале случайное число r рр и определить, в какой из интервалов оно попадает (см. лекцию 23).

После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 33.4 ) .

Пример. Имитация стрельбы из пушки по цели . Для того, чтобы проимитировать стрельбу из пушки по цели, построим модель марковского случайного процесса.

Определим следующие три состояния: S 0 — цель не повреждена; S 1 — цель повреждена; S 2 — цель разрушена. Зададим вектор начальных вероятностей:

Значение P 0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.

Зададим матрицу перехода состояний (см. табл. 33.1).

Матрица задает вероятность перехода из каждого состояния в каждое. Заметим, что вероятности заданы так, что сумма вероятностей перехода из некоторого состояния в остальные всегда равна единице (куда-то система должна перейти обязательно).

Наглядно модель марковского процесса можно представить себе в виде следующего графа (см. рис. 33.6 ).

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

Проимитируем, используя таблицу случайных чисел, процесс стрельбы. Пусть начальное состояние будет S 0 . Возьмем последовательность из таблицы случайных чисел: 0.31, 0.53, 0.23, 0.42, 0.63, 0.21, … (случайные числа можно взять, например, из этой таблицы).

0.31 : цель находится в состоянии S 0 и остается в состоянии S 0 , так как 0 < 0.31 < 0.45;
0.53 : цель находится в состоянии S 0 и переходит в состояние S 1 , так как 0.45 < 0.53 < 0.45 + 0.40;
0.23 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.23 < 0.45;
0.42 : цель находится в состоянии S 1 и остается в состоянии S 1 , так как 0 < 0.42 < 0.45;
0.63 : цель находится в состоянии S 1 и переходит в состояние S 2 , так как 0.45 < 0.63 < 0.45 + 0.55.

Так как достигнуто состояние S 2 (далее цель переходит из S 2 в состояние S 2 с вероятностью 1), то цель поражена. Для этого в данном эксперименте потребовалось 5 снарядов.

На рис. 33.7 приведена временная диаграмма, которая получается во время описанного процесса моделирования. Диаграмма показывает, как во времени происходит процесс изменения состояний. Такт моделирования для данного случая имеет фиксированную величину. Нам важен сам факт перехода (в какое состояние переходит система) и не важно, когда это происходит.

Процедура уничтожения цели совершена за 5 тактов, то есть марковская цепь этой реализации выглядит следующим образом: S 0 —S 0 —S 1 —S 1 —S 1 —S 2 . Конечно, ответом задачи это число быть не может, так как в разных реализациях получатся разные ответы. А ответ у задачи может быть только один.

Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 (S 0 —S 0 —S 1 —S 1 —S 2 ); 11 (S 0 —S 0 —S 0 —S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 1 —S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 4 (S 1 —S 1 —S 1 —S 1 —S 2 ); 6 (S 0 —S 0 —S 1 —S 1 —S 1 —S 1 —S 2 ); 5 (S 0 —S 0 —S 1 —S 1 —S 1 —S 2 ). Всего уничтожено 8 целей. Среднее число циклов в процедуре стрельбы составило: (5 + 4 + 11 + 5 + 6 + 4 + 6 + 5)/8 = 5.75 или, округляя, 6. Именно столько снарядов, в среднем, рекомендуется иметь в боевом запасе пушки для уничтожения цели при таких вероятностях попаданий.

Теперь следует определить точность. Именно точность может нам показать, насколько следует доверять данному ответу. Для этого проследим, как сходится последовательность случайных (приближенных) ответов к правильному (точному) результату. Напомним, что, согласно центральной предельной теореме (см. лекцию 25 , лекцию 21), сумма случайных величин есть величина неслучайная, поэтому для получения статистически достоверного ответа необходимо следить за средним числом снарядов, получаемых в ряде случайных реализаций.

На первом этапе вычислений средний ответ составил 5 снарядов, на втором этапе средний ответ составил (5 + 4)/2 = 4.5 снаряда, на третьем — (5 + 4 + 11)/3 = 6.7. Далее ряд средних величин, по мере накопления статистики, выглядит следующим образом: 6.3, 6.2, 5.8, 5.9, 5.8. Если изобразить этот ряд в виде графика средней величины выпущенных снарядов, необходимых для поражения цели, в зависимости от номера эксперимента, то обнаружится, что данный ряд сходится к некоторой величине, которая и является ответом (см. рис. 33.8 ).

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

Алгоритм имитации будет иметь следующий вид (см. рис. 33.9).

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

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

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

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

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

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

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

С интенсивностью потока (а переходы — это поток событий) мы уже научились работать в лекции 28 . Зная интенсивность λ 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 , указывающий, в какое именно состояние произойдет переход.

Пример. Моделирование работы станка . Промоделируем работу станка (см. рис. 33.10 ), который может находиться в следующих состояниях: S 0 — станок исправен, свободен (простой); S 1 — станок исправен, занят (обработка); S 2 — станок исправен, замена инструмента (переналадка) λ 02 < λ 21 ; S 3 — станок неисправен, идет ремонт λ 13 < λ 30 .

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

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

В частности, из рис. 33.11 видно, что реализовавшаяся цепь выглядит так: S 0 —S 1 —S 0 —… Переходы произошли в следующие моменты времени: T 0 —T 1 —T 2 —T 3 —… , где T 0 = 0 , T 1 = τ 01 , T 2 = τ 01 + τ 10 .

Задача . Поскольку модель строят для того, чтобы на ней можно было решить задачу, ответ которой до этого был для нас совсем не очевиден (см. лекцию 01), то сформулируем такую задачу к данному примеру. Определить долю времени в течение суток, которую занимает простой станка (посчитать по рисунку) T ср = (T + T + T + T )/N .

Алгоритм имитации будет иметь следующий вид (см. рис. 33.12 ).

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

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

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

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

Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

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

Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение случайных процессов. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.

Нетрудно заметить, что если обозначить состояние и изобразить зависимость, то такая зависимость и будет случайной функцией.

Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.

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

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

Если случайная последовательность обладает Марковским свойством, то она называется цепью Маркова.

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

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

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

2. Имеется вектор начальных вероятностей

описывающий начальное состояние системы.

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1

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

1. Невозвратное множество (рис. 2).

Рис.2.

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

2. Возвратное множество (рис. 3).

Рис. 3.

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

3. Эргодическое множество (рис. 4).

Рис. 4.

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество (рис. 5)

Рис. 5.

При попадании системы в это множество процесс заканчивается.

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

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

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

Структура и классификация систем массового обслуживания

Системы массового обслуживания

Нередко возникает необходимость в решении вероятностных задач, связанных с системами массового обслуживания (СМО), примерами которых могут быть:

Билетные кассы;

Ремонтные мастерские;

Торговые, транспортные, энергетические системы;

Системы связи;

Общность таких систем выявляется в единстве математических методов и моделей, применяемых при исследовании их деятельности.

Рис. 4.1. Основные сферы применения ТМО

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

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

1. Входящий поток требований.

2. Накопитель (очередь).

3. Приборы (каналы обслуживания).

4. Выходящий поток.

Рис. 4.2. Общая схема систем массового обслуживания

Рис. 4.3. Модель работы системы

(стрелками показаны моменты поступления требований в

систему, прямоугольниками – время обслуживания)

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

В зависимости от правил образования очереди различают следующие СМО:

1) системы с отказами , в которых при занятости всех каналов обслуживания заявка покидает систему необслуженной;

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

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

Рассмотрим характеристики входящего потока требований.

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

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

Поток событий называется ординарным , если невозможно одновременное поступление двух или более событий.

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

Интенсивностью потока заявок λ называется среднее число заявок, поступающих из потока за единицу времени.

Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:

Время между соседними заявками распределено по экспоненциальному закону с плотностью вероятности

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

Отношение интенсивности входящего потока к интенсивности потока обслуживания называется загрузкой системы

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

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

Такие процессы бывают двух типов: с дискретным или непрерывным временем.

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

Случайным процессом называется соответствие, при котором каждому значению аргумента (в данном случае – моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае – состояние СМО). Случайной величиной называется величина, которая в результате опыта может принять одно, но неизвестное заранее, какое именно, числовое значение из данного числового множества.

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

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

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

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

СМО делят на два основных типа (класса) : СМО с отказами и href="cmo_length.php">СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной). В СМО с ожиданием заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь на обслуживание.
СМО с ожиданием подразделяются на разные виды в зависимости от того, как организована очередь: с ограниченной или неограниченной длиной очереди, с ограниченным временем ожидания и т.п.
Процесс работы СМО представляет собой случайный процесс.
Под случайным (вероятностным или стохастическим) процессом понимается процесс изменения во времени состояния какой-либо системы в соответствии с вероятностными закономерностями.
Процесс называется процессом с дискретными состояниями, если его возможные состояния S 1 , S 2 , S 3 … можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.
Процесс работы СМО представляет собой случайный процесс c дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.).
Математический анализ работы СМО существенно упрощается, если процесс этой работы - марковский. Случайный процесс называется марковским или случайным процессом без последствия, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в момент t > t 0 счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S 1 , зависит от S 0 , но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t 0 .
Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S - группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t 0 . Вероятность того, что в момент t > t 0 материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t 0 , а не того, когда и в какой последовательности исчезли фигуры с доски до момента t 0 .
В ряде случаев предысторией рассматриваемых процессов можно просто пренебречь и применять для их изучения марковские модели.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой - так называемым графом состоянии. Обычно состояния системы изображаются прямоугольниками (кружками), а возможные переходы из состояния в состояние - стрелками (ориентированными дугами), соединяющими состояния.
Задача 1 . Построить граф состояний следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время.

Решение. Возможные состояния системы: S 0 - оба узла исправны; S 1 - первый узел ремонтируется, второй исправен; S 2 - второй узел ремонтируется, первый исправен; S 3 - оба узла ремонтируются. Граф системы приведен на рис.1.
Рис. 1
Стрелка, направленная, например, из S 0 в S 1 означает переход системы в момент отказа первого узла, из S 1 в S 0 - переход в момент окончанияремонта этого узла.
На графе отсутствуют стрелки из S 0 , в S 3 и из S 1 в S 2 . Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из S 0 в S 3) или одновременного окончания ремонтов двух узлов (переход из S 3 в S 0) можно пренебречь.

Поток событий

Случайный процесс X (t), tÎT называется марковским, если любых t l < t 2 < ... < t n , принадлежащих области Т, условная функция распределения случайной величины X(t n) относительно X(t 1), . . ., X(t n -1) совпадает с условной функцией распределения X(t n) относительно X(t n -1) в том смысле, что для любого x n ÎX справедливо равенство

Рассмотрение определения (3.1.1) при последовательно увеличивающихся n позволяет установить, что для марковских случайных процессов n-мерная функция распределения может быть представлена в виде

Аналогично свойство марковости (3.1.1), (3.1.2) может быть записано и для плотностей вероятности

Таким образом, для марковского процесса функция распреде­ления или плотность вероятности любой мерности n может быть найдена, если известна его одномерная плотность вероятности при t = t 1 и последовательность условных плотностей для моментов t i >t 1 , i = .Эта особенность по существу и определяет практи­ческое удобство аппарата марковских случайных процессов.

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

- цепи Маркова - процессы, у которых как область значе­ний X, так и область определения Т - дискретные множества;

- марковские последовательности - процессы, у которых об­ласть значений X - непрерывное, а область определения Т -дис­кретное множество;

- дискретные марковские процессы - процессы, у которых область значений X - дискретное, а область определения Т - не­прерывное множество;

- непрерывнозначные марковские процессы - процессы, у ко­торых как область значений X, так и область определения Т - непрерывные множества.

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

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

ЦЕПИ МАРКОВА

Пусть случайный процесс X (t) может принимать конечное (L < ) множество значений

{q l , l = } = С. Конкретное зна­чениеq l ; Î С, которое принял процесс X (t) в момент t, определя­ет его состояние при данном значении аргумента. Таким образом,

в рассматриваемом случае процесс X (t) имеет конечное мно­жество возможных состояний.

Естественно, что с течением времени процесс X (t) будет слу­чайным образом изменять свое состояние. Допустим, что такое изменение возможно не при любом t, а лишь в некоторые дискрет­ные моменты времени t 0 X (t) скачком изменяет свое состояние. Иначе говоря, в моменты времени t t имеют место переходы X(t 0) ®X(t 1) ® ..., причем X(t)Î C, i = 0,1,2,…

Два указанных признака определяют последовательность ди­скретных случайных величин X i - X (t i), i = 0.1, ... (дискретную случайную последовательность в терминах, параграфа 1.1), у ко­торой область значений представляет собой дискретное конечное множество С ={q l , l = ], а область определения - дискрет­ное бесконечное множество t i , i = 0,1, 2,...

Если для определенной таким образом дискретной случайной последовательности справедливо основное свойство (3.1.1) про­цессов Маркова, приобретающее в данном случае вид

то такая последовательность называется простой цепью Маркова.

Отметим, что из выражения (3.2.1) непосредственно вытекает

такое же равенство и для условных вероятностей нахождения

простой цепи Маркова в некотором состоянии

Р{х 1 /х 0 ,х 1 , ...,x i -1 } = Ρ{x i /x i -1 }, i = 1,2,....

Введенное определение допускает некоторое обобщение. По­ложим, что значение х i Î С рассматриваемого процесса X (t) за­висит не от одного, а от m(l£ m < i ) непосредственно предшест­вующих ему значений. Тогда, очевидно, что

Процесс, определяемый соотношением (3.2.2), называется сложной цепью Маркова порядка т. Соотношение (3.2.1) выте­кает из (3.2.2) как частный случай. В свою очередь, сложная цепь Маркова порядка т может быть сведена к простой цепи Маркова для m-мерного вектора. Для того чтобы показать это, положим, что состояние процесса в момент i i описывается с помощью m-мерного вектора.

(3.2.3)

На предыдущем шаге аналогичный вектор запишется как

Сравнение (3.2.3) и (3.2.4) показывает, что «средние» компо­ненты этих векторов (кроме X l в (3.2.3) и Х l - m в (3.2.4)) совпадают. Отсюда следует, что условная вероятность попадания про­цесса X (t) в состояние `X i в момент t 1 , если он находился в состоя­нии `X i -1 в момент t i -1 , может быть записана в виде

В (3.2.5) символ обозначает j-ю компоненту вектора `x i ; α (μ, ν) - символ Кронекера: α(μ, ν) = 1 при ν = μ и α(μ, ν) = ϋ при μ ¹ν. Возможность указанных обобщений позволяет ограничить­ся в дальнейшем рассмотрением только простых цепей Маркова.

Как система дискретных случайных величин простая цепь Мар­кова X i , i = 0, 1, 2, ... ,i, ... при любом фиксированном i может быть исчерпывающим образом описана i-мерной совместной вероят­ностью

ρ {θ 0 L , θ ίκ ,... , θ ί m ,} = P{Х 0 =θ L ,X 1 =θ k ,…,X j =θ m }, (3.2.6)

где индексы l , k,..., т принимают все значения от 1 до L неза­висимо друг от друга. Выражение (3.2.6) определяет матрицу с L строками и i+1 столбцом, элементами которой являются вероят­ности совместного пребывания системы случайных величин Χ 0 ,Χ 1 ,...,Χ ί в некотором конкретном состоянии. Данная матрица по аналогии с рядом распределения скалярной дискретной слу­чайной величины может быть названа матрицей распределения системы дискретных случайных величин

Χ 0 ,Χ 1 ,...,Χ ί .

На основании теоремы умножения вероятностей вероятность (3.2.6) может быть представлена в виде

Но согласно основному свойству (3.2.1) цепи Маркова

P{X l = m/X 0 = l ,X 1 = k ,…,X i -1 = r }=P{X i = m /X i -1 = r }

Повторение аналогичных рассуждений для входящей в (3.2.8) вероятности r } позволяет привести это выра­жение к виду

Отсюда окончательно получаем

(3.2.9)

Таким образом, полное вероятностное описание простой цепи Маркова достигается заданием вероятностей начального состояния цепи в момент t 0 , Ρ{Θ 0 l ,} = Р{Х 0 = Θ l }, l= и условных вероятностей

Ρ {X l = Θ k /X i-1 = Θ m }, i = 1 , 2, . .. · k, m =

Отметим, что поскольку возможные состояния Θ l Î`C цепи X (t) фиксированы и известны, для описания ее состояния в лю­бой момент времени достаточно указать номер l этого состояния. Это позволяет ввести для безусловных вероятностей нахождения цепи в l -м состоянии в момент t i (на i -м шаге) упрощенное обоз­начение

Для этих вероятностей, очевидно, имеют место свойства неот­рицательности и нормированности к единице

P l (i )>0,l = , i = 0, 1,2,...; (3.2.11)

При использовании матричных обозначений совокупность без­условных вероятностей записывается в виде матрицы-строки

(3.2.12)

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

Выражение (3.2.13) определяет вероятность прихода цепи в состояние l , в момент t за ν - μ шагов при условии, что в момент t μ цепь находилась в состоянии A . Нетрудно видеть, что для вероятностей перехода также имеют место свойства не­отрицательности и нормированности, поскольку на любом шаге цепь всегда будет находиться в одном из L возможных состояний

(3.2.14)

Упорядоченная совокупность вероятностей перехода для любой пары может быть представлена в виде квадратной мат­рицы

(3.2.15)

Как следует из выражения (3.2.14), все элементы этой матри­цы неотрицательны и сумма элементов каждой строки равна еди­нице. Квадратная матрица, обладающая указанными свойствами, называется стохастической.

Таким образом, вероятностное описание цепи Маркова может быть задано матрицей-строкой (3.2.12) и стохастической матри­цей (3.2.15).

С использованием введенных обозначений решим основную задачу теории цепей Маркова - определим безусловную вероят­ность Ρ l (ί) того, что за i -μ шагов процесс придет в некото­рое состояние l , l = . Очевидно, что в момент t m процесс может находиться в любом из L возможных состояний с вероятностью P k (m), k = . Вероятность же перехода из k-гo в l -е состояние задается вероятностью перехода p k l (m,i) . Отсюда на основании теоремы о полной вероятности получаем

; (3.2.16)

или в матричной форме

P(i )=P(m)P(m,i ); (3.2.17)

Рассмотрим в соотношении (3.2.16) вероятность перехода π kl (m,i ). Очевидно, что переход цепи из состояния k в момент t m в состояние l в момент t i за несколько шагов может осущест­вляться различными путями (через различные промежуточные со­стояния). Введем в рассмотрение промежуточный момент времени t m , t m Β этот момент процесс может находиться в любом из L возможных состояний, причем вероятность его попадания в r-е состояние в момент t m при условии, что в момент t m он был в состоянии k, равна π kr (μ,m). В свою очередь, из состояния r в состояние l процесс переходит с вероятностью π rl (m,i ). Отсю­да с использованием теоремы о полной вероятности получаем уравнение Маркова для вероятностей перехода

матричная форма которого имеет вид

П(m, ί) = П(μ, m) П(m,I) ; 0£m < m < I; (3.2.19)

Уравнения (3.2.18), (3.2.19) определяют характерное для це­пей Маркова свойство вероятностей перехода, хотя справедливос­ти (3.2.18) еще недостаточно, чтобы соответствующая цепь была марковской.

Расписывая последовательно формулу (3.2.19), получаем

П(μ, i ) = П (μ, i - 1) П (i - 1, ί) = П (μ, μ + 1) ... П (ί - 1, i ), (3.2.20)

где p(ν, μ), μ -n= 1- одношаговая вероятность перехода. Полагая теперь в выражении (3.2.17) μ =0, получаем

(3.2.21)

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

Очевидно, что свойства цепи Маркова в значительной мере определяются свойствами вероятностей перехода. С этой точки зрения, в частности, среди простых цепей Маркова выделяют од­нородные, для которых вероятности перехода зависят только от разности аргументов

p kl (m,i ) =p kl (i-m) ,i>m>0; (3.2.22)

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

Поскольку для однородной цепи вероятность перехода опре­деляется лишь разностью аргументов и не зависит от номера ша­га, очевидно, что для произвольных пар (μ,m), (j ,i ), удовлетво­ряющих условиям т - μ = 1, ί- j = 1, m¹i, справедливо

p kl (m-m) =p kl (i-j)= p kl (1) =p kl ;

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

(3.2.23)

Кроме того, очевидно, что

(3.4.7)

поскольку первый сомножитель под интегралом не зависит от пе­ременной интегрирования, а интеграл от второго равен единице. Вычитание уравнения (3.4.7) из (3.4,6) дает

Предположим, что плотность вероятности перехода рассматри­ваемого процесса может быть разложена в ряд Тейлора. Тогда выражение в квадратных скобках под интегралом в уравнении (3.4.8) может быть представлено в виде

Подставив выражение (3.4.9) в (3.4.8), разделив обе части полученного выражения на ∆t и перейдя к пределу при Δt → 0, получим

Уравнение (3.4.10) определяет широкий класс непрерывных марковских процессов, причем нетрудно видеть, что совокупность коэффициентов А ν (x 0 ,t 0) определяет физические свойства каждо­го из них. Так, коэффициент A 1 (x 0 , t 0) может трактоваться как среднее значение локальной (в точке x (t 0)) скорости изменения процесса, коэффициент A 2 (x 0 , t 0) - как локальная скорость изме­нения дисперсии его приращения и т. д. Однако марковские про­цессы такого общего вида сравнительно редко рассматриваются в приложениях. Наибольшее практическое значение имеет под­множество марковских процессов, удовлетворяющее условию

A ν (x 0 , t 0)¹0; n=1,2, A ν (x 0 , t 0)=0, n³3; (3.4.12)

При исследовании марковских процессов первоначально было установлено, что уравнению (3.4.10) при условии (3.4.12) удовле­творяют законы движения (диффузии) броуновских частиц, вслед­ствие чего соответствующие марковские процессы назвали диф­фузионными. Исходя из этого, коэффициент A 1 (x 0 , t 0)=a (x 0 , t 0) назвали коэффициентом сноса, о A 2 (x 0 , t 0)=b(x 0 , t 0) -- коэффици­ентом диффузии. В рамках (3.4.12) уравнение (3.4.10) приобре­тает окончательный вид

Это уравнение, в котором переменными являются х 0 и t 0 , носит название первого (обратного) уравнения Колмогорова.

Аналогичным образом может быть получено и второе урав­нение

Это уравнение, в честь впервые исследовавших его ученых, называется уравнением Фоккера, - Планка - Колмогорова или прямым уравнением Колмогорова (поскольку в нем фигурирует производ­ная по конечному моменту времени t>t 0).

Таким образом; показано, что плотности вероятности перехода диффузионных марковских процессов удовлетворяют уравнениям (3.4.13), (3.4.14), которые и являются основным инструментом их исследования. При этом- свойства конкретного процесса опреде­ляются «коэффициентами» a(x,tί) и b(x,t) которые, согласно уравнения (3.4.11), равны

Из выражений (3.4.15), (3.4.16) следует, что эти «коэффици­енты» имеют смысл условных математических ожиданий, опре­деляющих характер изменений реализаций процесса за бесконеч­но малый промежуток времени Δt. Допускаются весьма быстрые изменения процесса X (t) , но в противоположных направлениях, в результате чего среднее приращение процесса за малое время Δt конечно и имеет порядок .

КАТЕГОРИИ

Боль Анатомия Грудь Мастодиния Лечение

ПОПУЛЯРНЫЕ СТАТЬИ

Воздействие ударной нагрузки Уравнения удара материальной системы Пульс - здоровье, продолжительность жизни, старение и бессмертие Метод определения длительности удара Что бывает из за насвая. Вред насвая. Последствия и вред от употребления насвая Прикусил язык: чем лечить? Астроцитома — наиболее распространенная опухоль головного мозга

© 2024 «api-clinic.ru» — Центр естественной медицины

Контакты Карта сайта