Классификация состояний марковских процессов. Марковский процесс Какие процессы можно отнести к марковским
Случайный процесс 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 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
матричная форма которого имеет вид
П(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 конечно и имеет порядок .
Для математического описания многих операций, развивающихся в форме случайного процесса, может быть с успехом применен математический аппарат, разработанный в теории вероятностей для Марковских случайных процессов.
Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной величиной.
Случайная функция X(t) , аргументом которой является время, называетсяслучайным процессом .
Марковские процессы являются частным видом случайных процессов. Особое место марковских процессов среди других классов случайных процессов обусловлено следующими обстоятельствами: для марковских процессов хорошо разработан математический аппарат, позволяющий решать многие практические задачи; с помощью марковских процессов можно описать (точно или приближенно) поведение достаточно сложных систем.
Определение. Случайный процесс, протекающий в какой-либо системе S , называется марковским (или процессом без последействия), если он обладает следующим свойством: для любою момента времени t 0 вероятность любого состояния системы в будущем (при t > t 0 ) зависит только от ее состояния в настоящем (при t = t 0 ) и не зависит от того, когда и каким образом система S пришла в это состояние. То есть в марковском случайном процессе будущее развитие процесса не зависит от его предыстории.
Классификация марковских процессов. Классификация марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции X(t) и параметра t . Различают следующие основные виды марковских случайных процессов:
· с дискретными состояниями и дискретным временем (цепь Маркова);
· с непрерывными состояниями и дискретным временем (марковские последовательности);
· с дискретными состояниями и непрерывным временем (непрерывная цепь Маркова);
· с непрерывным состоянием и непрерывным временем.
Здесь будут рассматриваться только марковские процессы с дискретными состояниями S 1 , S 2 ,…, S n . То есть эти состояния можно перенумеровать одно за другим, а сам процесс состоит в том, что система случайным образом скачком меняет свое состояние.
Граф состояний. Марковские процессы с дискретными состояниями удобно иллюстрировать с помощью так называемого графа состояний (рис. 1.1.), где квадратиками обозначены состояния S 1 , S 2 , ... системы S , а стрелками - возможные переходы из состояния в состояние. На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные задержки в прежнем состоянии изображают «петлей», т. е. стрелкой, направленной из данного состояния в него же. Число состояний системы может быть как конечным, так и бесконечным (но счетным).
Рис. 3.1. Граф состояний системы S
Задача 1. Система S – автомобиль, которая может находиться в одном из пяти состояний.
S 1 – исправна, работает;
S 2 – неисправна, ожидает осмотра;
S 3 –осматривается;
S 4 – ремонтируется;
S 5 – списана.
Построить граф состояний системы.
Задача 2. Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. У каждого узла может быть только 2 состояния. 1 – исправен, 2 – неисправен. Построить граф состояний системы.
Задача 3. Построить граф состояний в условиях предыдущей задачи, предполагая, что ремонт узлов в ходе процесса не производится.
Задача 4. Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. Каждый узел, перед тем как начать восстанавливаться подвергается осмотру с целью локализации неисправности. Состояния системы нумеруются 2-мя индексами: S ij (i – состояния первого узла, j – состояния второго узла). У каждого узла три состояния (работает, осматривается, восстанавливается).
Эволюция которого после любого заданного значения временно́го параметра t {\displaystyle t} не зависит от эволюции, предшествовавшей t {\displaystyle t} , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»).
Энциклопедичный YouTube
1 / 3
✪ Лекция 15: Марковские случайные процессы
✪ Происхождение марковских цепей
✪ Обобщенная модель марковского процесса
Субтитры
История
Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым , который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова .
Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым .
Марковское свойство
Общий случай
Пусть
(Ω
,
F
,
P)
{\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P})}
- вероятностное пространство с фильтрацией
(F
t
,
t
∈
T)
{\displaystyle ({\mathcal {F}}_{t},\ t\in T)}
по некоторому (частично упорядоченному) множеству
T
{\displaystyle T}
; и пусть
(S
,
S)
{\displaystyle (S,{\mathcal {S}})}
- измеримое пространство . Случайный процесс
X
=
(X
t
,
t
∈
T)
{\displaystyle X=(X_{t},\ t\in T)}
, определённый на фильтрованном вероятностном пространстве, считается удовлетворяющим марковскому свойству
, если для каждого
A
∈
S
{\displaystyle A\in {\mathcal {S}}}
и
s
,
t
∈
T:
s
<
t
{\displaystyle s,t\in T:s
Марковский процесс - это случайный процесс, удовлетворяющий марковскому свойству с естественной фильтрацией .
Для марковских цепей с дискретным временем
В случае, если S {\displaystyle S} является дискретным множеством и T = N {\displaystyle T=\mathbb {N} } , определение может быть переформулировано:
P (X n = x n | X n − 1 = x n − 1 , X n − 2 = x n − 2 , … , X 0 = x 0) = P (X n = x n | X n − 1 = x n − 1) {\displaystyle \mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{0}=x_{0})=\mathbb {P} (X_{n}=x_{n}|X_{n-1}=x_{n-1})} .Пример марковского процесса
Рассмотрим простой пример марковского случайного процесса. По оси абсцисс случайным образом перемещается точка. В момент времени ноль точка находится в начале координат и остается там в течение одной секунды. Через секунду бросается монета - если выпал герб, то точка X перемещается на одну единицу длины вправо, если цифра - влево. Через секунду снова бросается монета и производится такое же случайное перемещение, и так далее. Процесс изменения положения точки («блуждания ») представляет собой случайный процесс с дискретным временем (t=0, 1, 2, …) и счетным множеством состояний. Такой случайный процесс называется марковским, так как следующее состояние точки зависит только от настоящего (текущего) состояния и не зависит от прошлых состояний (неважно, каким путём и за какое время точка попала в текущую координату).
Очень удобно описывать появление случайных событий в виде вероятностей переходов из одного состояния системы в другое, так как при этом считается, что, перейдя в одно из состояний, система не должна далее учитывать обстоятельства того, как она попала в это состояние.
Случайный процесс называется марковским процессом (или процессом без последействия ), если для каждого момента времени t вероятность любого состояния системы в будущем зависит только от ее состояния в настоящем и не зависит от того, как система пришла в это состояние.
Итак, марковский процесс удобно задавать графом переходов из состояния в состояние. Мы рассмотрим два варианта описания марковских процессов с дискретным и непрерывным временем .
В первом случае переход из одного состояния в другое происходит в заранее известные моменты времени такты (1, 2, 3, 4, ). Переход осуществляется на каждом такте, то есть исследователя интересует только последовательность состояний, которую проходит случайный процесс в своем развитии, и не интересует, когда конкретно происходил каждый из переходов.
Во втором случае исследователя интересует и цепочка меняющих друг друга состояний, и моменты времени, в которые происходили такие переходы.
И еще. Если вероятность перехода не зависит от времени, то марковскую цепь называют однородной .
Марковский процесс с дискретным временем
Итак, модель марковского процесса представим в виде графа, в котором состояния (вершины) связаны между собой связями (переходами из i -го состояния в j -е состояние), см. рис. 33.1 .
Каждый переход характеризуется вероятностью перехода P ij . Вероятность P ij показывает, как часто после попадания в i -е состояние осуществляется затем переход в j -е состояние. Конечно, такие переходы происходят случайно, но если измерить частоту переходов за достаточно большое время, то окажется, что эта частота будет совпадать с заданной вероятностью перехода.
Ясно, что у каждого состояния сумма вероятностей всех переходов (исходящих стрелок) из него в другие состояния должна быть всегда равна 1 (см. рис. 33.2 ).
(переходы из i-го состояния являются
полной группой случайных событий)
Например, полностью граф может выглядеть так, как показано на рис. 33.3 .
Реализация марковского процесса (процесс его моделирования) представляет собой вычисление последовательности (цепи) переходов из состояния в состояние (см. рис. 33.4 ). Цепь на рис. 33.4 является случайной последовательностью и может иметь также и другие варианты реализации.
по марковскому графу, изображенному на рис. 33.3
Чтобы определить, в какое новое состояние перейдет процесс из текущего i -го состояния, достаточно разбить интервал на подынтервалы величиной P i 1 , P i 2 , P i 3 , (P i 1 + P i 2 + P i 3 + = 1 ), см. рис. 33.5 . Далее с помощью ГСЧ надо получить очередное равномерно распределенное в интервале случайное число r рр и определить, в какой из интервалов оно попадает (см. лекцию 23).
состояния марковской цепи в j-е с использованием
генератора случайных чисел
После этого осуществляется переход в состояние, определенное ГСЧ, и повтор описанной процедуры для нового состояния. Результатом работы модели является марковская цепь (см. рис. 33.4 ) .
Пример. Имитация стрельбы из пушки по цели . Для того, чтобы проимитировать стрельбу из пушки по цели, построим модель марковского случайного процесса.
Определим следующие три состояния: S 0 цель не повреждена; S 1 цель повреждена; S 2 цель разрушена. Зададим вектор начальных вероятностей:
S 0 | S 1 | S 2 | |
P 0 | 0.8 | 0.2 | 0 |
Значение P 0 для каждого из состояний показывает, какова вероятность каждого из состояний объекта до начала стрельбы.
Зададим матрицу перехода состояний (см. табл. 33.1).
Таблица 33.1. Матрица вероятностей перехода дискретного марковского процесса |
|||||||||||||||||||
В S 0 | В S 1 | В S 2 | Сумма вероятностей переходов |
|
Из S 0 | 0.45 | 0.40 | 0.15 | 0.45 + 0.40 + 0.15 = 1 |
Из S 1 | 0 | 0.45 | 0.55 | 0 + 0.45 + 0.55 = 1 |
Из S 2 | 0 | 0 | 1 | 0 + 0 + 1 = 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 ).
марковского процесса на примере имитации работы станка
Очень часто аппарат марковских процессов используется при моделировании компьютерных игр, действий компьютерных героев.
Для системы массового обслуживания характерен случайный процесс. Изучение случайного процесса, протекающего в системе, выражение его математически и является предметом теории массового обслуживания.
Математический анализ работы системы массового обслуживания значительно облегчается, если случайный процесс этой работы является марковским. Процесс, протекающий в системе, называется марковским, если в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние. При исследовании экономических систем наибольшее применение имеют марковские случайные процессы с дискретными и непрерывными состояниями.
Случайный процесс называется процессом с дискретными состояниями, если все его возможные состояния можно заранее перечислить, а сам процесс состоит в том, что время от времени система скачком переходит из одного состояния в другое.
Случайный процесс называется процессом с непрерывным состоянием, если для него характерен плавный, постепенный переход из состояния в состояние.
Также можно выделить марковские процессы с дискретным и непрерывным временем. В первом случае переходы системы из одного состояния в другое возможны только в строго определенные, заранее фиксированные моменты времени. Во втором случае переход системы из состояния в состояние возможен в любой, заранее неизвестный, случайный момент. Если вероятность перехода не зависит от времени, то марковский процесс называют однородным.
В исследовании систем массового обслуживания большое значение имеют случайные марковские процессы с дискретными состояниями и непрерывным временем.
Исследование марковских процессов сводится к изучению матриц переходных вероятностей (). Каждый элемент такой матрицы (поток событий) представляет собой вероятность перехода из заданного состояния (которому соответствует строка) к следующему состоянию (которому соответствует столбец). В этой матрице предусмотрены все возможные переходы данного множества состояний. Следовательно, процессы, которые можно описывать и моделировать с помощью матриц переходных вероятностей, должны обладать зависимостью вероятности конкретного состояния от непосредственно предшествующего состояния. Так выстраивается цепь Маркова. При этом цепью Маркова первого порядка называется процесс, для которого каждое конкретное состояние зависит только от его предшествующего состояния. Цепью Маркова второго и более высоких порядков называется процесс, в котором текущее состояние зависит от двух и более предшествующих.
Ниже представлены два примера матриц переходных вероятностей.
Матрицы переходных вероятностей можно изобразить графами переходных состояний, как показано на рисунке.
Пример
Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия.
В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1):
Первая итерация – построение матрицы двухступенчатых переходов.
Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна
Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна
Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна
Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна
В результате расчетов получаем матрицу двухступенчатых переходов:
Результат достигается перемножением матрицы т,на матрицу с такими же значениями вероятностей:
Для проведения этих процедур в среде Excel необходимо выполнить следующие действия:
- 1) формировать матрицу;
- 2) вызывать функцию МУМНОЖ;
- 3) указывать первый массив – матрицу;
- 4) указывать второй массив (эта же матрица или другая);
- 5) ОК;
- 6) выделить зону новой матрицы;
- 7) F2;
- 8) Ctrl+Shift+Enter;
- 9) получить новую матрицу.
Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид:
Таким образом, в ближайшие два месяца работы предприятия вероятность получения прибыли от выпуска продукта выше, по сравнению с вероятностью получения убытка. Однако следует заметить, что вероятность получения прибыли падает, поэтому предприятию необходимо осуществить разработку нового продукта для замены производимого продукта.