Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.
Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений особое внимание Марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.
Несмотря на указанную выше простоту и наглядность, практическое применение теории Марковских цепей требует знания некоторых терминов и основных положений, на которых следует остановиться перед изложением примеров.
Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).
Случайной функцией называется функция, значение которой при любом значении аргумента является случайной величиной (СВ). По- иному, СФ можно назвать функцию, которая при каждом испытании принимает какой-либо заранее неизвестный вид.
Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.
Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение случайных процессов. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.
Нетрудно заметить, что если обозначить состояние и изобразить зависимость, то такая зависимость и будет случайной функцией.
Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.
Кроме указанных выше примеров классификации случайных процессов существует еще одно важное свойство. Это свойство описывает вероятностную связь между состояниями случайных процессов. Так, например, если в случайном процессе вероятность перехода системы в каждое последующее состояние зависит только от предыдущего состояния, то такой процесс называется процессом без последействия.
Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.
Если случайная последовательность обладает Марковским свойством, то она называется цепью Маркова.
С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется Марковским процессом с непрерывным временем.
Марковский случайный процесс называется однородным, если переходные вероятности остаются постоянными в ходе процесса.
Цепь Маркова считается заданной, если заданы два условия.
1. Имеется совокупность переходных вероятностей в виде матрицы:
2. Имеется вектор начальных вероятностей
описывающий начальное состояние системы.
Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).
Рис. 1
Множество состояний системы Марковской цепи, определенным образом классифицируется с учетом дальнейшего поведения системы.
1. Невозвратное множество (рис. 2).
Рис.2.
В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.
2. Возвратное множество (рис. 3).
Рис. 3.
В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.
3. Эргодическое множество (рис. 4).
Рис. 4.
В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.
4. Поглощающее множество (рис. 5)
Рис. 5.
При попадании системы в это множество процесс заканчивается.
В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.
Основным признаком дискретной Марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.
Кроме того, с учетом наличия и отсутствия тех или иных, упомянутых выше, множеств состояний Марковские цепи могут быть поглощающими, если имеется хотя бы одно поглощающее состояние, или эргодическими, если переходные вероятности образуют эргодическое множество. В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают.
Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:
Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позицийполной определенности в настоящем и будущем.
Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.
Т.е. здесь как, например, в теории игр задачи рассматриваются в условиях неопределенности .
Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».
Понятие случайного процесса
Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.
Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системеS протекаетслучайный процесс , если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.
Примеры: 1. СистемаS – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.
2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.
Марковский случайный процесс
Случайный процесс, протекающий в системе, называется Марковским , если для любого момента времениt 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный моментt 0 и не зависят от того, когда и как система пришла в это состояние.
Пусть в настоящий момент t 0 система находится в определенном состоянииS 0 . Мы знаем характеристики состояния системы в настоящеми все, что было приt <t 0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет приt >t 0 ? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое времясистемаS окажется в состоянииS 1 или останется в состоянииS 0 и т.д.
Пример . СистемаS – группа самолетов, участвующих в воздушном бою. Пустьx – количество «красных» самолетов,y – количество «синих» самолетов. К моменту времениt 0 количество сохранившихся (не сбитых) самолетов соответственно –x 0 ,y 0 . Нас интересует вероятность того, что в момент временичисленный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времениt 0 , а не от того, когда и в какой последовательности погибали сбитые до моментаt 0 самолеты.
На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием «предистории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели (в теории массового обслуживания рассматриваются и не Марковские системы массового обслуживания, но математический аппарат, их описывающий, гораздо сложнее).
В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.
Процесс называется процессом с дискретным состоянием , если его возможные состоянияS 1 ,S 2 , … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.
Процесс называется процессом с непрерывным временем , если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент.
Пример . Технологическая система (участок)S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:
S 0 - оба станка исправны;
S 1 - первый станок ремонтируется, второй исправен;
S 2 - второй станок ремонтируется, первый исправен;
S 3 - оба станка ремонтируются.
Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом состояний . Вершины графа – состояния системы. Дуги графа – возможные переходы из состояния в
Рис.1. Граф состояний системы
состояние. Для нашего примера граф состояний приведен на рис.1.
Примечание. Переход из состояния S 0 вS 3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.
Лекция 9
Марковские процессыЛекция 9
Марковские процессы
1
Марковские процессы
Марковские процессыСлучайный процесс, протекающий в системе, называется
марковским, если он обладает отсутствием последствия. Т.е.
если рассматривать текущее состояние процесса (t 0) - как
настоящее, совокупность возможных состояний { (s),s t} - как
прошлое, совокупность возможных состояний { (u),u t} - как
будущее, то для марковского процесса при фиксированном
настоящем будущее не зависит от прошлого, а определяется
лишь настоящим и не зависит от того, когда и как система
пришла в это состояние.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
2
Марковские процессы
Марковские процессыМарковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин
и создавшего теорию, которую можно назвать "динамикой
вероятностей". В дальнейшем основы этой теории явились
исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
3
Марков Андрей Андреевич Марков Андрей Андреевич Марков Андрей Андреевич
Марковские процессыМарков Андрей Андреевич
1856-1922
Русский математик.
Написал около 70 работ по
теории
чисел,
теории
приближения функций, теории
вероятностей. Существенно расширил сферу применения закона
больших чисел и центральной
предельной теоремы. Является
основоположником теории случайных процессов.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
4
Марковские процессы
Марковские процессыНа практике марковские процессы в чистом виде обычно
не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь, и при изучении
таких процессов можно применять марковские модели. В
настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
5
Марковские процессы
Марковские процессыБиология: процессы рождения и гибели - популяции, мутации,
эпидемии.
Физика:
радиоактивные
распады,
теория
счетчиков
элементарных частиц, процессы диффузии.
Химия:
теория
следов
в
ядерных
фотоэмульсиях,
вероятностные модели химической кинетики.
Images.jpg
Астрономия: теория флуктуационной
яркости млечного пути.
Теория массового обслуживания: телефонные станции,
ремонтные мастерские, билетные кассы, справочные бюро,
станочные и другие технологические системы, системы управления
гибких производственных систем, обработка информации серверами.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
6
Марковские процессы
Марковские процессыПусть в настоящий момент t0 система находится в
определенном состоянии S0. Мы знаем характеристики
состояния системы в настоящем и все, что было при t < t0
(предысторию процесса). Можем ли мы предсказать будущее,
т.е. что будет при t > t0?
В точности – нет, но какие-то вероятностные характеристики
процесса в будущем найти можно. Например, вероятность того,
что через некоторое время
система S окажется в состоянии
S1 или останется в состоянии S0 и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
7
Марковские процессы. Пример.
Марковские процессыМарковские процессы. Пример.
Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество
«красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов
соответственно – x0, y0.
Нас интересует вероятность того, что в момент времени
t 0 численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система
в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
8
Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Марковский процесс с конечным или счетным числом
состояний и моментов времени называется дискретной
цепью Маркова. Переходы из состояния в состояние возможны только в целочисленные моменты времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
9
10. Дискретные цепи Маркова. Пример
Марковские процессыПредположим,
что
речь
идет
о
последовательных бросаниях монеты при
игре "в орлянку"; монета бросается в
условные моменты времени t =0, 1, ... и на
каждом шаге игрок может выиграть ±1 с
одинаковой
вероятностью
1/2,
таким
образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... .
При условии, что ξ(t) = k, на следующем шаге выигрыш будет
уже равен ξ(t+1) = k ± 1, принимая значения j = k ± 1 c одинаковой вероятностью 1/2. Можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
10
11. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Обобщая этот пример, можно представить себе систему со
счетным числом возможных состояний, которая с течением
дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов
ξ(0) -> ξ(1) -> ... -> ξ(t) -> ξ(t+1) ->...-> ... .
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
11
12. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом
состояний. Вершины графа – состояния системы. Дуги графа
– возможные переходы из состояния в состояние.
Игра «в орлянку».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
12
13. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Обозначим все возможные состояния целыми i = 0, ±1, ...
Предположим, что при известном состоянии ξ(t) =i на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
P{ (t 1) j (t) i}
независимо от ее поведения в прошлом, точнее, независимо
от цепочки переходов до момента t:
P{ (t 1) j (t) i; (t 1) it 1;...; (0) i0 }
P{ (t 1) j (t) i}
Это свойство называется марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
13
14. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Число
pij P{ (t 1) j (t) i}
называется вероятностью
перехода системы из состояния i в состояние j за один шаг в
момент времени t 1.
Если переходная вероятность не зависит от t , то цепь
Маркова называется однородной.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
14
15. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Матрица P , элементами которой являются вероятности
перехода pij , называется переходной матрицей:
p11 ... p1n
P p 21 ... p 2n
p
n1 ... p nn
Она является стохастической, т.е.
pij 1 ;
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p ij 0 .
15
16. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
Матрица переходов для игры «в орлянку»
...
k 2
k 2
0
k 1
1/ 2
k
0
k 1
k
k 1
k 2
0
1/ 2
0
0
1/ 2
0
1/ 2
0
1/ 2
0
0
0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
...
k 1 k 2
0
0
0
1/ 2
0
1/ 2
...
0
0
1/ 2
0
16
17. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
Садовник в результате химического анализа почвы оценивает
ее состояние одним из трех чисел - хорошее (1), удовлетворительное (2) или плохое (3). В результате наблюдений на протяжении многих лет садовник заметил,
что продуктивность почвы в текущем
году зависит только от ее состояния в
предыдущем году. Поэтому вероятности
перехода почвы из одного состояния в
другое можно представить следующей
цепью Маркова с матрицей P1:
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
17
18. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
Однако в результате агротехнических мероприятий садовник может изменить переходные вероятности в матрице P1.
Тогда матрица P1 заменится
на матрицу P2:
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
18
19. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Рассмотрим, как изменяются состояния процесса с течением времени. Будем рассматривать процесс в последовательные моменты времени, начиная с момента 0. Зададим начальное распределение вероятностей p(0) { p1 (0),..., pm (0)} , где m число состояний процесса, pi (0) - вероятность нахождения
процесса в состоянии i в начальный момент времени. Вероятность pi (n) называется безусловной вероятностью состояния
i в момент времени n 1.
Компоненты вектора p (n) показывают, какие из возможных состояний цепи в момент времени n являются наиболее
вероятными.
m
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
pk (n) 1
k 1
19
20. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Знание последовательности { p (n)} при n 1,... позволяет составить представление о поведении системы во времени.
В системе с 3-мя состояниями
p11 p12 p13
P p21
p
31
p22
p32
p23
p33
p2 (1) p1 (0) p12 p2 (0) p22 p3 (0) p32
p2 (n 1) p1 (n) p12 p2 (n) p22 p3 (n) p32
В общем случае:
p j (1) pk (0) pkj
p j (n 1) pk (n) pkj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
k
p(n 1) p(n) P
20
21. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
Матрица
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
Шаг
{ p (n)}
n
0
1, 0, 0
n
1
0.2 , 0.5 , 0.3
n
2
0.04 , 0.35 , 0.61
n
3
0.008 , 0.195 , 0.797
n
4
0.0016 , 0.1015 , 0.8969
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
21
22. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
n
Матрица перехода за n шагов P(n) P .
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
p(2) p(0) P
2
p (2)
P(2) P 2
1, 0, 0
0.0016
0.
0.
0.0016
0.
0.
0.1015
0.0625
0.
0.1015
0.0625
0.
0.8969
0.9375
1.
0.8969
0.9375
1.
0.04 , 0.35 , 0.61
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
22
23. Дискретные цепи Маркова
Марковские процессыДискретные цепи Маркова
Как ведут себя марковские цепи при n ?
Для однородной марковской цепи при определенных условиях выполняется следующее свойство: p (n) при n .
Вероятности 0 не зависят от начального распределения
p(0) , а определяются только матрицей P . В этом случае называется стационарным распределением, а сама цепь – эргодической. Свойство эргодичности означает, что по мере увеличения n
вероятность состояний практически перестаёт изменяться, а система переходит в стабильный режим функционирования.
i
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
23
24. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
0.20 0.50 0.30
0.00 0.50 0.50
0.00 0.00 1.00
0 0 1
P() 0 0 1
0 0 1
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
p () (0,0,1)
24
25. Дискретные цепи Маркова. Пример
Марковские процессыДискретные цепи Маркова. Пример
0.30 0.60 0.10
0.10 0.60 0.30
0.05 0.40 0.55
0.1017 0.5254 0.3729
P() 0.1017 0.5254 0.3729
0.1017 0.5254 0.3729
p () (0.1017,0.5254,0.3729)
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
25
26. Марковские процессы с непрерывным временем
Марковские процессыПроцесс называется процессом с непрерывным временем, если
моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти
в любой момент.
Пример. Технологическая система S состоит из двух устройств,
каждое из которых в случайный момент времени может выйти из
строя, после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
Возможны следующие состояния системы:
S0 - оба устройства исправны;
S1 - первое устройство ремонтируется, второе исправно;
S2 - второе устройство ремонтируется, первое исправно;
S3 - оба устройства ремонтируются.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
26
27. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
Переходы системы S из состояния в состояние происходят
практически мгновенно, в случайные моменты выхода из строя
того или иного устройства или
окончания ремонта.
Вероятностью одновременного
выхода из строя обоих устройств
можно пренебречь.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
27
28. Потоки событий
Марковские процессыПотоки событий
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
– это среднее число событий,
Интенсивность потока событий
приходящееся на единицу времени.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
28
29. Потоки событий
Марковские процессыПотоки событий
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
В частности, интенсивность
стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
29
30. Потоки событий
Марковские процессыПотоки событий
Поток событий называется потоком без последствий, если для
любых двух непересекающихся участков времени и число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты
времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным, если вероятность появления на элементарном участке t двух и более событий пренебрежимо мала по сравнению с вероятностью появления одного
события, т.е. события в нем появляются поодиночке, а не группами по нескольку сразу
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
30
31. Потоки событий
Марковские процессыПотоки событий
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: 1) стационарен, 2) ординарен, 3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую
роль, как и закон нормального распределения среди других
законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных
потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
31
32. Потоки событий
Марковские процессыПотоки событий
Для простейшего потока с интенсивностью
интервал
времени T между соседними событиями имеет показательное
распределение с плотностью
p(x) e x , x 0 .
Для случайной величины T, имеющей показательное распределение, математическое ожидание есть величина, обратная параметру.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
32
33. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
Рассматривая процессы с дискретными состояниями и непрерывным временем, можно считать, что все переходы системы S из состояния в состояние происходят под действием
простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.).
Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в
системе, будет марковским.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
33
34. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
Пусть на систему, находящуюся в состоянии, действует
простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния
в состояние.
- интенсивность потока событий, переводящий систему
из состояния
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
в
.
34
35. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
Пусть рассматриваемая система S имеет
возможных состояний
. Вероятность p ij (t) является вероятностью перехода из состояния i в состояние j за время t.
Вероятность i - го состояния
- это вероятность того,
что в момент времени t система будет находиться в состоянии
. Очевидно, что для любого момента времени сумма
всех вероятностей состояний равна единице:
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
35
36. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
Для нахождения всех вероятностей состояний
как
функций времени составляются и решаются дифференциальные уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний.
Для переходных вероятностей:
p ij (t) p ik (t) kj
k
Для безусловных вероятностей:
p j (t) p k (t) kj
k
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
36
37. Колмогоров Андрей Николаевич
Марковские процессыКолмогоров Андрей Николаевич
1903-1987
Великий русский
математик.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
37
38. Марковские процессы с непрерывным временем
Марковские процессыМарковские процессы с непрерывным временем
- интенсивности потока отказов;
- интенсивности потока восстановлений.
Пусть система находится в состоянии
S0. В состояние S1 ее переводит поток
отказов первого устройства. Его интенсивность равна
где
- среднее время безотказной работы устройства.
Из состояния S1 в S0 систему переводит поток восстановлений
первого устройства. Его интенсивность равна
где
- среднее время ремонта первого станка.
Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
38
39. Системы массового обслуживания
Марковские процессыПримеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские,
билетные
кассы,
справочные
бюро,
станочные и другие технологические системы,
системы
управления
гибких
производственных систем,
обработка информации серверами и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
39
40. Системы массового обслуживания
Марковские процессыСистемы массового обслуживания
СМО состоит из какого – то количества обслуживающих
единиц, которые называются каналами обслуживания (это
станки, роботы, линии связи, кассиры и т.д.). Всякая СМО
предназначена для обслуживания потока заявок (требований), поступающих в случайные моменты времени.
Обслуживание заявки продолжается случайное время, после чего канал освобождается и готов к приему следующей
заявки.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
40
41. Системы массового обслуживания
Марковские процессыСистемы массового обслуживания
Процесс работы СМО – случайный процесс с дискретными
состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких - то событий
(прихода новой заявки, окончания обслуживания, момента,
когда заявка, которой надоело ждать, покидает очередь).
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
41
42. Системы массового обслуживания
Марковские процессыСистемы массового обслуживания
Классификация систем массового обслуживания
1. СМО с отказами;
2. СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не
обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости
от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени
ожидания, «дисциплины обслуживания».
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
42
43. Системы массового обслуживания
Марковские процессыСистемы массового обслуживания
Предмет теории массового обслуживания – построение
математических моделей, связывающих заданные условия
работы СМО (число каналов, их производительность, правила
работы, характер потока заявок) с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком
заявок. Ими могут быть: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
43
44.
СПАСИБОЗА ВНИМАНИЕ!!!
44
45. Построить граф переходов
Марковские процессыПостроить граф переходов
0.30
0.70
0.0
0.10
0.60
0.30
0.50
0.50
0.0
ХНУРЕ, каф. ПМ, лектор Кириченко Л.О.
«Теория вероятностей, математическая
статистика и случайные процессы»
Многие операции, которые приходится анализировать при выборе оптимального решения, развиваются как случайные процессы, зависящие от ряда случайных факторов.
Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применен математический аппарат, разработанный в теории вероятностей для так называемых марковских случайных процессов.
Поясним понятие марковского случайного процесса.
Пусть имеется некоторая система S, состояние которой меняется с течением времени (под системой S может пониматься все что угодно: промышленное предприятие, техническое устройство, ремонтная мастерская и т. д.). Если состояние системы S меняется во времени случайным, заранее непредсказуемым образом, говорят, что в системе S протекает случайный процесс.
Примеры случайных процессов:
флуктуации цен на фондовом рынке;
обслуживание клиентов в парикмахерской или ремонтной мастерской;
выполнение плана снабжения группы предприятий и т. д.
Конкретное протекание каждого из этих процессов зависит от ряда случайных, заранее непредсказуемых факторов, таких как:
поступление на фондовый рынок непредсказуемых известий о политических изменениях;
случайный характер потока заявок (требований), поступающих со стороны клиентов;
случайные перебои в выполнении плана снабжения и т. д.
ОПРЕДЕЛЕНИЕ. Случайный процесс, протекающий в системе, называется марковским (или процессом без последствия ), если он обладает следующим свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0) зависит только от ее состояния в настоящем (при t = t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т. е. как развивался процесс в прошлом).
Другими словами, в марковском случайном процессе будущее развитие его зависит только от настоящего состояния и не зависит от “предыстории” процесса.
Рассмотрим пример. Пусть система S представляет собой фондовый рынок, который уже существует какое-то время. Нас интересует, как будет работать система в будущем. Ясно, по крайней мере в первом приближении, что характеристики работы в будущем (вероятности падения цен конкретных акций через неделю) зависят от состояния системы в настоящий момент (здесь могут вмешаться самые различные факторы типа решений правительства или результатов выборов) и не зависят от того, когда и как система достигла своего настоящего состояния (не зависят от характера движения цен на эти акции в прошлом).
На практике часто встречаются случайные процессы, которые, с той или другой степенью приближения можно считать марковскими.
Теория марковских случайных процессов имеет широкий спектр различных приложений. Нас будет интересовать главным образом применение теории марковских случайных процессов к построению математических моделей операций, ход и исход которых существенно зависит от случайных факторов.
Марковские случайные процессы подразделяются на классы в зависимости от того, как и в какие моменты времени система S" может менять свои состояния.
ОПРЕДЕЛЕНИЕ. Случайный процесс называется процессом с дискретными состояниями, если возможные состояния системы s x , s 2 , s v ... можно перечислить (пронумеровать) одно за другим, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.
Например, разработку проекта S осуществляют совместно два отдела, каждый из которых может совершить ошибку. Возможны следующие состояния системы:
5, - оба отдела работают нормально;
s 2 - первый отдел совершил ошибку, второй работает нормально;
s 3 - второй отдел совершил ошибку, первый работает нормально;
s 4 - оба отдела совершили ошибку.
Процесс, протекающий в системе, состоит в том, что она случайным образом в какие-то моменты времени переходит («перескакивает») из состояния в состояние. Всего у системы четыре возможных состояния. Перед нами - процесс с дискретными состояниями.
Кроме процессов с дискретными состояниями существуют случайные процессы с непрерывными состояниями : для этих процессов характерен постепенный, плавный переход из состояния в состояние. Например, процесс изменения напряжения в осветительной сети представляет собой случайный процесс с непрерывными состояниями.
Мы будем рассматривать только случайные процессы с дискретными состояниями.
При анализе случайных процессов с дискретными состояниями очень удобно пользоваться геометрической схемой - так называемым графом состояний. Граф состояний геометрически изображает возможные состояния системы и ее возможные переходы из состояния в состояние.
Пусть имеется система S с дискретными состояниями:
Каждое состояние будем изображать прямоугольником, а возможные переходы (“перескоки”) из состояния в состояние - стрелками, соединяющими эти прямоугольники. Пример графа состояния приведен на рис. 4.1.
Заметим, что стрелками отмечаются только непосредственные переходы из состояния в состояние; если система может перейти из состояния s 2 в 5 3 только через s y то стрелками отмечаются только переходы s 2 -> и л, 1 -> 5 3 , но не s 2 -» s y Рассмотрим несколько примеров:
1. Система S - фирма, которая может находиться в одном из пяти возможных состояний: s ] - работает с прибылью;
s 2 - утратила перспективу развития и перестала приносить прибыль;
5 3 - стала объектом для потенциального поглощения;
s 4 - находится под внешним управлением;
s 5 - имущество ликвидируемой фирмы продается на торгах.
Граф состояний фирмы показан на рис. 4.2.
Рис. 4.2
- 2. Система S - банк, имеющий два отделения. Возможны следующие состояния системы:
- 5, - оба отделения работают с прибылью;
s 2 - первое отделение работает без прибыли, второе работает с прибылью;
5 3 - второе отделение работает без прибыли, первое работает с прибылью;
s 4 - оба отделения работают без прибыли.
Предполагается, что улучшение состояния не происходит.
Граф состояний представлен на рис. 4.3. Отметим, что на графе не показан возможный переход из состояния s ] непосредственно в s 4 , который осуществится, если банк сразу будет работать в убыток. Возможностью такого события можно пренебречь, что и подтверждает практика.
Рис. 4.3
3. Система S - инвестиционная компания, состоящая из двух трейдеров (отделов): I и II; каждый из них может в какой-то момент времени начать работать в убыток. Если это происходит, то руководство компании немедленно принимает меры для восстановления прибыльной работы отдела.
Возможные состояния системы: s - деятельность обоих отделов прибыльна; s 2 - первый отдел восстанавливается, второй работает с прибылью;
s 3 - первый отдел работает с прибылью, второй восстанавливается;
s 4 - оба отдела восстанавливаются.
Граф состояний системы показан на рис. 4.4.
4. В условиях предыдущего примера деятельность каждого трейдера перед тем, как он начнет восстанавливать прибыльную работу отдела, подвергается изучению руководством фирмы в целях принятия мер по ее улучшению.
Состояния системы будем для удобства нумеровать не одним, а двумя индексами; первый будет означать состояния первого трейдера (1 - работает с прибылью, 2 - его деятельность изучается руководством, 3 - восстанавливает прибыльную деятельность отдела); второй - те же состояния для второго трейдера. Например, s 23 будет означать: деятельность первого трейдера изучается, второй - восстанавливает прибыльную работу.
Возможные состояния системы S:
s u - деятельность обоих трейдеров приносит прибыль;
s l2 - первый трейдер работает с прибылью, деятельность второго изучается руководством компании;
5 13 - первый трейдер работает с прибылью, второй восстанавливает прибыльную деятельность отдела;
s 2l - деятельность первого трейдера изучается руководством, второй работает с прибылью;
s 22 - деятельность обоих трейдеров изучается руководством;
- 5 23 - работа первого трейдера изучается, второй трейдер восстанавливает прибыльную деятельность отдела;
- 5 31 - первый трейдер восстанавливает прибыльную деятельность отдела, второй работает с прибылью;
- 5 32 - прибыльная деятельность отдела восстанавливается первым трейдером, работа второго трейдера изучается;
- 5 33 - оба трейдера восстанавливают прибыльную работу своего отдела.
Всего девять состояний. Граф состояний показан на рис. 4.5.
Эволюция к-рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот момент фиксировано (короче: "будущее" н "прошлое" процесса не зависят друг от друга при известном "настоящем").
Определяющее М. п. свойство принято наз. марковским; впервые оно было сформулировано А. А. Марковым . Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как М. п., попытку, получившую обоснование после исследований Н. Винера (N. Wiener, 1923). Основы общей теории М. п. с непрерывным временем были заложены А. Н. Колмогоровым .
Марковское свойство. Имеются существенно отличающиеся друг от друга определения М. п. Одним из наиболее распространенных является следующее. Пусть на вероятностном пространстве задан случайный процесс со значениями из измеримого пространства где Т - подмножество действительной оси Пусть N t (соответственно N t ).есть s-алгебра в порожденная величинами X(s).при где Другими словами, N t (соответственно N t ) - это совокупность событий, связанных с эволюцией процесса до момента t(начиная с t). Процесс X(t).наз. марковским процессом, если (почти наверное) для всех выполняется марковское свойство:
или, что то же самое, если для любых
М. п., для к-рого Тсодержится в множестве натуральных чисел, наз. Маркова цепью (впрочем, последний термин чаще всего ассоциируется со случаем не более чем счетного Е). Если Тявляется интервалом в а Ене более чем счетно, М. п. наз. цепью Маркова с непрерывным временем. Примеры М. п. с непрерывным временем доставляются диффузионными процессами и процессами с независимыми приращениями, в том числе пуассоновским и винеровским.
В дальнейшем для определенности речь будет идти только о случае Формулы (1) и (2) дают ясную интерпретацию принципа независимости "прошлого" и "будущего" при известном "настоящем", но основанное на них определение М. п. оказалось недостаточно гибким в тех многочисленных ситуациях, когда приходится рассматривать не одно, а набор условий типа (1) или (2), отвечающих различным, хотя и согласованным определенным образом, мерам Такого рода соображения привели к принятию следующего определения (см. , ).
Пусть заданы:
а) измеримое пространство где s-алгебра содержит все одноточечные множества в Е;
б) измеримое пространство снабженное семейством s-алгебр таких, что если
в) функция ("траектория") x t =x t (w), определяющая при любых измеримое отображение
г) для каждых и вероятностная мера на s-алгебре такая, что функция измерима относительно если и
Набор наз. (необрывающимся) марковским процессом, заданным в если -почти наверное
каковы бы ни были Здесь - пространство элементарных событий, - фазовое пространство или пространство состояний, Р(s, x, t, В ) - переходная функция или вероятность перехода процесса X(t). Если Енаделено топологией, а - совокупность борелевских множеств в Е, то принято говорить, что М. п. задан в Е. Обычно в определение М. п. включают требование, чтобы и тогда истолковывается как вероятность при условии, что x s =x.
Возникает вопрос: всякую ли марковскую переходную функцию Р(s, x ; t, В ), заданную в измеримом пространстве можно рассматривать как переходную функцию нек-рого М. п. Ответ положителен, если, напр., Еявляется сепарабельным локально компактным пространством, а - совокупностью борелевских множеств в Е. Более того, пусть Е - полное метрич. пространство и пусть
для любого гдеА - дополнение e-окрестности точки х. Тогда соответствующий М. п. можно считать непрерывным справа и имеющим пределы слева (т. е. таковыми можно выбрать его траектории). Существование же непрерывного М. п. обеспечивается условием при (см. , ). В теории М. п. основное внимание уделяется однородным (по времени) процессам. Соответствующее определение предполагает заданной систему объектов а) - г) с той разницей, что для фигурировавших в ее описании параметров sи u теперь допускается лишь значение 0. Упрощаются и обозначения:
Далее, постулируется однородность пространства W, т. е. требуется, чтобы для любых существовало такое что (w) при Благодаря этому на s-алгебре N, наименьшей из s-алгебр в W, содержащих любое событие вида задаются операторы временного сдвига q t , к-рые сохраняют операции объединения, пересечения и вычитания множеств и для к-рых
Набор наз. (необрывающимся) однородным марковским процессом, заданным в если -почти наверное
для Переходной функцией процесса X(t).считается Р(t, x, В ), причем, если нет специальных оговорок, дополнительно требуют, чтобы Полезно иметь в виду, что при проверке (4) достаточно рассматривать лишь множества вида где и что в (4) всегда F t можно заменить s-алгеброй , равной пересечению пополнений F t по всевозможным мерам Нередко в фиксируют вероятностную меру m ("начальное распределение") и рассматривают марковскую случайную функцию где - мера на заданная равенством
М. п. наз. прогрессивно измеримым, если при каждом t>0 функция индуцирует измеримое отображение в где есть s-алгебра
борелевских подмножеств в . Непрерывные справа М. п. прогрессивно измеримы. Существует способ сводить неоднородный случай к однородному (см. ), и в дальнейшем речь будет идти об однородных М. п.
Строго марковское свойство. Пусть в измеримом пространстве задан М. п.
Функция наз. марковским моментом, если для всех При этом множество относят к семейству F t , если при (чаще всего F t интерпретируют как совокупность событий, связанных с эволюцией X(t).до момента т). Для полагают
Прогрессивно измеримый М. п. Xназ. строго марковским процессом (с. м. п.), если для любого марковского момента т и всех и соотношение
(строго марковское свойство) выполняется -почти наверное на множестве W t . При проверке (5) достаточно рассматривать лишь множества вида где в этом случае С. м. п. является, напр., любой непрерывный справа феллеровский М. п. в топологич. пространстве Е. М. п. наз. феллеровским марковским процессом, если функция
непрерывна всякий раз, когда f непрерывна и ограничена.
В классе с. м. п. выделяются те или иные подклассы. Пусть марковская переходная функция Р(t, x, В ), заданная в метрическом локально компактном пространстве Е, стохастически непрерывна:
для любой окрестности Uкаждой точки Тогда если операторы переводят в себя класс непрерывных и обращающихся в 0 в бесконечности функций, то функции Р(t, х, В ).отвечает стандартный М. п. X, т. е. непрерывный справа с. м. п., для к-рого
и - почти наверное на множестве а - неубывающие с ростом пмарковские моменты.Обрывающийся марковский процесс. Нередко физич. системы целесообразно описывать с помощью необрывающегося М. п., но лишь на временном интервале случайной длины. Кроме того, даже простые преобразования М. п. могут привести к процессу с траекториями, заданными на случайном интервале (см. "Функционал" от марковского процесса). Руководствуясь этими соображениями, вводят понятие обрывающегося М. п.
Пусть - однородный М. п. в фазовом пространстве имеющий переходную функцию и пусть существуют точка и функция такие, что при и в противном случае (если нет специальных оговорок, считают ). Новая траектория x t (w) задается лишь для ) посредством равенства a F t определяется как след в множестве
Набор где наз. обрывающимся марковским процессом (о. м. п.), полученным из с помощью обрыва (или убивания) в момент z. Величина z наз. моментом обрыва, или временем жизни, о. м. п. Фазовым пространством нового процесса служит где есть след s-алгебры в Е. Переходная функция о. м. п.- это сужение на множество Процесс X(t).наз. строго марковским процессом, или стандартным марковским процессом, если соответствующим свойством обладает Необрывающийся М. п. можно рассматривать как о. м. п. с моментом обрыва Неоднородный о. м. п. определяется аналогичным образом. М.
Марковские процессы и дифференциальные уравнения. М. п. типа броуновского движения тесно связаны с дифференциальными уравнениями параболич. типа. Переходная плотность р(s, x, t, у ).диффузионного процесса удовлетворяет при нек-рых дополнительных предположениях обратному и прямому дифференциальным уравнениям Колмогорова:
Функция р(s, x, t, у ).есть функция Грина уравнений (6) - (7), и первые известные способы построения диффузионных процессов были основаны на теоремах существования этой функции для дифференциальных уравнений (6) - (7). Для однородного по времени процесса оператор L(s, x ) = L (x).на гладких функциях совпадает с характеристич. оператором М. п. (см. "Переходных операторов полугруппа" ).
Математич. ожидания различных функционалов от диффузионных процессов служат решениями соответствующих краевых задач для дифференциального уравнения (1). Пусть - математич. ожидание по мере Тогда функция удовлетворяет при s уравнению (6) и условию
Аналогично, функция
удовлетворяет при s уравнению
и условию и 2 ( Т, x ) = 0.
Пусть тt - момент первого достижения границы дD области траекторией процесса Тогда при нек-рых условиях функция
удовлетворяет уравнению
и принимает значения ср на множестве
Решение 1-й краевой задачи для общего линейного параболич. уравнения 2-го порядка
при довольно общих предположениях может быть записано в виде
В случае, когда оператор Lи функции с, f не зависят от s, аналогичное (9) представление возможно и для решения линейного эллиптич. уравнения. Точнее, функция
при нек-рых предположениях есть решение задачи
В случае, когдгг оператор Lвырождается (del b(s, х ) = 0 ).или граница дD недостаточно "хорошая", граничные значения могут и не приниматься функциями (9), (10) в отдельных точках или на целых множествах. Понятие регулярной граничной точки для оператора L имеет вероятностную интерпретацию. В регулярных точках границы граничные значения достигаются функциями (9), (10). Решение задач (8), (11) позволяет изучать свойства соответствующих диффузионных процессов и функционалов от них.
Существуют методы построения М. п., не опирающиеся на построение решений уравнений (6), (7), напр. метод стохастических дифференциальных уравнений, абсолютно непрерывная замена меры и др. Это обстоятельство вместе с формулами (9), (10) позволяет вероятностным путем строить и изучать свойства краевых задач для уравнения (8), а также свойства решении соответствующего эллиптич. уравнения.
Так как решение стохастического дифференциального уравнения нечувствительно к вырождению матрицы b(s, x ), то вероятностные методы применялись для построения решений вырождающихся эллиптических и параболических дифференциальных уравнений. Распространение принципа усреднения Н. М. Крылова и Н. Н. Боголюбова на стохастические дифференциальные уравнения позволило с помощью (9) получить соответствующие результаты для эллиптических и параболических дифференциальных уравнений. Нек-рые трудные задачи исследования свойств решений уравнений такого типа с малым параметром при старшей производной оказалось возможным решить с помощью вероятностных соображений. Вероятностный смысл имеет и решение 2-й краевой задачи для уравнения (6). Постановка краевых задач для неограниченной области тесно связана с возвратностью соответствующего диффузионного процесса.
В случае однородного по времени процесса (Lне зависит от s) положительное решение уравнения с точностью до мультипликативной постоянной совпадает при нек-рых предположениях со стационарной плотностью распределения М. п. Вероятностные соображения оказываются полезными и при рассмотрении краевых задач для нелинейных параболич. уравнений. Р. 3. Хасьминский.
Лит. : Марков А. А., "Изв. физ.-мат. об-ва Казан. ун-та", 1906, т. 15, №4, с. 135-56; В а с h e l i е r L., "Ann. scient. Ecole norm, super.", 1900, v. 17, p. 21-86; Колмогоров А. Н., "Math. Ann.", 1931, Bd 104, S. 415- 458; рус. пер.-"Успехи матем. наук", 1938, в. 5, с. 5-41; Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; Р е 1 1 е r W., "Ann. Math.", 1954, v. 60, p. 417-36; Д ы н к и н Е. Б., Ю ш к е в и ч А. А., "Теория вероятн. и ее примен.", 1956, т. 1, в. 1, с. 149-55; X а н т Дж.-А., Марковские процессы и потенциалы, пер. с англ., М., 1962; Д е л л а ш е р и К., Емкости и случайные процессы, пер. с франц., М., 1975; Д ы н к и н Е. В., Основания теории марковских процессов, М., 1959; его же, Марковские процессы, М., 1963; Г и х м а н И. И., С к о р о х о д А. В., Теория случайных процессов, т. 2, М., 1973; Фрейдлин М. И., в кн.: Итоги науки. Теория вероятностей, математическая статистика. - Теоретическая кибернетика. 1966, М., 1967, с. 7-58; X а с ь м и н с к и й Р. 3., "Теория вероятн. и ее примен.", 1963, т. 8, в . 1, с. 3-25; Вентцель А. Д., Фрейдлин М. И., Флуктуации в динамических системах под действием малых случайных возмущений, М., 1979; Blumenthal R. М., G e t о о r R. К., Markov processes and potential theory, N.Y.- L., 1968; Getоor R. K., Markov processes: Ray processes and right processes, В., 1975; Кузнецов С. Е., "Теория вероятн. и ее примен.", 1980, т. 25, в. 2, с. 389-93.