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

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

Последовательность образует цепь Маркова, если

=

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

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

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

Введем матрицу, образующую вероятностями

Из записанного выше равенства следует, что Тогда

Распределение цепи будет полностью определено, если задано некоторое начальное распределение величины

и задана матрица перехода P.

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

Множество состояние ,- первый игрок имеетрублей.

Начальное распределение:

Матрица перехода

Если игрок не имеет денег, игра прекращается. Игрок остается в состоянии с вероятностью 1.

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

Если игрок имеет 4 рубля, то игра прекращается из-за банкротства второго игрока.

Проведем классификацию состояний.

1. Состояние называетсянесущественным, если существует такое состояние и целое числочтодля любого.

Из несущественного состояния за несколько шаговможно попасть в состояние, но уже из состоянияникогда не вернуться в состояние.

2. Существенные состояния иназываютсясообщающимися, если существуют , чтои.

Из существенного состояния за несколько шаговможно попасть в существенное состояниеи из него зашагов можно попасть обратно в состояние.

Пример 2. Система находится в одном из состояний Дана матрица перехода

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

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

Существенными являются сообщающиеся состояния и

Существенные несообщающиеся состояния называются поглощающими.

В примере 1 состояния иявляются полагающими, а состоянияявляются несущественными.

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

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

Далее рассмотрим неразложимую цепь Маркова. Пусть мы вышли из состояния и вернулись в него впервые только черезшагов. Введем вероятность этого события

Пусть

Продолжим классификацию состояний.

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

4. Состояние называетсянулевым, если иненулевым в противном случае.

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

Приведем теорему солидарности:

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