Понятие марковского случайного процесса реферат

Обновлено: 02.07.2024

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

Файлы: 1 файл

Марковские процессы, их математическое описание и область применения Тане.docx

Реферат по предмету Математический Аппарат Радиотехники

Выполнил: Ерохин А.А.

ЭЛЕМЕНТЫ ТЕОРИИ МАРКОВСКИХ СЛУЧАЙНЫХ ПРОЦЕССОВ.

Понятие марковского случайного процесса.

Функционирование широкого класса систем можно представить как процесс перехода из одного состояния в другое под воздействием каких-либо причин. Например, процесс функционирования ЭВМ характеризуется тем, что в каждый момент времени обработкой информации заняты те или иные блоки. Процесс прохождения обрабатываемой информации по блокам ЭВМ можно рассматривать как процесс перехода системы из одного состояния в другое. В полной мере это относится и к процессу функционирования ЭВМ с точки зрения надежности. В каждый момент времени некоторые узлы работоспособны, а некоторые отказали и

восстанавливаются. Если каждому возможному множеству работоспособных (или отказывающих) элементов поставить в соответствие множество состояний системы, то отказы и восстановления элементов будут отражаться переходом объекта из

одного состояния в другое.

Пусть имеется некоторая физическая система S, которая в процессе функционирования может принимать различные состояния Si. Если состояния системы меняются во времени случайным образом, то процесс смены состояний можно рассматривать как случайный процесс, описываемый случайной функцией X(b).

Полное множество состояний Si исследуемой системы может быть либо конечным (i = 1, n), либо бесконечно большим.

Большинство реальных систем имеет дискретное конечное пространство состояний. Последовательность состояний такой системы Si (i = 1, n) и сам процесс переходов из состояния в состояние называется цепью. Ниже будут рассмотрены только случайные цепи.

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

Для систем с дискретным временем время пребывания системы, в каждом состоянии фиксированное, а моменты переходов t1, t2, . tk размещаются на временной оси через равные промежутки и называются "шагами" или "этапами". Время нахождения системы в некотором состоянии представляет дискретную случайную величину.

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

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

одного состояния в другое.

МАРКОВСКИЕ СЛУЧАЙНЫЕ ПРОЦЕССЫ

С ДИСКРЕТНЫМИ СОСТОЯНИЯМИ И ДИСКРЕТНЫМ ВРЕМЕНЕМ

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

Пусть имеется некоторая система S, которая в процессе функционирования может принимать различные состояния Si, i=1..n. Если состояния системы меняются случайным образом, то последовательность состояний системы образует случайный процесс.

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

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

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

Обычно марковскую цепь изображают в виде графа, вершины которого соответствуют возможным состояниям системы Si, а дуги - возможным переходам системы из состояния Si -> Sj. Каждой дуге соответствует переходная вероятность Pij(k)=P[Sj(k)/Si(k-1)] - это условная вероятность перехода системы на К-ом шаге в состояние Sj при условии, что на предыдущем (К-1)-ом этапе система находилась в состоянии Si.

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

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

| P11 P12 . P1j . P1n|

| P21 P22 . P2j . P2n| n ____

|Pij| = | . | SUMMA(Pij)=1; i=1, n

| | Pi1 Pi2 . Pij . Pin| j=1

i | Pn1 Pn2 . Pnj . Pnn|

Для неоднородной марковской цепи требуется К матриц, где К - число шагов.

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

Пусть в начальный момент t0 система находится в состоянии Si.

Тогда Pi(0)=1, Pj(0)=0, j=1,2. n, j=/=i. Найдем вероятности состояний после 1-го шага P1(1)=Pi1, P2(1)=Pi2, . Pj(1)=Pij,

. Pn(1)=Pin. Найдем вероятность состояний после 2-го шага, рассматривая следующий набор гипотез:

- после 1-го шага система была в состоянии S1;

- после 1-го шага система была в состоянии S2;

- после 1-го шага система была в состоянии Sn.

Вероятности гипотез известны и равны вероятностям состояний системы после 1-го шага.

Тогда по формуле полной вероятности:

Pi(2)=SUMMA [Pj(1)*Pji] i=1,n

Аналогично после 3-го шага вероятности определяются выражением

Pi(3) = SUMMA [Pj(2)*Pji] i=1,n

Pi(k)= SUMMA [Pj(k-1)*Pji i=1,n

Аналогично для неоднородной марковской цепи

Pi(k)= SUMMA [Pj(k-1)*Pji(k)] (2)

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

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

Эргодические марковские цепи описываются сильно связанным графом. Это означает, что в такой системе возможен переход из любого состояния Si в любое состояние Sj (i,j=1..n) за конечное число шагов.

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

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

Для определения стационарных вероятностей Pi нахождения системы в состоянии Si (i=1..n) нужно составить систему n линейных однородных алгебраических уравнений с n неизвестными:

Pi= SUMMA(Pj*Pji) i=1..n (3)

Причем, искомые вероятности должны удовлетворять условию:

или, что равносильно Pi=1- SUMMA Pj (4)

Поэтому любое уравнение системы (3) можно заменить уравнением (4).

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

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

Продолжительность нахождения системы в каждом состоянии кратна длительности шага дельта t.

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

| S3 | 0,8 | 0,05| 0,15|

S1 - состояние, в котором реализуются задачи пользователя

S2 - состояние, в котором реализуются программы операционной системы

S3 - состояние простоя

Граф функционирования системы имеет вид:

Составим для установившегося режима систему линейных алгебраических уравнений.

Р1 = 0,7P1 + 0,8P2 + 0,8P3

Р2 = 0,2P1 + 0,1P2 + 0,05P3

Р3 = 0,1P1 + 0,1P2 + 0,15P3

В результате решения получаем значение вероятностей состояния в установленном режиме:

Р1 = 0,749; Р2 = 0,154; Р3 = 0,097.

Коэффициент простоя процессора Кп = Р3 = 0,097.

Коэффициент использования Ри = 1 - Кп = 0,903, при этом на обработку программ пользователя затрачивается 74,3% времени, а на обслуживание операционной

Непрерывные марковские цепи.

Непрерывные марковские цепи описывают функционирование систем, принимающих в процессе работы конечное число состояний Si (i = 1, n) и осуществляющих переходы из одного состояния в другое (Si --> Sj, i, j = 1, n) случайным образом в произвольный момент времени t. Иначе говоря, время пребывания системы в

любом состоянии представляет непрерывную случайную величину.

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

Определим для непрерывной марковской цепи вероятности всех состояний системы для любого момента времени Pi(t), i = 1,n. Так как для любого момента времени t все состояния системы образуют полную группу событий, то

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

Содержание работы

Введение 1
Понятие случайного процесса 2
2. Понятие марковского случайного процесса 5
3. Марковские процессы с дискретным временем 7
4. Марковские процессы с непрерывным временем 13
5. Процессы размножения и гибели 18
Список литературы: 26

Файлы: 1 файл

Реферат. Марковский процесс.doc

Введение

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

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

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

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

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

Понятие случайного процесса

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

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

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

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

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

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

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

Обозначим через g(t) случайный процесс с дискретными состояниями, а возможные значения g(t), т.е. возможные состояния цепи, - через символы E₀, E₁, E₂, … . Иногда для обозначения дискретных состояний используют числа 0, 1, 2. из натурального ряда.

Случайный процесс g(t) называется процессом с дискретным временем, если переходы процесса из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времени t₀, t₁, t₂, …. Если переход процесса из состояния в состояние возможен в любой, заранее неизвестный момент времени, то случайный процесс называется процессом с непрерывным временем. В первом случае, очевидно, что интервалы времени между переходами являются детерминированными, а во втором - случайными величинами.

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

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

Содержание

Введение.
§1. Основные понятия.
§2. Виды Марковских процессов.
§3.Решение задачи.
Заключение.
Список литературы.

Вложенные файлы: 1 файл

Kursovaya_Mat_metody.doc

§1. Основные понятия.

§2. Виды Марковских процессов.

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

1. Основные понятия Марковских процессов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1 Ориентированный взвешенный граф

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

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

Рис.2. Невозвратное множество

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

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

Рис. 3. Возвратное множество

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

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

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

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

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

Рис. 5. Поглощающее множество

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

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

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

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

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

Марковские цепи.
Марковские последовательности.
Марковские процессы с конечным числом состояний.
Марковские процессы с бесконечным числом состояний.
Дискретно-непрерывные марковские процессы.
Смешанные марковские процессы.

2.Виды Марковских процессов

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

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

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

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

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

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

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

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

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

Основным математическим соотношением для ДМЦ является уравнение, с помощью которого определяется состояние системы на любом ее k-м шаге. Это уравнение имеет вид:

и называется уравнением Колмогорова-Чепмена.

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

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

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

Рис. 9. Пример графа Марковского процесса с непрерывным временем

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

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

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

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

Зная интенсивность λ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, указывающий, в какое именно состояние произойдет переход.

Рассмотрим пример. Моделирование работы станка. Промоделируем работу станка (см. рис.10), который может находиться в следующих состояниях: S0 — станок исправен, свободен (простой); S1 — станок исправен, занят (обработка); S2 — станок исправен, замена инструмента (переналадка) λ02

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

В частности, из рис. 10 видно, что реализовавшаяся цепь выглядит так: S0—S1—S0—… Переходы произошли в следующие моменты времени: T0—T1—T2—T3—…, где T0 = 0, T1 = τ01, T2 = τ01 + τ10.

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

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

Таким образом, случайное блуждание − пример однородной цепи Маркова с дискретным временем.

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

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

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

Пусть число состояний конечно и равно k.

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

Так как в каждой строке матрицы помещены вероятности событий (перехода из одного и того же состояния i в любое возможное состояние j), которые образуют полную группу, то сумма вероятностей этих событий равна единице. Другими словами, сумма переходных вероятностей каждой строки матрицы перехода равна единице:

2.3. Однородная цепь Маркова. Переходные вероятности. Матрица перехода.

Определение. Однородной называют цепь Маркова, если условная вероятность (переход из состояния i в состоянии j) не зависит от номера испытания. Поэтому вместо пишут просто .

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

Функция X(t) называется случайной, если ее значение при любом аргументе t является случайной величиной.

Случайная функция X(t), аргументом которой является время, называетсяслучайным процессом.

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

Определение. Случайный процесс, протекающий в какой-либо системе S, называется марковским (или процессом без последействия), если он обладает следующим свойством: для любою момента времени t₀ вероятность любого состояния системы в будущем (при t > t₀) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, когда и каким образом система S пришла в это состояние. То есть в марковском случайном процессе будущее развитие процесса не зависит от его предыстории.

Классификация марковских процессов.Классификация марковских случайных процессов производится в зависимости от непрерывности или дискретности множества значений функции X(t) и параметра t. Различают следующие основные виды марковских случайных процессов:

· с дискретными состояниями и дискретным временем (цепь Маркова);

· с непрерывными состояниями и дискретным временем (марковские последовательности);

· с дискретными состояниями и непрерывным временем (непрерывная цепь Маркова);

· с непрерывным состоянием и непрерывным временем.

Здесь будут рассматриваться только марковские процессы с дискретными состояниями S₁, S₂,…, S_n. То есть эти состояния можно перенумеровать одно за другим, а сам процесс состоит в том, что система случайным образом скачком меняет свое состояние.

Рис. 3.1. Граф состояний системы S

Задача 1. Система S – автомобиль, которая может находиться в одном из пяти состояний.

S₁ – исправна, работает;

S₂ – неисправна, ожидает осмотра;

S₃ –осматривается;

S₄ – ремонтируется;

Построить граф состояний системы.

Задача 2.Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. У каждого узла может быть только 2 состояния. 1 – исправен, 2 – неисправен. Построить граф состояний системы.

Задача 3.Построить граф состояний в условиях предыдущей задачи, предполагая, что ремонт узлов в ходе процесса не производится.

Задача 4. Техническое устройство S состоит из 2-х узлов: 1 и 2, каждый из которых может в любой момент времени отказать. Каждый узел, перед тем как начать восстанавливаться подвергается осмотру с целью локализации неисправности. Состояния системы нумеруются 2-мя индексами: S_ij (i – состояния первого узла, j – состояния второго узла). У каждого узла три состояния (работает, осматривается, восстанавливается).

Читайте также: