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

Содержание

 

Введение

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

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

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

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

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

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

Заключение

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

Введение

 

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

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

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

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

 

Цепь Маркова

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

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

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

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

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

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

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

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

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

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

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

 

Равенство Маркова

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

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

 

 

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

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

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

 

. (1)

 

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

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

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

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

 

 ()

 

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

 

 

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

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

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

 

,

 

Получим

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

,

 

Или

 

 (2)

 

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

 

 

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

 

 

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

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

 

 (3)

 

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

 (4)

 

Из равенств

 

и

 

следует

 

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

 

 

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

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

 

 (5)

 

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

 

 (6)

 

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

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

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

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

 

.

 

Заключение

 

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

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

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

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

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

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

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

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

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

 

Содержание

 

Введение

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

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

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

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

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

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

Заключение

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

Введение

 

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

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

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

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

 

Цепь Маркова

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

 

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

 

 

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

 

 

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

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

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

 

 

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

S1

0,2 0,7

S2 0,4 S4

0,6 0,5

0,1 0,5

S3

 

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

 

Равенство Маркова

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

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

 

 

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

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

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

 

. (1)

 

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

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

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

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

 

 ()

 

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

 

 

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

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

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

 

,

 

Получим

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

,

 

Или

 

 (2)

 

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

 

 

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

 

 

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

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

 

 (3)

 

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

 (4)

 

Из равенств

 

и

 

следует

 

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

 

 

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

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

 

 (5)

 

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

 

 (6)

 

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

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

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

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

 

.