Цепи Маркова

Содержание


Введение

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

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

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

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

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

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

Заключение

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


Введение


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

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

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

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


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


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

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

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

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

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

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

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

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

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

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

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


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


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

Пример 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


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


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


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

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


Цепи Маркова


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

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

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


Цепи Маркова. (1)


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

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

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

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


Цепи Маркова (Цепи Маркова)


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


Цепи Маркова


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

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

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


Цепи Маркова,


Получим

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

Цепи Маркова,


Или


Цепи Маркова (2)


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


Цепи Маркова


Положив Цепи Маркова в (1), аналогично получим


Цепи Маркова


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

Цепи Маркова

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


Цепи Маркова Цепи Маркова (3)


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

Цепи Маркова (4)


Из равенств


Цепи Маркова

и Цепи Маркова Цепи Маркова


следует

Цепи Маркова


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


Цепи Маркова Цепи Маркова


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

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


Цепи Маркова (5)


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


Цепи Маркова (6)


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

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

Решение. Воспользуемся формулой Цепи Маркова

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


Цепи Маркова.


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


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


Цепи Маркова (7)


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


Цепи Маркова, Цепи Маркова

Цепи Маркова Цепи Маркова Цепи Маркова (8)


где

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

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

Похожие рефераты: