Марковские цепи. Однородные цепи маркова Граф марковской цепи

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

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

Любой марковский процесс описывают с помощью вероятностей состояний и переходных вероятностей.

Вероятности состояний P k (t) марковского процесса – это вероятности того, что случайный процесс (система) в момент времени t находится в состоянии S k:

Переходные вероятности марковского процесса – это вероятности перехода процесса (системы) из одного состояния в другое:

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

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

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

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

Переходные вероятности цепи Маркова за один шаг записывают в виде матрицы P=||P ij ||, которую называют матрицей вероятностей перехода или просто переходной матрицей.

Пример: множество состояний студентов специальности следующие:

S 1 – первокурсник;

S 2 – второкурсник …;

S 5 – студент 5 курса;

S 6 –специалист, окончивший вуз;

S 7 – человек, обучавшийся в вузе, но не окончивший его.

Из состояния S 1 за год возможны переходы в состояние S 2 с вероятностью r 1 ; S 1 с вероятностью q 1 и S 7 с вероятностью p 1 , причем:

r 1 +q 1 +p 1 =1.

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

Составим матрицу вероятностей переходов:

Переходные матрицы обладают свойством:

Все их элементы неотрицательны;

Их суммы по строкам равны единице.

Матрицы с таким свойством называют стохастическими.

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

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

При изучении цепей Маркова наибольший интерес представляют:

Вероятности перехода за m шагов;

Распределение по состояниям на шаге m→∞;

Среднее время пребывания в определенном состоянии;

Среднее время возвращения в это состояние.

Рассмотрим однородную цепь Маркова с n состояниями. Для получения вероятности перехода из состояния S i в состояние S j за m шагов в соответствии с формулой полной вероятности следует просуммировать произведения вероятности перехода из состояния Siв промежуточное состояние Sk за l шагов на вероятность перехода из Sk в Sj за оставшиеся m-l шагов, т.е.

Это соотношение для всех i=1, …, n; j=1, …,n можно представить как произведение матриц:

P(m)=P(l)*P(m-l).

Таким образом, имеем:

P(2)=P(1)*P(1)=P 2

P(3)=P(2)*P(1)=P(1)*P(2)=P 3 и т.д.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=P m ,

что дает возможность найти вероятности перехода между состояниями за любое число шагов, зная матрицу переходов за один шаг, а именно P ij (m) – элемент матрицы P(m) есть вероятность перейти из состояния S i в состояние S j за m шагов.

Пример : Погода в некотором регионе через длительные периоды времени становится то дождливой, то сухой. Если идет дождь, то с вероятностью 0,7 он будет идти на следующий день; если в какой-то день сухая погода, то с вероятностью 0,6 она сохраниться и на следующий день. Известно, что в среду погода была дождливая. Какова вероятность того, что она будет дождливой в ближайшую пятницу?

Запишем все состояния цепи Маркова в данной задаче: Д – дождливая погода, С – сухая погода.

Построим граф состояний:

Ответ: р 11 =р(Д пят |Д ср) =0,61.

Пределы вероятностей р 1 (m), р 2 (m),…, р n (m) при m→∞, если они существуют, называются предельными вероятностями состояний .

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

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

Вектор р, составленный из предельных вероятностей, должен удовлетворять соотношению: р=p*P.

Среднее время пребывания в состоянии S i за время T равно p i *T, где p i - предельная вероятность состояния S i . Среднее время возвращения в состояние S i равно .

Пример.

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

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

p 11 =0,2; p 12 =0,4; p 13 =0,4; p 14 =0;

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

твертую, т.е.

в четвертую, т.е.

p 41 =0; p 42 =0,4; p 43 =0,5; p 44 =0,1;

в) из второй в другие градации могут быть только реже: в первую - в два раза, в третью на 25%, в четвертую - в четыре раза реже, чем переход во вторую, т.е.

p 21 =0,2;p 22 =0,4; p 23 =0,3; p 24 =0,1;

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

p 31 =0,1; p 32 =0,4; p 33 =0,4; p 34 =0,1;

Построим граф:

Составим матрицу вероятностей перехода:

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

Откуда p 4 =0.08; p 3 =; p 2 =; p 1 =0.15

Периодичность возвращения в состояние S i равна .

Следовательно, периодичность засушливых лет в среднем равна 6.85, т.е. 6-7 лет, а дождливых 12 лет.

Маркова цепь (Markov Chain) - марковский процесс с дискретным временем, заданный в измеримом пространстве.

Введение

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

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

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

Простой пример: бросание монеты

Прежде чем дать описание общей схемы, обратимся к простому примеру. Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ...

При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные значения j = k ± 1 c одинаковой вероятностью 1/2.

Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.

Формулы и определения

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

Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.

Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е. P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n.

Ясно, что P ij - квадратная матрица с неотрицательными элементами и единичными суммами по строкам.

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

На практике: доставка оборудования по округам

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

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

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

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

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

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

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

Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С.

Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1.

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

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

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

2) С-->B и B-->B;

3) С-->A и A-->B.

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

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

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

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

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

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

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

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

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

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).

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

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

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

Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Цепи Маркова

Введение

§ 1. Цепь Маркова

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

§3. Равенство Маркова

§4. Стационарное распределение. Теорема о предельных вероятностях

§5. Доказательство теоремы о предельных вероятностях в цепи Маркова

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

Заключение

Список использованной литературы

Введение

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

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

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

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

§1. Цепь Маркова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

§3. Равенство Маркова

Определение. Обозначим через вероятность того, что в результате шагов (испытаний) система перейдет из состояния в состояние . Например, – вероятность перехода за 10 шагов из второго состояния в пятое.

Подчеркнем, что при получим переходные вероятности

Поставим перед собой задачу: зная переходные вероятности найти вероятности перехода системы из состояния в состояние за шагов.

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

По формуле полной вероятности, получим

. (1)

Эту формулу называют равенством Маркова.

Пояснение. Введем обозначения:

– интересующее нас событие (за шагов система перейдет из начального состояния в конечное ), следовательно, ; − гипотезы(за шагов система перейдет из первоначального состояния в промежуточное состояние ), следовательно, − условная вероятность наступления при условии, что имела место гипотеза (за шагов система перейдет из промежуточного состояния в конечное ), следовательно,

По формуле полной вероятности,

()

Или в принятых нами обозначениях

что совпадает с формулой Маркова (1).

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

Действительно, положив в равенстве Маркова

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

(2)

Таким образом, по формуле (2) можно найти все вероятности следовательно, и саму матрицу . Поскольку непосредственное использование формулы (2) оказывается утомительным, а матричное исчисление ведет к цели быстрее, напишу вытекающие из (2) соотношение в матричной форме:

Положив в (1), аналогично получим

В общем случае

Теорема 1. При любых s, t

(3)

Доказательство. Вычислим вероятность по формуле полной вероятности (), положив

Из равенств

Отсюда из равенств (4) и

получим утверждение теоремы.

Определим матрицу В матричной записи (3) имеет вид

Так как то где − матрица вероятности перехода. Из (5) следует

(6)

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

Пример 1. Задана матрица перехода Найти матрицу перехода

Решение. Воспользуемся формулой

Перемножив матрицы, окончательно получим:

§4. Стационарное распределение. Теорема о предельных вероятностях

Распределение вероятностей в произвольной момент времени можно найти, воспользовавшись формулой полной вероятности

(7)

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

где вероятности перехода.

Если в цепи Маркова то при любом

Это утверждение следует по индукции из (7) и (8).

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

Теорема 1. Если при некотором >0 все элементы матрица положительны, то для любых , при

, (9)

где стационарное распределение с а некоторая постоянная, удовлетворяющая неравенством 0< h <1.

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

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

Рассмотрим несколько примеров цепи Маркова, которых условия теоремы 1, не выполнены. Нетрудно проверить, что такими примерами является примеры. В примере вероятности перехода имеют приделы, но эти приделы зависят от начального состояния. В частности, при

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

Найдем стационарное распределение в примере 1. Нужно найти вектор удовлетворяющий условиям (8):

;

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

Для полиномиальной схемы были введены случайные величины, равные чесу исходов данного типа. Введем аналогичные величины для цепей Маркова. Пусть − число попадания системы в состояние за время . Тогда частота попаданий системы в состояние . Используя формулы (9), можно доказать, что при сближается с . Для этого нужно получить асимптотические формулы для и и воспользоваться неравенством Чебышева. Приведем вывод формулы для . Представим в виде

(10)

где , если , и в противном случае. Так как

то, воспользовавшись свойством математического ожидания и формулой (9), получим

Втрое слагаемое в правой части этого равенства в силу теоремы 1 является частной суммой сходящегося ряда. Положив , получим

Поскольку

Из формулы (11), в частности, следует, что

при

Так же можно получить формулу для которая используется для вычисления дисперсии.

§5. Доказательство теоремы о предельных вероятностях в цепи Маркова

Докажем сначала две леммы. Положим

Лемма 1. При любых существуют пределы

Доказательство. Используя уравнение (3) с получим

Таким образом, последовательности и монотонны и ограничены. Отсюда следует утверждение леммы 1.

Лемма 2. Если выполнены условия теоремы 2, то существуют постоянные , такие, что

Для любых

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

. (12)

Так как в условиях теоремы 1 вероятности перехода при всех , то при любых

И в силу конечности числа состояний

Оценим теперь разность . Используя уравнение (3) с , , получим

Отсюда, используя (8)-(10), найдем

Объединяя это соотношение с неравенством (14) , получим утверждение леммы.

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

0<. (15)

Отсюда и из леммы 1 находим

Следовательно, при получи и

Положительность следует из неравенства (15). Переходя к пределу при и в уравнении (3), получим, что удовлетворяет уравнению (12). Теорема доказана.

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

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

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

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

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

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

Также цепь Маркова можно использовать для генерации текстов. На вход подается несколько текстов, затем строится цепь Маркова с вероятностями следования одних слов за другими и на основе данной цепи создается результирующий текст. Игрушка получается весьма занятной!

Заключение

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

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

Список использованной литературы

1. Чистяков В.П. Курс теории вероятностей. 6-е изд., испр. − СПб.: Издательство «Лань», 2003. − 272 с. − (Учебник для вузов. Специальная литература).

2. Гнеденко Б.В. Курс теории вероятностей.

3. Гмурман В.Е. Теория вероятностей и математическая статистика.

4. Вентцель Е.С. Теория вероятностей и ее инженерные приложения.

5. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Введение в теорию вероятностей. − Москва-Ижевск: Институт компьютерных исследований, 2003, 188 стр.

6. Кац М. Вероятность и смежные вопросы в физике.

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

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью . Для такого процесса моменты t 1 , t 2 , когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t , а номер шага 1, 2, k , Случайный процесс в этом случае характеризуется последовательностью состояний S(0) , S(1) , S(2) , S(k) , где S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы после первого шага; S(k) - состояние системы после k -го шага...

Событие {S(k) = S i }, состоящее в том, что сразу после k -го шага система находится в состоянии S i (i = 1, 2,), является случайным событием. Последовательность состояний S(0) , S(1) , S(k) , можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью , если для каждого шага вероятность перехода из любого состояния S i в любое S j не зависит от того, когда и как система пришла в состояние S i . Начальное состояние S(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятности P i (k) того, что после k -го шага (и до (k + 1)-го) система S будет находиться в состоянии S i (i = 1, 2, n ). Очевидно, для любою k .

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

P 1 (0), P 2 (0), P i (0), P n (0).

В частном случае, если начальное состояние системы S в точности известно S(0) = S i , то начальная вероятность Р i (0) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система S после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шага) она находилась в состоянии S i .

Поскольку система может пребывать в одном из n состояний, то для каждого момента времени t необходимо задать n 2 вероятностей перехода P ij , которые удобно представить в виде следующей матрицы:

где Р ij - вероятность перехода за один шаг из состояния S i в состояние S j ;

Р ii - вероятность задержки системы в состоянии S i .

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

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

Переходные вероятности однородной Марковской цепи Р ij образуют квадратную матрицу размера n m .

Отметим некоторые ее особенности:

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из i -го) состояния, в том числе и переход в самое себя.

2. Элементы столбцов показывают вероятности всех возможных переходов системы за один шаг в заданное (j -е) состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец - в состояние).

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

4. По главной диагонали матрицы переходных вероятностей стоят вероятности Р ii того, что система не выйдет из состояния S i , а останется в нем.

Если для однородной Марковской цепи заданы начальное распределение вероятностей и матрица переходных вероятностей , то вероятности состояний системы P i (k) (i, j = 1, 2, n ) определяются по рекуррентной формуле:

Пример 1. Рассмотрим процесс функционирования системы - автомобиль. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (S 1 ) и неисправном (S 2 ). Граф состояний системы представлен на рис. 3.2.

Рис. 3.2.Граф состояний автомобиля

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

где P 11 = 0,8 - вероятность того, что автомобиль останется в исправном состоянии;

P 12 = 0,2 - вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

P 21 = 0,9 - вероятность перехода автомобиля из состояния «неисправен» в состояние «исправен»;

P 22 = 0,1 - вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан , т.е. Р 1 (0) = 0 и Р 2 (0) =1.

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

Используя матрицу переходных вероятностей и формулу (3.1), определим вероятности состояний P i (k) после первого шага (после первых суток):

P 1 (1) = P 1 (0)×P 11 + P 2 (0)×P 21 = 0?0,8 + 1?0,9 = 0,9;

P 2 (1) = P 1 (0)×P 12 + P 2 (0)×P 22 = 0?0,2 + 1?0,1 = 0,2.

Вероятности состояний после второго шага (после вторых суток) таковы:

P 1 (2) = P 1 (1)×P 11 + P 2 (1)×P 21 = 0,9×0,8 + 0,1×0,9 = 0,81;

= 0,9×0,2 + 0,1×0,1 = 0,19.

Вероятности состояний после третьего шага (после третьих суток) равны:

P 1 (3) = P 1 (2)×P 11 + P 2 (2)×P 21 = 0,81×0,8 + 0,19×0,9 = 0,819;

= 0,81×0,2 + 0,19×0,1 = 0,181.

Таким образом, после третьих суток автомобиль будет находиться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

Пример 2. В процессе эксплуатации ЭВМ может рассматриваться как физическая система S , которая в результате проверки может оказаться в одном из следующих состояний: S 1 - ЭВМ полностью исправна; S 2 - ЭВМ имеет неисправности в оперативной памяти, при которых она может решать задачи; S 3 - ЭВМ имеет существенные неисправности и может решать ограниченный класс задач; S 4 - ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние S 1 ). Проверка ЭВМ производится в фиксированные моменты времени t 1 , t 2 , t 3 . Процесс, протекающий в системе S , может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид

Определить вероятности состояний ЭВМ после трех проверок.

Решение . Граф состояний имеет вид, показанный на рис. 3.3. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний P 1 (0) = 1, P 2 (0) = P 3 (0) = P 4 (0) = 0.

Рис. 3.3. Граф состояний ЭВМ

По формуле (3.1), учитывая в сумме вероятностей только те состояния, из которых возможен непосредственный переход в данное состояние, находим:

P 1 (1) = P 1 (0)×P 11 = 1×0,3 = 0,3;

P 2 (1) = P 1 (0)×P 12 = 1×0,4 = 0,4;

P 3 (1) = P 1 (0)×P 13 = 1×0,1 = 0,1;

P 4 (1) = P 1 (0)×P 14 = 1×0,2 = 0,2;

P 1 (2) = P 1 (1)×P 11 = 0,3×0,3 = 0,09;

P 2 (2) = P 1 (1)×P 12 + P 2 (1)×P 22 = 0,3×0,4 + 0,4×0,2 = 0,20;

P 3 (2) = P 1 (1)×P 13 + P 2 (1)×P 23 + P 3 (1)×P 33 = 0,27;

P 4 (2) = P 1 (1)×P 14 + P 2 (1)×P 24 + P 3 (1)×P 34 + P 4 (1)×P 44 = 0,44;

P 1 (3) = P 1 (2)×P 11 = 0,09×0,3 = 0,027;

P 2 (3) = P 1 (2)×P 12 + P 2 (2)×P 22 = 0,09×0,4 + 0,20×0,2 = 0,076;

P 3 (3) = P 1 (2)×P 13 + P 2 (2)×P 23 + P 3 (2)×P 33 = 0,217;

P 4 (3) = P 1 (2)×P 14 + P 2 (2)×P 24 + P 3 (2)×P 34 + P 4 (2)×P 44 = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок следующие: P 1 (3) = 0,027; P 2 (3) = 0,076; P 3 (3) = 0,217; P 4 (3) = 0,680.

Задача 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t 1 , t 2 , t 3 , t 4 .

Возможные состояния системы: S 1 - цель невредима; S 2 - цель незначительно повреждена; S 3 - цель получила значительные повреждения; S 4 - цель полностью поражена. В начальный момент времени цель находится в состоянии S 1 . Определить вероятности состояний цели после четырех выстрелов если матрица переходных вероятностей имеет вид.