Справочник от Автор24
Теория вероятностей

Конспект лекции
«Дискретные цепи Маркова»

Справочник / Лекторий Справочник / Лекционные и методические материалы по теории вероятности / Дискретные цепи Маркова

Выбери формат для чтения

pdf

Конспект лекции по дисциплине «Дискретные цепи Маркова», pdf

Файл загружается

Файл загружается

Благодарим за ожидание, осталось немного.

Конспект лекции по дисциплине «Дискретные цепи Маркова». pdf

txt

Конспект лекции по дисциплине «Дискретные цепи Маркова», текстовый формат

Тема № 2 Дискретные цепи Маркова Пусть T   0 или T   , т.е. имеется последовательность случайных величин 0 , 1,..., n ,... , определенных на одном вероятностном пространстве , A, P . Пусть En - множество значений n , тогда E   En - множество состояний цепи n Маркова или фазовое пространство. Определение. Последовательность дискретных случайных величин  , n    n называется цепью Маркова, если при любых n   для всех l1  l2  ...  ln 1   0 и для любых i1, i2 ,..., in , in 1  E имеют место равенства:  P l n 1  in 1 | l  i1,,..., l n 1 1    in 1, l  in  P l n   in 1 | l  in , n 1 n если эти вероятности определены. Величина n – это дискретное время. Запись n  in означает «Цепь Маркова в момент времени n находится в состоянии in » По теореме об умножении вероятностей верно равенство P 0  i0,..., n  in   P0  i0  P1  i1 | 0  i0   P2  i2 | 1  i1, 0  i0 ...P n  in | 0  i0,..., n1  in1    P 0  i0  P 1  i1 | 0  i0 ...P n  in | n 1  in 1  . Назовем величину pij(n )  P n  j | n 1  i  переходной вероятность из i -го состояния в j -е за 1 шаг в момент времени n . Определение. Цепь Маркова называется однородной во времени, если ее переходные вероятности не зависят от n , т. е. pij(n )  pij для всех i, j  E ¸ в любой момент времени n . В дальнейшем мы будем рассматривать однородные цепи Маркова. Определение. Цепь Маркова - конечная, если фазовое пространство E – конечно (в противном случае цепь Маркова счетна). Обозначим  || pij ||NN , где N – мощность фазового пространства E , и назовем ее матрицей переходных вероятностей за 1 шаг. Обозначим через p вектор   p  P 0  i  ; i  E . Вектор p - распределение случайной величины 0 . Назовем вектор p начальным вектором (начальным распределением) цепи Маркова. Набор ( p ,П) полностью определяет однородную цепь Маркова. Обозначим через pij n   P l n  j | l  i  переходную вероятность из i – го состояния в j – е за n шагов. В силу однородности цепи Маркова величина pij n  не зависит от l . Введем матрицу переходных вероятностей за n шагов:  n  || pij n  ||N N . С помощью формулы полной вероятности докажите самостоятельно, что pij n    pik n  1 pkj . k E Это равенство называется уравнением Колмогорова – Чепмена. В матричном виде оно будет выглядеть следующим образом:  n    n  1  . Следовательно,  n   n для всех n   . 1, i  j Определим pij 0   , 0, i  j  1  0    .      1  0  0  EN N Очевидно, что выполняется равенство P n  j    i0 ,i1 ,...,in 1 E  P 0  i0  pi i pi i ...pi Определим вектор p n  P n  j ; j  E 01  12 n 1 j . – распределение цепи Маркова в момент времени n . Очевидно, что выполняется равенство Пример. 1. отрезка 1,N  , pn  p 0n  pn1 . Предположим, что некоторая частица, двигаясь по целочисленным точкам в дискретные моменты времени может совершать скачки влево или вправо на один шаг. Вероятность скачка вправо равна p  0 из любой внутренней точки k  2, N  1 , равна 1 из точки 1 и равна 0 из точки N . Вероятность скачка влево равна q  1  p  0 из любой внутренней точки k  2, N  1 , равна 0 из точки 1 и равна 1 из точки N . Пусть n - точка, характеризующая положение частицы в момент времени n   0 . Легко видеть, что последовательность n , n   0  образует цепь Маркова. Эта цепь называется случайным блужданием с отражающими экранами. В качестве левого и правого отражающих экрана выступают концевые точки отрезка 1 иN. Случайное блуждание с отражающими экранами как цепь Маркова n , n   0  имеет следующую матрицу переходных вероятностей: 1 2 3  N 1 N 1 0 1 0  2 p 0 q  3 0 p 0  0.        N 1 0 0 0  q N 0 0 0  1 2. Изменим свойства экранов в предыдущем примере. Пусть теперь из точки 1 можно произвести скачок вправо с вероятностью  , а с вероятностью 1   можно остаться в точке 1. Из точки N можно произвести скачок влево с вероятностью  , а с вероятностью 1   можно остаться в точке N . Остальные условия оставим без изменения. Последовательность n , n   0  так же образует цепь Маркова с матрицей переходных вероятностей: 1 2 3  N 1 N 1 1  0  2 p 0 q  3 p 0         N 1 0 0  q N 0 0   1 Если 0    1 , то это случайное блуждание с упругими экранами, а если   0 - это случайное блуждание с поглощающими экранами. Классификация состояний цепи Маркова Пусть E1, E 2 ,... - состояния цепи Маркова. Определение. Состояние E j называется несущественным, если найдется состояние Ek и натуральное число m такие, что pjk m   0 , но pkj n   0 при любых n   . В противном случае состояние E j - существенное. Пример. При случайном блуждании с поглощающими экранами состояния 1 и N существенные, а остальные – несущественные. При случайном блуждании с упругими и отражающими экранами все состояния существенны. Определение. Существенные состояния E j и Ek называются сообщающимися, если существуют m, n   такие, что pjk m   0 и pkj n   0 . Пример. При случайном блуждании с упругими и отражающими экранами все состояния существенные и сообщающиеся. Докажите самостоятельно, что отношение сообщаемости является отношением эквивалентности. Обозначим через S 0 класс несущественных состояний данной цепи Маркова. Существенные состояния разбиваются на непересекающиеся подклассы по отношению сообщаемости. Обозначим эти подклассы S 1 , S 2 и т.д. Перенумеруем состояния из фазового пространства так, чтобы первые номера были в S 0 , вторые – в S 1 и т. д. Для конечной цепи Маркова это можно сделать. В матрице переходных вероятностей переставятся строки и столбцы, и она приобретет вид: S 0 S1 S2  S0     S1  . S2        Через  мы обозначили те клетки, в которых могут быть ненулевые элементы. Пример. При случайном блуждании с поглощающими экранами S  2,..., N  1  2, N  1 , S  1 , 1 S  N  . 2 Если в матрице класс переходных вероятностей переставятся строки и столбцы, то она приобретет вид 2 3  N 1 1 N 2 0 q  p 0 3 p 0  0 0        N 1 0 0  0 q 1 0 0  1 0 N 0 0  0 1 Определение. Если какой-либо класс сообщающихся состояний состоит из одного состояния, то оно называется поглощающим состоянием. Пример. При случайном блуждании с поглощающими экранами состояния 1 и N поглощающие. Определение. Во введенных выше обозначениях классы S 1, S 2 ,... называются эргодическими подклассами существенных состояний, S 0 – классом несущественных состояний. Определение. Если все фазовое пространство цепи Маркова составляет один эргодический подкласс сообщающихся состояний, то эта цепь называется неприводимой или неразложимой. Пример. При случайном блуждании с упругими или отражающими экранами цепи Маркова являются неприводимыми. Определение. Существенное состояние E j называется периодическим с периодом d j , если d j - это наибольший общий делитель всех таких натуральных n , что pjj n   0 . 1,N  , в   дискретные моменты времени может совершать скачки вправо на один шаг, если она Пример. Пусть некоторая частица, двигаясь по целочисленным точкам отрезка находилась в точке k  1, N  1 , а из состояния N она совершает скачок в 1. Пусть n точка, характеризующая положение частицы в момент времени n   0 . Легко видеть, что последовательность  , n    n образует цепь Маркова, а все ее состояния – существенные и сообщающиеся, а d1  ...  dN  N . Определение. Существенное состояние Ej с периодом dj  1 называется ациклическим. Утверждение (без доказательства). Все состояния неприводимой цепи Маркова имеют одинаковый период. Определение. Неприводимая цепь Маркова, в фазовом пространстве которой все состояния ациклические, называется ациклической. Всякой конечной однородной цепи Маркова с матрицей переходных вероятностей  || pij ||NN , соответствует взвешенный орграф G  , для которого  является матрицей смежности: pij - это вес ребра eij если pij  0 , то ребро eij отсутствует. Такой орграф называется графом переходов. Для неприводимости цепи Маркова необходима сильная связность графа переходов. Эргодические подклассы составляет компоненты сильной связности орграфа, а несущественные состояния лежат на подходах к ним. Смена состояний в конечной однородной цепи Маркова эквивалентна переходу от вершины к вершине в конечном графе в соответствии с вероятностями, заданными весами на дугах. Такие процессы задают случайное блуждание на графе. Пример. При случайном блуждании с поглощающими экранами граф переходов выглядит следующим образом: Эргодическая теорема для неприводимых цепей Маркова Докажем некоторые результаты из теории чисел, играющие важную роль в дальнейшем изложении. Лемма 1. Если наибольший общий делитель чисел m1, m2 ,..., mr равен 1, то существует n 0   такое, что любое натуральное число n  n 0 можно представить в виде линейной комбинации n  k1m1  ...  kr mr , где ki   0 при всех i  1, r . r Доказательство. Возьмем произвольное n   и разделим его с остатком на m i 1 n  k (m1  ...  mr )  d , где Мы получим, что i . 0  d   i 1 mi . По свойствам k наибольшего общего делителя существуют такие li   , i  1, r , что 1  l1m1  ...  lr mr . Тогда n  k (m1  ...  mr )  d (l1m1  ...  lr mr )   (k  dl1 )m1  ...  (k  dlr )mr . Если обозначить ki  k  dli при всех i  1, r , то получим, что если k достаточно большое, то ki  0 .   Лемма доказана. Обозначим M i  n   : pii (n )  0 . Если Ei - состояние неприводимой цепи Маркова с периодом d , то из неприводимости следует, что множество M i не пусто, и d делит любое число n  M i . В множестве M i можно указать числа m1d,..., mrd такие, что наибольший общий делитель чисел m1, m2 ,..., mr равен 1 (иначе период был бы не d , а больше). Из леммы 1 следует, что существует n 0   такое, что любое натуральное число n  n 0 можно представить в виде линейной комбинации n  k1m1  ...  kr mr , где ki   0 при всех i  1, r . Следовательно, nd  k1m1d  ...  kr mrd . Лемма 2. В введенных выше обозначениях получаем, что все достаточно большие числа вида nd принадлежат множеству M i . Доказательство. Верна следующая цепочка неравенств: pii nd   pii k1m1d  ...  kr mrd      pii k1m1d   ...  pii kr mrd   pii m1d  k1    ...  pii m1d  kr  0. Лемма доказана. Следствие 1. Если d  1 , то в введенных выше обозначениях получаем, что все доста   точно большие числа n принадлежат множеству M i  m   : pii m   0 . Следствие 2. Для неприводимой ациклической цепи Маркова существует n 0   такое, что при любом натуральном числе n  n 0 все диагональные элементы матрицы переходных вероятностей за n шагов  n   n положительны. Лемма 3. Для неприводимой ациклической конечной цепи Маркова существует n1   такое, что при любом натуральном числе n  n1 все элементы матрицы n положительны. Доказательство. Из следствия 2 получаем, что достаточно проверить элементы, не стоящие на главной диагонали. Для всех Ei  E j из условий леммы следует, что существует натуральное nij такое, что pij nij   0 . Тогда для всех l   верно неравенство pij l  nij  n 0   pii n 0  l   pij nij   0 . Выберем в качестве n1  n 0  max nij  1 . (i , j ) Лемма доказана. Теперь с использованием этих лемм докажем следующий результат. Теорема (эргодическая для неприводимых ациклических цепей Маркова). Пусть цепь Маркова конечна, неприводима и ациклична (т. е. d  1 ). Тогда при всех i, j  1, N , где N - мощность фазового пространства E , существует ненулевой предел lim pij n  , n  который не зависит от i . Если обозначить lim pij n   p j , то pj  0 . n  Доказательство. Далее мы будем рассматривать такие n , что n  0 (т. е. pij n   0 при всех i, j  1, N ). Сперва введем обозначения. Пусть максимальный и минимальный элементы вероятностей n . Теперь при фиксированном j M j n   max pij n  , m j n   min pij n  i в j -м i столбце матрицы - переходных выберем i так, чтобы выполнялось равенство M j n  1  pij n  1 . Очевидно, что верна следующая цепочка неравенств M j n  1  pij n  1   pik pkj n   M j n   pik  M j n  . (k ) Теперь выберем i Очевидно, что (k ) так, чтобы выполнялось равенство m j n  1  pij n  1 . mj n  1  pij n  1   pik pkj n   mj n   pik  mj n  . (k ) (k ) Следовательно, при любом j верны неравенства 0  M j n  1  M j n  и 1  m j n  1  m j n  .     Последовательности M j n  и m j n  монотонны и ограничены. Следовательно, существуют пределы lim m j n   A и lim M j n   B . n  n  Если мы докажем, что A  B , то так как m j (n )  pij  M j (n) , то мы получим, что существует lim pij n   p j и этот предел из-за конечности фазового пространства цепи n  Маркова больше нуля. Если фазовое пространство состоит из одного элемента, то все очевидно. Мы будем рассматривать случай, когда E  1 . Выбираем состояния Ei  Ei и E j . 1 2 Используя уравнения Колмогорова-Чепмена, pi j n    pi k s  pkj n  s  и pi j n    pi k s  pkj n  s  . Тогда 1 1 (k ) 2 pi j n   pi j n   1 2 что 2 (k )  p n  s p s   p s  kj i1 j (k ) Введем два множества:   E получаем, i2 j  n   0 . E   Ek  E : pi k n   pi k n   0 , E Так 1 k 2  E : pi k n   pi k 1 2  p s   p s   1  1  0 , как i1k (k ) то i2k верно равенство  p s   p s     p s   p s  . Обозначим левую часть этого равенства k : Ek E  i1k i2k как h (i1, i2 ) . Тогда pi j n   pi j n   1 i1k k :Ek E  2  i2k  p s   p s  p n  s   k : Ek E  i1k i2k kj  p s   p s  p n  s   M n  s   h i , i   k : Ek E  i1k i2k kj j  1 2  m j n  s   h i1, i2   h i1, i2  M j n  s   m j n  s  . Так как E   E , то h i1, i2    k : Ek E  pi k s   1 . Обозначим h  max h i1, i2   1 . Тогда i1 ,i2  1    pi j n   pi j n   h M j n  s   m j n  s  . 1 2 Выберем числа i1 и i2 так, чтобы pi j n   M j n  и pi j n   m j n  . Обозначим 1 2 n  s  n / s   z , где z   , 0  z  n / s  . Тогда M j n   m j n   h M j n  s   m j n  s          h 2 M j n  2s   m j n  2s    h  Очевидно, что n /s   M z   m z  . j j M j z   m j z   M j z   1 , следовательно,  M j n   m j n   h  Так как h  1 , то верны неравенства   n /s   . 0  lim M j n   m j n   lim h  n  n /s   n   0. Следовательно, существуют и равны между собой пределы lim M j n   lim m j n   lim pij n   p j  0 . n  n  n  Теорема доказана. Вектор p  p1, p2 ,..., pN  назовем предельным распределением цепи Маркова или эргодическим распределением. Легко видеть, что верно следующее равенство  p p  p   1 2 N  p p  p  2 N  , lim n   1  n          p1 p2  pN  т.е. устремив степень матрицы переходных вероятностей неприводимой конечной ациклической цепи Маркова к бесконечности, мы получим матрицу, в которой все строки одинаковы, и которая не содержит нулевых элементов. Теорема (без доказательства). Предельное распределение конечной неприводимой ациклической цепи Маркова с фазовым пространством мощности N удовлетворяет системе линейных уравнений: N  xk  1  k 1  N  x  x p , j 1, N   j k 1 k kj и является её единственным решением. Если обозначить x  x 1,..., x n  , то эту систему можно записать в виде  N  x  1  k .  k 1 x  x  Определение. Рассмотрим матрицу AN ,N с неотрицательными элементами. Если для всех i  1, N N выполняется равенство a j 1  1, ij то эта матрица называется стохастической. Стохастическая матрица BN ,N называется дважды стохастической, если для всех j  1, N выполняется равенство N b i 1 ij  1. Следствие. Если конечная неприводимая ациклическая цепь Маркова имеет дважды стохастическую матрицу переходных вероятностей, то её предельное распределение имеет вид: 1 1 p   ,...,  . N  N Легко видеть, что такой вектор – решение системы уравнений  N  x  1  k .  k 1 x  x  Стационарные распределения Пусть дана цепь Маркова с матрицей переходных вероятностей  и начальным   распределением p(0)  P 0  j , j  1, N , где N – мощность фазового пространства E . Через p(n ) обозначим распределение цепи Маркова в момент времени n :   p(n )  P n  j , j  1, N , p(n )  p(0)n . Определение. Вектор q с координатами q ,...,q  1 распределением цепи Маркова, если для всех i  1, N N выполняются равенства q i 1 i N называется стационарным верно неравенство qi  0 и  1 и q  q . Заметим, что если в качестве p(0) взять q , то для всех n   выполняется p (n )  qn  qn 1  ...  q . Если цепь Маркова конечна, ациклична и неприводима, то по теореме об эргодичности существует единственное стационарное распределение, совпадающее с предельным: q j  lim pij (n )  pj . n 

Рекомендованные лекции

Смотреть все
Высшая математика

Системные представления в технической эксплуатации ЛА. Основы системного анализа

Уважаемые студенты-бакалавры-заочники! Вот основной материал для изучения дисциплины МСиПр, кроме теории графов. Эта теория в отдельных файлах.. Предл...

Высшая математика

Элементы теории случайных процессов

МИНОБРНАУКИ РОССИИ –––––––––––––––––– Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» ––––––––––––––––––––––––––––––––––––––...

Автор лекции

Е.А. Бурков П.И. Падерно

Авторы

Теория вероятностей

Случайные процессы. Математическое ожидание. Корреляционная функция СП

1. Случайные процессы Функция X(t) называется случайной, если при каждом значении аргумента t = t* X(t*) является случайной величиной (СВ). Если аргум...

Теория вероятностей

Марковские процессы с дискретным множеством состояний.Цепи Маркова

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

Теория вероятностей

Теория вероятностей. Основные понятия.

Министерство Российской Федерации по связи и информатизации Сибирский государственный университет телекоммуникаций и информатики Н. И. Чернова ТЕОРИЯ ...

Автор лекции

Чернова Н.И.

Авторы

Теория вероятностей

Методы и системы принятия решений

Министерство образования и науки Российской Федерации ФГБОУ ВПО «Сибирский федеральный университет» Г.А. Доррер МЕТОДЫ И СИСТЕМЫ ПРИНЯТИЯ РЕШЕНИЙ Допу...

Автор лекции

Доррер Г.А.

Авторы

Теория вероятностей

Марковские процессы с непрерывным временем

Тема № 3 Марковские процессы с непрерывным временем   Теперь рассмотрим процесс t ; t  T , где T   0;  . Определение. Случайный процесс t ;...

Высшая математика

Марковские процессы. Модели массового обслуживания

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

Высшая математика

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

ЦЕПИ МАРКОВА И СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ 1. Марковские цепи с конечным числом состояний и дискретным временем. Пусть некоторая физическая система...

Высшая математика

Дискретная математика

Дискретная математика (конспект лекций) для студентов направления 09.03.03 «Прикладная информатика» 2 Теория множеств. Множеством S называется объедин...

Смотреть все