Geum.ru

Курс лекций для специальности Прикладная математика и информатика

Вид материалаКурс лекций

Содержание


Марковское свойство
Подобный материал:
1   2   3   4   5   6   7   8   9   10   11
§24. Цепи Маркова.

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

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

Множество будем называть множеством состояний.

играет роль времени, - состояние системы, за которой мы наблюдаем.

Марковское свойство:

- прошлое и будущее независимы при фиксированном настоящем.

Определим , где - переходная вероятность из состояния в состояние в момент времени .

Если (т . е. не зависит от момента времени) однородная цепь Маркова.

Чтобы знать все вероятности , необходимо знать

  • .

Например, = .

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

Для матрицы выполняются условия:



Любая матрица с такими совйствами называется стохастической.

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


и матрицу
  1. .

Задачи.
  1. Пусть - цепь Маркова. Показать, что тоже цепь Маркова.
  2. независимые одинаково распределенные целочисленные случайные величины с известными вероятностями Какой вид имеет матрица 



Лекция 14 (7.12.10)

Зададимся следующим вопросом: верно ли, что для однородных марковских цепей справедливо равенство

при всех натуральных k?

Утверждение: однородная ЦМ , при всех .

Доказательство: индукцией по .

База: - равенство следует из определения однородной ЦМ.

Пусть верно для , докажем для .

Рассмотрим


= == = = = = = = .


Введем обозначение: - это переходная вероятность из состояния в состояние за шагов.

 – это тоже стохастическая матрица (оба свойства выполняются).


Пусть известна - матрица переходных вероятностей за 1 шаг.

Как найти  - матрицу переходных вероятностей за шагов?


Теорема (Маркова – Чепмена - Колмогорова)

  = 

Следствия:
  1.  = ;
  2.   .

Доказательство (теоремы). Достаточно доказать равенство:



Имеем

= { умножаем и делим (как в утверждении) на } = .

Доказали следующее равенство:  . Это доказывает теорему.

Замечание (к теореме и утверждению): Умножать и делить можно лишь тогда, когда в знаменателе не 0.


Пусть принимают конечное число значений. Пусть . ЦМ можно изобразить графически и составить для нее 






Можно и наоборот, по  построить график.

Задача: Знаем . Можно ли восстановить ?


§25. Классификация состояний.

Пусть - состояния.

Определения.

Состояние достижимо из состояния () существует : .

Состояния и наз. сообщающимися () и существуют : >0 и >0, ( может быть и не равно ).

Состояние называется существенным, если оно сообщается с любым достижимым из него состоянием , т.е. куда бы не ушли из , то всегда бы с могли в него вернуться.

Утверждение:
  1. и

Доказательство: Существует : и существует : .

Рассмотрим .
  1. Пусть - существенное состояние и . Тогда тоже существенное состояние.

Доказательство: Предположим противное: пусть - несущественное существует состояние : и .

и (т.к. - сущ.)

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

Доказательство: следует непосредственно из предыдущих утверждений.








Введем обозначение: - вероятность впервые достичь лишь на -ом шаге.

- вероятность впервые вернуться в состояние на -ом шаге.

- вероятность когда-нибудь вернуться в состояние .

Определение.

Состояние называется возвратным .

Если , то - невозвратное состояние.

Примеры:
  1. k – состояние (все целые числа на вещественной прямой, их счетное количество)

на каждом шаге происходит сдвиг вправо на 1 или остаемся на месте.

Здесь возвратных состояний нет.
  1. , , , .

Т.о., состояние 3 возвратное.


Теорема (Критерий возвратности)
  1. - возвратное состояние (ряд расходится);
  2. - невозвратное состояние .

Доказательство теоремы.

Пусть имеется последовательность чисел (),.

, если такой ряд суммируемый.

- производящая функция последовательности .

Рассмотрим и , тогда их производящие функции:

; ;

Имеем по формуле полной вероятности:

; тогда

. Отсюда следует равенство

(равенство после суммирования) (*).

определена на , т.к. при ряд может расходиться.

определена на , т.к. ряд всегда конечен.

Заметим, что .

Из (*) следует ; и далее (если - возвратное состояние), т.е. ряд расходится.

Если ряд расходится, то при - возвратное состояние.


Лекция 15 (14.12.10)

Пусть цепь Маркова. Разобьем все состояния цепи Маркова на следующие классы:

класс несущественных состояний. Пусть существует существенное состояние

Тогда

существенные состояния, сообщающиеся с . Пусть существует существенное состояние , которое не входит в класс S1. Тогда

существенные состояния, сообщающиеся с .

…

Понятно, что эти классы не пересекаются, т.е.



Перенумеруем состояния. Сначала занумеруем состояния из класса S0, затем из класса S1 и т.д.

Тогда матрица переходных вероятностей за n шагов будет иметь следующий вид:






…
















0




0
0



0

0




0




















Каждый блок в отдельности – стохастическая матрица.

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

Теорема. (О солидарности для возвратности)

Пусть ЦМ неразложимая или все состояния возвратные, или все невозвратные.

Доказательство.

Пусть возвратное состояние и пусть состояние .

Пусть

Напомним, что по критерию возвратности

возвратное состояние

Рассмотрим



состояние тоже возвратно.


Случайные блуждания по целым точкам в 



н. о. р. с. в. ,

цепь Маркова - случайное блуждание по целым точкам на . ().

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

Очевидно, что



Рассмотрим =

Используем формулу Стирлинга ( где ) и получаем

где . Тогда

( заметим, что в этом случае)

состояние 0 – возвратное, а если состояние 0 – невозвратное.

Итак, если случайное блуждание по целым точкам на вещественной прямой симметрично (т.е. p=q), то оно возвратное и наоборот.


Случайное блуждание по решётке «целочисленных» точек в 




Симметричные случайные блуждания на плоскости тоже будут возвратными.

Рассмотрим событие, которое означает возврат в начальное состояние через шагов.

Каждая из таких ситуаций может быть записана цепочкой длины последовательности шагов : (П П В Н … Л … В) -

Здесь П означает шаг вправо, Л – шаг влево, В – шаг вверх и Н – шаг вниз, причем для возврата в начальное состояние число шагов в каждом направлении должно быть следующим:


в сумме шагов

Тогда








Ряд с такими членами расходится, и следовательно, такое случайное блуждание тоже возвратное.


Случайное блуждание в 


Рассмотрим симметричные случайные блуждания по точкам с целочисленными координатами в трехмерном пространстве. Здесь шаг вверх – ВВ, шаг вниз – ВН, шаг вправо – П , шаг влево – Л, шаг вперед – ВП и шаг назад – Н и пусть



Для возврата в начальное состояние число шагов в каждом направлении должно быть

следующим:

в сумме шагов

Тогда

=





Заметим, что



Поскольку



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