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

Министерство образования  и науки РФ

федеральное государственное  бюджетное образовательное учреждение высшего профессионально образования

Забайкальский государственный  университет

(ФГБОУ – ВПО «ЗабГУ»)

Энергетический факультет

 

 

 

 

 

 

 

 

 

Реферат

на тему: «Случайные процессы. Цепи Маркова»

 

 

 

 

 

 

 

 

 

Выполнили: ст.гр. ЭУЭ-10

 

Проверил:

 

 

 

 

Чита 2012

Содержание

Введение

1. Понятие случайного процесса
2. Цепь Маркова
3. Однородная цепь Маркова. Переходные вероятности. Матрица перехода
4. Области применения цепей Маркова

Заключение

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

 

Введение

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

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

 

                

 

 

 

 

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

 

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Цепь Маркова

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

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

.

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

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

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

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

Классификация состояний  цепи Маркова:

• Возвратное состояние
• Возвратная цепь Маркова
• Достижимое состояние
• Неразложимая цепь Маркова
• Периодическое состояние
• Периодическая цепь Маркова
• Поглощающее состояние
• Эргодическое состояние

 

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

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

.

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

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

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

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

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

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

Матрицей  перехода системы:

Пусть {E₁, E₂, ..., E_k} - множество состояний некоторой физической системы. В любой момент времени система может находиться в одном состоянии и меняет свое состояние только в моменты t₁, t₂, ..., t_n, .... Для однородных цепей Маркова вероятность  перехода системы из состояния  в состояние  за один шаг зависит только от того, из какого состояния в какое осуществлялся переход.

Вероятности перехода удобно располагать в виде матрицы. Обозначим  ее:

и будем называть матрицей перехода однородной цепи Маркова за один шаг.

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

(i = 1, 2, …, k)

0 ≤ P_ij ≤ 1

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

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

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

Пример 2.

Частица, находящаяся на прямой, движется по этой прямой под влиянием случайных  толчков, происходящих в моменты  t₁, t₂, t₃, ... Частица может находиться в точках с целочисленными координатами 1, 2, 3, 4, 5; в точках 1 и 5 находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью  и влево с вероятностью, если частицы не находятся у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка [1,5]. Найти матрицу перехода P и ей соответствующий граф.

Решение. Пусть , E_i = (t); t  = 1, 2, 3, 4, 5. Тогда граф перехода выглядит следующим образом:

A матрица перехода –

 

 

 

4 Области применения цепей Маркова

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

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

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

Стационарные процессы. Самая старая из известных эргодических теорем, как отмечалось выше, может быть интерпретирована как результат, описывающий предельное поведение стационарного случайного процесса. Такой процесс обладает тем свойством, что все вероятностные законы, которым он удовлетворяет, остаются инвариантными относительно сдвигов по времени. Эргодическую теорему, впервые сформулированную физиками в качестве гипотезы, можно представить как утверждение о том, что при определенных условиях среднее по ансамблю совпадает со средним по времени. Это означает, что одну и ту же информацию можно получить из долговременного наблюдения за системой и из одновременного (и одномоментного) наблюдения многих независимых копий той же самой системы. Закон больших чисел есть не что иное, как частный случай эргодической теоремы Биркгофа. Интерполяция и предсказание поведения стационарных гауссовских процессов, понимаемых в широком смысле, служат важным обобщением классической теории наименьших квадратов. Теория стационарных процессов – необходимое орудие исследования во многих областях, например, в теории связи, которая занимается изучением и созданием систем, передающих сообщения при наличии шума или случайных помех.