Цепи Маркова

Цепи Маркова

Содержание
Введение
§ 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)
где />вероятности перехода.
Если в цепи Маркова /> то при любом />
/> />
Это утверждение следует по индукции из (7) и (8).
Приведем формулировку теоремы о предельных вероятностях для одноговажного класса цепей Маркова.
Теорема 1. Если при некотором />>0 всеэлементы матрица /> положительны, то для любых />, при />
/>, (9)
 
где /> стационарное распределение с /> /> /> а />некоторая постоянная,удовлетворяющая неравенством 0h
Так как /> , то по условию теоремы из любогосостояния можно попасть в любое за время /> с положительной вероятностью.Условия теоремы исключает цепи, являющиеся в некотором смысле периодическими.
Если выполнить условие теоремы 1, то вероятность того, что системанаходится в некотором состоянии />, в пределе не зависит отначального распределение. Действительно, из (9) и (7) следует, что при любомначальном распределении /> , />
/>/> />
Рассмотрим несколько примеров цепи Маркова, которых условиятеоремы 1, не выполнены. Нетрудно проверить, что такими примерами являетсяпримеры. В примере /> вероятности перехода имеютприделы, но эти приделы зависят от начального состояния. В частности, при />

/> 0, />/>
/> />
/>
В других примеров приделы вероятностей /> /> при /> очевидно, не существуют.
Найдем стационарное распределение в примере 1. Нужно найти вектор /> удовлетворяющийусловиям (8):
/> />,
/>,
/>;
/> /> />
Отсюда, /> /> Таким образом, стационарное распределениесуществует, но не все координаты векторы /> положительны.
Для полиномиальной схемы были введены случайные величины, равныечесу исходов данного типа. Введем аналогичные величины для цепей Маркова. Пусть/> /> − числопопадания системы в состояние /> за время />. Тогда /> частота попаданий системы всостояние />.Используя формулы (9), можно доказать, что /> при /> сближается с />. Для этого нужнополучить асимптотические формулы для /> и /> и воспользоваться неравенствомЧебышева. Приведем вывод формулы для />. Представим /> в виде
/> (10)
где />, если />, и /> в противном случае. Так как
/>,
то, воспользовавшись свойством математического ожидания и формулой(9), получим
/>.
Втрое слагаемое в правой части этого равенства в силу теоремы 1является частной суммой сходящегося ряда. Положив />, получим
/> /> (11)
Поскольку
/> />
Из формулы (11), в частности, следует, что
/>/> /> при />

Так же можно получить формулу для /> которая используется длявычисления дисперсии.
§5. Доказательство теоремы о предельных вероятностяхв цепи Маркова
 
Докажем сначала две леммы. Положим
/> />
 
Лемма 1. При любых /> существуют пределы
 
/> /> и />/>
Доказательство. Используя уравнение (3) с /> получим
/>
/>
Таким образом, последовательности /> и /> монотонны и ограничены. Отсюдаследует утверждение леммы 1.
Лемма 2. Если выполнены условиятеоремы 2, то существуют постоянные />, /> /> такие, что
/> />
Для любых />

/>/>
где /> , /> означает суммирование по всем />, при которых /> положительно,а />суммированиепо остальным />. Отсюда
/>. (12)
Так как в условиях теоремы 1 вероятности перехода /> при всех />, то при любых />
/> (13)
И в силу конечности числа состояний
/> (14)
Оценим теперь разность />. Используя уравнение (3) с />, />, получим
/>
=/>
/>.

Отсюда, используя (8)-(10), найдем
/>/>
=/>.
Объединяя это соотношение с неравенством (14), получимутверждение леммы.
Перейти к доказательству теоремы. Так как последовательности />, /> монотонны, то
0. (15)
Отсюда и из леммы 1 находим
/>
Следовательно, при /> получи /> и
/> (16)
Положительность /> следует из неравенства (15).Переходя к пределу при /> и /> в уравнении (3), получим, что /> удовлетворяетуравнению (12). Теорема доказана.

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

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

Список использованной литературы
 
1. Чистяков В.П. Курс теории вероятностей. 6-е изд., испр. −СПб.: Издательство «Лань», 2003. − 272 с. − (Учебник для вузов.Специальная литература).
2. Гнеденко Б.В. Курс теории вероятностей.
3. Гмурман В.Е. Теория вероятностей и математическая статистика.
4. Вентцель Е.С. Теория вероятностей и ее инженерные приложения.
5. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Введение в теориювероятностей. − Москва-Ижевск: Институт компьютерных исследований, 2003,188 стр.
6. Кац М. Вероятность и смежные вопросы в физике.