Ирина Эланс

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

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

Содержание

Введение.

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

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

§3.Решение задачи.

Заключение.

Список литературы.

Введение

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

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

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-м шаге. Это уравнение имеет вид:

(4)

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

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

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 < λ21; S3 — станок неисправен, идет ремонт λ13 < λ30.

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

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

Рис. 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) не зависит от номера испытания. Поэтому вместо пишут просто .

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

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

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

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

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

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

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

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

Пример 2. По заданной матрице перехода построить граф состояний.

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

0.2 0.7

S2 0.4 S4

0.6 0.5

0.1 0.5

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

2.4. Цепь Маркова.

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

Определение. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется одно и только одно из k несовместных событий полной группы, причем условная вероятность того, что в S-м испытании наступит событие , при условии, что в (s-1)-м испытании наступило событие , не зависит от результатов предшествующих испытаний.

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

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

Часто при изложении теории цепей Маркова придерживаются иной терминология и говорят о некоторой физической системе S, которая в каждый момент времени находится в одном из состояний: , и меняет свое состояние только в отдельные моменты времени то есть система переходит из одного состояния в другое ( например из i в j). Для цепей Маркова вероятность перейти в какое-либо состояние в момент зависит только от того, в каком состоянии система находилась в момент , и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния i в состояние j = i).

Для иллюстрации рассмотрим пример.

Представим, что частица, находящаяся на прямой, движется по этой ней под влиянием случайных толчков, происходящих в моменты . Частица может находиться в точках с целочисленными координатами: a,a+1,a+2,…,b ; в точках a и b находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью p и влево с вероятностью q=1-p, если только частица не находится у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка между стенками. Здесь мы видим, что этот пример блуждания частицы представляет собой типичную цепь Маркова.

Таким образом, события называют состояниями системы, а испытания – изменениями ее состояний.

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

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

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

Задача.

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

после осуществления доставки в район А следующая доставка в 30 случаях осуществляется в А, в 30 случаях – в В и в 40 случаях – в С;

после осуществления доставки в район В следующая доставка в 40 случаях осуществляется в А, в 40 случаях – в В и в 20 случаях – в С;

после осуществления доставки в район С следующая доставка в 50 случаях осуществляется в А, в 30 случаях – в В и в 20 случаях – в С.

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

Матрица вероятностей перехода будет выглядеть следующим образом:

Например, = 0,4 – это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А.

Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в районе А, будут в А, 30% будут в В и 40% – в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, то каждый элемент матрицы будет 0 < < 1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени (t + 1) зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь района В в 2 шага? Итак, существует несколько путей из С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С® В и В ® В;

3) С ® А и А ® В.

Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:

Р = Р(СА) × Р(АВ) + Р(СВ) × Р(ВВ) + Р(СС) × Р(СВ).

Подставляя числовые значения:

Р = 0,5 × 0,3 + 0,3 × 0,4 + 0,2 × 0,3 = 0,33.

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки.

Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок – это может занять довольно много времени.

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

Тогда элемент (2, 3) – это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице Р2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ.

р(СА) × Р(АВ) + р(СВ) × Р(ВВ) + р(СС) × Р(СВ) =

= 0,37 × 0,3 + 0,33 × 0,4 + 0,3 × 0,3 = 0,333,

где р(СА) – вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы Р2).

2 способ. Вычислить матрицу Р3:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уже не имеет значение в каком округе курьер начал работу. Таким образом, в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Список литературы:

http://referatwork.ru/new/source/66326text-66326.html
http://portal.tpu.ru/SHARED/l/LASUKOV/tv/Tab3/g5.pdf
http://matmodel.ru/article.php/20090122191350482
http://rfwiki.org/%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81
http://slovar-lopatnikov.ru/slovar/m/markovskij-process/
http://ru.convdocs.org/docs/index-114225.html?page=2
http://www.km.ru/referats/9023B19914564AD79F6597EECB607992#
Дискретные цепи Маркова и их применение (Волгоград 2011)
http://slovari.yandex.ru/марковский%20процесс/БСЭ/Марковский%20процесс/
http://dic.academic.ru/dic.nsf/enc_mathematics/3015/МАРКОВСКИЙ
http://www.masters.donntu.edu.ua/2008/kita/ivanova/library/recognition/markov.htm

Марковские случайные процессы 📙 Курсовая → 🆔 120823