Цепи Маркова в теории вероятности и их приложения - Математика курсовая работа

Главная

Математика
Цепи Маркова в теории вероятности и их приложения

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
"МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ИМЕНИЕ М.Е. ЕВСЕВЬЕВА"
ЦЕПИ МАРКОВА В ТЕОРИИ ВЕРОЯТНОСТИ И ИХ ПРИЛОЖЕНИЯ
1. Основные понятия теории марковских цепей
2. Возвратные и невозвратные состояния
Марковские случайные процессы названы по имени выдающегося русского математика А.А.Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях.
Благодаря сравнительной простоте и наглядности математического аппарата, высокой достоверности и точности получаемых решений, особое внимание марковские процессы приобрели у специалистов, занимающихся исследованием операций и теорией принятия оптимальных решений.
Марковские цепи используются в теории массового обслуживания для расчета распределения вероятностей числа занятых приборов в системе, состоящей из n приборов с пауссоновским потоком требований и показательным законом времени обслуживания.
Цепь Маркова, используется и в качестве математической модели при изучении поведения определенных стохастических систем. Для коротких отрезков времени можно использовать вычисления абсолютных вероятностей . Когда же число переходов неограниченно возрастает (больше k), необходимы иные методы анализа поведения системы.
В неприводимой цепи Маркова, любое состояние Sj может быть достигнуто из любого другого состояния Si за конечное число переходов, т. е. , где , в такой цепи все состояния будут сообщающимися. Все состояния неприводимой Марковской цепи образуют замкнутое множество состояний и никакое его подмножество состояний не может быть замкнутым.
Данная курсовая работа рассматривает цепи Маркова в теории вероятностей и их приложения. Объект исследования: цепи Маркова. Цель исследования: изучить Марковкие цепи, их виды, состояния. Задачи исследования: рассмотреть задачи, решаемые с использованием цепей Маркова.
марковский цепь вероятность невозвратный
1. Основные понятия теории марковских цепей
Условно будем говорить о некоторой физической системе, шаг за шагом меняющей свое фазовое состояние. Будем считать, что имеется лишь конечное или счетное число различных фазовых состояний е 1 , е 2 , ... Обозначим о (п) состояние системы через п шагов. Будем предполагать, что цепочка последовательных переходов
зависит от вмешательства случая, причем соблюдается следующая закономерность: если на каком-либо шаге п система находится в состоянии е i , то, независимо от предшествующих обстоятельств, она на следующем шаге с вероятностью p ij переходит в состояние е j
p ij = Р{ о (n+1) = е i / о (п) = е j }, i, j =1, 2, ... (2.1)
Описанная выше модель называется однородной цепью Маркова, а вероятности р ij называются переходными вероятностями этой цепи. Кроме них, еше задается начальное распределение вероятностей
p o i = P{о (0) = е i }, i=1, 2, ... (2.2)
Какова вероятность того, что система через п шагов будет находиться в состоянии е j ?
Обозначим эту вероятность p j (n) :
Через п -- 1 шагов система обязательно будет находиться в одном из состояний е k , k = 1, 2, ..., причем в е k она будет с вероятностью, обозначенной р к (п -- 1). При условии, что через п--1 шагов система будет находиться в состоянии е k , вероятность оказаться через п шагов в состоянии е j равна вероятности р kj перехода из е k в е j . Используя формулу полной вероятности, получаем, что
Это дает следующие рекуррентные соотношения для вероятностей р j (п), j=1, 2, ...:
Если в начальный момент система находится в определенном состоянии е i , то начальное распределение вероятностей таково, что р 0 i = 1, p 0 k = 0 для k ? i а вероятность p i (n) совпадает с вероятностью p ij (n) того, что система из состояния е i за п шагов перейдет в состояние е j .
p ij (n) = Р{о(п) = е j /о(0) =е i }, i, j = 1, 2, ... (2.6)
При начальном распределении вида р 0 i =1, р 0 k = 0 для k ? i формула (2.5) дает следующие соотношения между переходными вероятностями p ij (n); i,j =1, 2,... :
Удобно ввести матрицу Р(п) = { p ij (n)}. Согласно формуле (2.7)
Р(0)= I, Р(1) = Р, Р(2) =Р(1) Р = P 2 , ...,
где I -- единичная матрица, Р = {p ij } ? матрица переходных вероятностей. Видно, что имеет место следующее равенство:
Задача о стопке книг. На письменном столе лежит стопка из m книг. Если обозначить каждую книгу соответствующим номером, то порядок их расположения сверху вниз можно описать перестановкой из т чисел (i 1 , i 2 , … … i m ), где i 1 -- номер книги, лежащей сверху, i 2 -- номер следующей книги, ..., i т --номер последней книги, лежащей в самом низу. Предположим, что каждая книга, берется с определенной вероятностью, скажем, книга с номером k берется с вероятностью р k (к=1, ..., m), причем при возвращении она кладется сверху.
Возьмем произвольное состояние (i 1 , i 2 , …, i m ). На следующем шаге оно либо остается неизменным, что происходит с вероятностью при выборе лежащей сверху книги с номером i 1 либо меняется на одно из m -- 1 состояний вида (i k , i 1 , ...), что происходит с вероятностью при выборе книги с номером i k . Перед нами цепь Маркова с состояниями, каждое из которых описывается соответствующей перестановкой (i 1 , i 2 , … … i m ), и указанными переходными вероятностями.
Остановимся на случае т = 2. Тогда имеется лишь два состояния: е 1 =(1,2) и е 2 = (2, 1). Переходные вероятности имеют вид:
и матрица переходных вероятностей есть
Вероятности перехода за два шага суть
p 11 (2)=p 21 (2)=p 1 p 1 +p 2 p 1 =p 1 (p 1 +p 2 )=p 1,
p 12 (2)=p 22 (2)= p 1 p 2 +p 2 p 2 =p 2 (p 1 +p 2 )=p 2 .
Видно, что Р 2 = Р и вообще Р n = Р. При любом начальном распределении вероятностей имеем (n =1, 2, ...)
p 1 (n)= p 11 (n)+p 21 (n)=p 1 (+)=p 1,
p 2 (n)= p 12 (n)+p 2 (n)=p 2 (+)=p 2 .
Задача о наилучшем выборе. Положим о 0 (0)=1 и обозначим: о(1) -- порядковый номер первого предмета, оказавшегося наилучшим среди всех осмотренных ранее; о(2)--порядковый номер следующего наилучшего среди всех осмотренных до него предметов и т. д. Цепочка о(0)>о(1)>о(2)... обрывается на некотором н-м шаге, если предмет с порядковым номером о(н) оказывается абсолютно наилучшим, так что и среди не осмотренных еще предметов нет лучшего. Число н является случайным, поскольку случайным является сам порядок осмотра. Введем состояния е 1 , е 2 , …е m , е m +1 , охарактеризовав их следующим образом: е i при i=1, …, т означает, что предмет с порядковым номером i (т. е. i-й по счету осмотренный предмет) является наилучшим среди всех ранее осмотренных; е m +1 означает, что уже осмотрен абсолютно наилучший предмет. Если положить о(n) = е m +1 , при всех п>н, то последовательность о(0)>о(1)>о(2)... образует цепь Маркова.
Найдем соответствующие переходные вероятности р ij Очевидно, р ij =0 при i?j, j?m, а p m +1, m +1 =1. Подсчитаем вероятности p ij при iо(1)>о(2)... будет цепью Маркова с переходными вероятностями вида
Рассмотрим случайное блуждание другого типа. Частица блуждает лишь по целым неотрицательным точкам, причем из точки i она с вероятностью р i переходит на следующем шаге в соседнюю точку i+1, а с вероятностью q i =1 - p i возвращается в нулевое положение. Соответствующие переходные вероятности суть
2. Возвратные и невозвратные состояния
Рассмотрим цепь Маркова с состояниями е 1 , е 2 , … и переходными вероятностями р ij , i, j=1, 2, … Пусть в начальный момент система находится в состоянии е i . Временно положим u n =p ij (n) и обозначим х n вероятность того, что через п шагов система впервые вернется в исходное состояние е i . Имеет место следующее равенство:
и п = u 0 х n + u 1 х n -1 + … + u n -1 х 1 + u n х 0, n=1, 2, …,
где дополнительно введены u 0 = 1 и х 0 = 0.
Оно является следствием общей формулы полной вероятности. Именно, если ввести события В k --"система через k шагов впервые возвращается в исходное состояние е i ", k = 1, …, п, и событие В п+1 --"система ни разу не побывает в состоянии е i в течение первых п шагов", то В 1 , ..., B n +1 будет полной системой событий, и вероятность события А -- "система через п шагов будет находиться в исходном состоянии е i " -- по формуле полной вероятности есть
P(B k )=х k ; P(A|B k )=u n - k , k=1, …, n; P(A|B n +1 )=0.
Если обратиться к производящим функциям
то отношение (8.8), справедливое при всех п= 1, 2,... , можно записать в виде
есть вероятность того, что система рано или поздно попадет в исходное состояние е i , иначе х есть вероятность возвращения в е i . Состояние е i называется возвратным, если вероятность возвращения в него равна 1, и невозвратным, если вероятность эта меньше 1.
Теорема. Состояние е i является возвратным тогда и только тогда, когда
Доказательство. Возвратность состояния е i означает, что
Это предельное соотношение равносильно тому, что
Таким образом, возвратность состояния е i равносильна тому, что ряд расходится. Для завершения доказательства остается лишь напомнить, что и п = р ii (п).
Теорема. Если исходное состояние е i является возвратным, то система с вероятностью 1 за бесконечное число шагов бесконечно много раз возвратится в е i . Если это состояние является невозвратным, то за бесконечное число шагов система с вероятностью 1 лишь конечное число раз побывает в состоянии е i , другими словами, после некоторого конечного числа шагов она никогда больше не возвращается в е i .
Доказательство. Обозначим н 1 -- число шагов до первого возвращения в состояние е i , н 2 -- число шагов до второго возвращения и т. д. Если за бесконечное числа шагов происходит меньше k возвращений, то полагаем н k =?. Событие {н k < ?} означает, что произошло по меньшей мере k возвращений. Вероятность возвращения есть
При условии осуществления события {н 1 < ?} система через некоторое конечное число шагов н 1 возвращается в исходное состояние е i , после чего ее дальнейшее поведение подчиняется тем же закономерностям, как если бы она только начинала свое движение. Таким образом, вероятность события {н 2 < ?} при условии, что {н 1 < ?}, будет равна х:
Очевидно, если н 1 =?, то также и н 2 =?. Поэтому
Невозвратность состояния е i означает, что х<1. В этом случае
и, согласно первой лемме Бореля -- Кантелли, с вероятностью 1 может произойти лишь конечное число событий вида {н k < ?}, т. е. с вероятностью 1 за бесконечное число шагов система лишь конечное число раз побывает в состоянии е i .
Возвратность состояния е i означает, что х=1. В этом случае при любом k
Обозначим х число возвращений за бесконечное число шагов. Очевидно, событие {х ? k} тождественно с событием {н k < ?}, так что, если P{н k < ?} =1 при всех k, то с вероятностью 1 величина x превосходит любое наперед заданное число k. Это значит, что
Говорят, что состояние е j достижимо из е i , если за некоторое число шагов система с положительной вероятностью переходит из е i в е j т. е. p ij (M)>0 при некотором М.
Пусть е i -- возвратное состояние е j достижимо из е i . Тогда е i в свою очередь достижимо из е j , так как в противном случае, выходя из е i система за М шагов с положительной вероятностью р ij (М)=б>0 попадает в состояние е j , после чего уже не может вернуться в е i ; таким образом, вероятность возвращения в е i будет не больше, чем 1--б, а это противоречит возвратности е i . Итак, если е j достижимо из возвратного состояния е i , то в свою очередь е i достижимо из е j , т. е. p ij (N)=в>0 при некотором N. Как следует из формулы (8.7), при любом п
Эти неравенства показывают, что ряды
сходятся или расходятся одновременно. Согласно условию (8.11), для возвратного состояния еi ряд расходится. Поэтому также и
Следовательно, состояние е j является возвратным. Мы пришли к следующему результату.
Теорема. Если состояние е j достижимо из возвратного состояния е i , то е j также является возвратным, причем е i в свою очередь достижимо из е j .
Следствие. Если цепь Маркова имеет лишь конечное число состояний, причем каждое из них достижимо из любого другого состояния, то все они являются возвратными.
Действительно, если имеется лишь конечное число состояний, то за бесконечное число шагов хотя бы в одном из них система обязательно побывает бесконечное число раз. Следовательно, хотя бы одно состояние является возвратным, а поскольку по условию из него можно с положительной вероятностью перейди в любое другое состояние, все они будут возвратными.
Задача о стопке книг. Очевидно, если каждая книга выбирается с положительной вероятностью, т. е. p i >0 при всех i=1,..., т, то любое состояние достижимо из каждого другого состояния. Всего имеется т! различных состояний (i 1 , …, i m ) и все они будут возвратными. Если p i = 0 при некотором i то все состояния вида(i 1 , …, i m ), где i 1 =i (книга с номером i лежит на самом верху), являются невозвратными, так как после первого же шага выбирается некоторая книга с номером j, отличным от i, и книга с номером i, никогда не вынимаемая из стопки, опускается ниже.
Задача о наилучшем выборе. Очевидно, через некоторое число шагов, не больше т (т -- число всех имеющихся предметов), система попадает в состояние е m +1 , в котором остается навсегда. Таким образом, все состояния, кроме е m + 1, являются невозвратными.
Случайные блуждания. Рассмотрим случайное блуждание, при котором частица из каждой целочисленной точки i на следующем шаге с вероятностью р переходит в соседнюю точку j=i - 1, а с вероятностью q -- в точку j=i - 1. Ясно, что каждое состояние достижимо из любого другого состояния и (см. формулу (6.0))
Используя формулу Стирлинга, при п>? получаем
причем знак равенства имеет место лишь при р = q=. Таким образом, при п>?
сходятся или расходятся одновременно. При р ? q, когда 4pq<1, ряд сходится, и следовательно, каждое состояние i является невозвратным. Интуитивно ясно, что, например, при р>q блуждающая частица постепенно будет уходить все дальше и дальше в положительном направлении, рано или поздно навсегда покидая любое фиксированное состояние i. При неограниченно продолжающемся симметричном случайном блуждании, когда р = q=, частица бесконечное число раз возвращается в каждое из состояний.
Рассмотрим теперь случайное блуждание, при котором частица из неотрицательной целой точки i на следующем шаге с вероятностью р i смещается в соседнюю точку j = i + 1, а с вероятностью q i = 1--р i переходит в нулевую точку j = 0. Очевидно, если все вероятности р i таковы, что 0