Что такое марковский процесс

Марковские процессы

Марковский процесс — случайный процесс, эволюция которого после любого заданного значения временно́го параметра t не зависит от эволюции, предшествовавшей t , при условии, что значение процесса в этот момент фиксировано (короче: «будущее» процесса не зависит от «прошлого» при известном «настоящем»).

История

Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым, который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова. Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как марковский процесс, попытку, получившую обоснование после исследований Винера в 1923. Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым.

Wikimedia Foundation . 2010 .

Смотреть что такое «Марковские процессы» в других словарях:

• Марковские процессы — вероятностные процессы, обладающие тем свойством, что при известном значении процесса в момент времени поведение процесса в более поздние моменты времени не зависит от его поведения до момента. Типичными примерами марковских процессов являются… … Начала современного естествознания
• СКАЧКООБРАЗНЫЕ МАРКОВСКИЕ ПРОЦЕССЫ — класс марковских случайныхпроцессов, у к рых значения изменяются мгновенно (скачки) в отдельные(случайные) моменты времени. В наиб. простом случае, когда марковский процесс может принимать лишь конечное или счётное число значений x1. х п … Физическая энциклопедия
• МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ — процессы без вероятностного последствия, статистич. свойства к рых в последующие моменты времени зависят только от значений процессов в данный момент и не зависят от их предыстории. M.с … Физическая энциклопедия
• ВЕРОЯТНОСТЕЙ ТЕОРИЯ — математическая наука, позволяющая по вероятностям одних случайных событий находить вероятности других случайных событий, связанных к. л. образом с первыми. Утверждение о том, что к. л. событие наступает с вероятностью, равной, напр., 1/2, еще не… … Математическая энциклопедия
• Вероятностей теория — математическая наука, позволяющая по вероятностям одних случайных событий находить вероятности других случайных событий, связанных каким либо образом с первыми. Утверждение о том, что какое либо событие наступает с Вероятностью,… … Большая советская энциклопедия
• МАРКОВСКИЙ ПРОЦЕСС — процесс без последействия, случайный процесс, эволюция к рого после любого заданного значения временного параметра tне зависит от эволюции, предшествовавшей t, при условии, что значение процесса в этот момент фиксировано (короче: будущее н… … Математическая энциклопедия
• Доказательства эволюции — Ископаемый археоптерикс, обнаруженный вскоре после публикации « … Википедия
• КОЛМОГОРОВА — ФЁЛЛЕРА УРАВНЕНИЕ — интегродифференц. ур ние для переходной плотности вероятности марковских случайных процессов с разрывными (скачкообразными) изменениями состояния. Получено А. Н. Колмогоровым в 1938 и У. Феллером (W. Feller) в 1940. Пусть, напр., реализации… … Физическая энциклопедия
• ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ — раздел математики, посвященный теории и методам решения многошаговых задач оптимального управления. В Д. п. для управляемых процессов среди всевозможных управлений ищется то, к рое доставляет экстремальное (наименьшее или наибольшее) значение… … Математическая энциклопедия
• ЭКСЦЕССИВНАЯ ФУНКЦИЯ — для марковского процесса аналог неотрицательной супергармонической функции. Пусть в измеримом пространстве задана однородная марковская цепь с вероятностями перехода за один шаг Измеримая относительно функция наз. эксцессивной функцией для этой… … Математическая энциклопедия

Лекция 33.
Моделирование марковских случайных
процессов

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

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

Итак, марковский процесс удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов — с дискретным и непрерывным временем.

В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени — такты (1, 2, 3, 4, ). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.

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

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

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

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

Рис. 33.1. Пример графа переходов

Каждый переход характеризуется вероятностью перехода P_ij . Вероятность P_ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.

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

Рис. 33.2. Фрагмент графа переходов (переходы из i-го состояния являются полной группой случайных событий)

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

Рис. 33.3. Пример марковского графа переходов

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

Рис. 33.4. Пример марковской цепи, смоделированной по марковскому графу, изображенному на рис. 33.3

Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал [0; 1] на подынтервалы величиной P_i1 , P_i2 , P_i3 , ( P_i1 + P_i2 + P_i3 + = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале [0; 1] случайное число r_рр и определить, в какой из интервалов оно попадает (см. лекцию 23).

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

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

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

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

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

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

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

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

Рис. 33.6. Граф марковского процесса, моделирующий стрельбу из пушки по цели

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

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

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

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

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

Рис. 33.7. Временная диаграмма переходов в марковском графе (пример имитации)

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

Повторяя данную имитацию, можно получить, например, еще такие реализации (это зависит от того, какие конкретно случайные числа выпадут): 4 ( S₀—S₀—S₁—S₁—S₂ ); 11 ( S₀—S₀—S₀—S₀—S₀—S₁—S₁—S₁—S₁—S₁—S₁—S₂ ); 5 ( S₁—S₁—S₁—S₁—S₁—S₂ ); 6 ( S₀—S₀—S₁—S₁—S₁—S₁—S₂ ); 4 ( S₁—S₁—S₁—S₁—S₂ ); 6 ( S₀—S₀—S₁—S₁—S₁—S₁—S₂ ); 5 ( S₀—S₀—S₁—S₁—S₁—S₂ ). Всего уничтожено 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.8. Изменение средней величины в зависимости от номера эксперимента

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

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

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

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

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

Рис. 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₀ — станок исправен, свободен (простой); S₁ — станок исправен, занят (обработка); S₂ — станок исправен, замена инструмента (переналадка) λ₀₂ < λ₂₁ ; S₃ — станок неисправен, идет ремонт λ₁₃ < λ₃₀ .

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

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

Рис. 33.11. Пример моделирования непрерывного марковского процесса с визуализацией на временной диаграмме (желтым цветом указаны запрещенные, синим — реализовавшиеся состояния)

В частности, из рис. 33.11 видно, что реализовавшаяся цепь выглядит так: S₀—S₁—S₀—&#133 Переходы произошли в следующие моменты времени: T₀—T₁—T₂—T₃—&#133 , где T₀ = 0 , T₁ = τ₀₁ , T₂ = τ₀₁ + τ₁₀ .

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

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

Рис. 33.12. Блок-схема алгоритма моделирования непрерывного марковского процесса на примере имитации работы станка

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

Марковский процесс, сущность и применение кратко

Привет, сегодня поговорим про марковский процесс, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое марковский процесс , настоятельно рекомендую прочитать все из категории вероятностные процессы. марковский процесс — случайный процесс, эволюция которого после любого заданного значения временно́го параметра не зависит от эволюции, предшествовавшей , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»). Процесс Маркова — модель авторегрессии первого порядка AR(1): x_t=ψ₁*x_t-1+ε_t Случайный процесс, протекающий в системе, называется марковским, если он обладает отсутствием последствия. Т.е. если рассматривать текущее состояние процесса — как настоящее, совокупность возможных состояний — как прошлое, совокупность возможных состояний — как будущее, то для марковского процесса при фиксированном настоящем будущее не зависит от прошлого, а определяется лишь настоящим и не зависит от того, когда и как система пришла в это состояние. Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать «динамикой вероятностей». В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д.

История

Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым, который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова. Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как марковский процесс, попытку, получившую обоснование после исследований Винера в 1923. Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым.

Классификация марковских процессов

Отличие Марковского процесса от Марковской цепи

Марковская цепь с дискретным временем — время дискретно, пространство состояний дискретно. Марковская цепь с непрерывным временем — время непрерывно, пространство состояний дискретно. Марковский процесс — и время, и пространство состояний непрерывно.

Марковское свойство

Марковское свойство

Общий случай

Пусть — вероятностное пространство с фильтрацией по некоторому (частично упорядоченному) множеству ; и пусть — cигма-алгебра. Об этом говорит сайт https://intellect.icu . Случайный процесс , определенный на фильтрованном вероятностном пространстве, считается удовлетворяющим марковскому свойству, если для каждого и , Марковский процесс — это случайный процесс, удовлетворяющий марковскому свойству с естественной фильтрацией.

Для марковских цепей с дискретным временем

В случае, если является дискретным множетсвом и , определение может быть переформулировано: .

Пример марковского процесса

Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета — если выпал герб, то точка X перемещается на одну единицу длины вправо, если цифра — влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путем и за какое время точка попала в текущую координату).

Диаграмма, представляющая марковский процесс с двумя состояниями, с состояниями, обозначенными E и A. Каждое число представляет вероятность перехода марковского процесса из одного состояния в другое в направлении, указанном стрелкой. Например, если марковский процесс находится в состоянии A, то вероятность, что он перейдет в состояние E, равна 0,4, а вероятность, что он останется в состоянии A, равна 0,6.

Марковские процессы. Пример.

Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохра-нившихся (не сбитых) самолетов соответственно – x0, y0.
Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта ве-роятность зависит от того, в каком состоянии находилась си-стема в момент времени t0, а не от того, когда и в какой после-довательности погибали сбитые до момента t0 самолеты

Применение Марковских процессов

• Биология: процессы рождения и гибели — популяции, мутации, эпидемии.
• Физика: радиоактивные распады, теория счетчиков элементарных частиц, процессы диффузии.
• Химия: теория следов в ядерных фотоэмульсиях, вероятностные модели химической кинетики.
• Астрономия: теория флуктуационной яркости млечного пути.
• Теория массового обслуживания: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, станочные и другие технологические системы, системы управления гибких производственных систем, обработка информации серверами.

Вау!! �� Ты еще не читал? Это зря!

• Цепь Маркова
• немарковский процесс ,
• Скрытая марковская модель
• Марковское свойство
• Динамика марковских частиц
• Процесс Гаусса – Маркова
• Метод аппроксимации цепей Маркова
• Геостатистика цепи Маркова
• Время перемешивания цепи Маркова
• Марковский процесс принятия решений
• Марковский источник информации
• Марковский одометр
• Марковское случайное поле
• Квантовая цепь Маркова
• Полумарковский процесс
• Марковское обновление
• Стохастический клеточный автомат
• Телескопическая цепь Маркова
• Марковская модель переменного порядка

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

Из статьи мы узнали кратко, но содержательно про марковский процесс

Марковский процесс

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

История

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

Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как марковский процесс, попытку, получившую обоснование после исследований Винера в 1923.

Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым.

Отличие Марковского процесса от Марковской цепи

Марковская цепь с дискретным временем — время дискретно, пространство состояний дискретно.

Марковская цепь с непрерывным временем — время непрерывно, пространство состояний дискретно

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

См. также

• Цепь Маркова
• Немарковский процесс
• Скрытая марковская модель

Ссылки

• Weisstein, Eric W.Markov process (англ.) на сайте Wolfram MathWorld.

• Марковские процессы