Дискретные случайные последовательности. Цепи Маркова

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

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

Случайный процесс x₁, x₂, … со значениями x_iÎX, i = 1, 2, … задан, если для любых n указан способ вычисления совместных распределений вероятностей P(x₁…x_n).

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

,

где P(x_i)– вероятность появления x_iÎX в момент времени i. Для описания такого процесса достаточно указать вероятности P(x_i)для всех x_iÎX (всего N - 1 вероятностей).

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

Процесс называется стационарным, если для любых n и m имеет место равенство

,

в котором подразумевается, что x_i=x_i+m, i=1, …, n.

Иными словами, случайный процесс стационарен, если вероятность любой последовательности не изменяется при ее сдвиге во времени (не зависит от положения последовательности на оси времени).

Числовые характеристики, в частности, математическое ожидание стационарных процессов не зависят времени. Рассматривая стационарные процессы, мы сможем вычислять независящие от времени информационные характеристики случайных процессов.

Мы уже рассмотрели один пример стационарного процесса – процесс, значения которого независимы и одинаково распределены. Источник, порождающий такой процесс, называют дискретным постоянным источником (ДПИ).

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

Случайный процесс x₁, x₂, … называют цепью Маркова связности s , если для любых n и для любых справедливы соотношения

.

Иными словами, мы называем марковским процессом связности s такой процесс, для которого при n > s

P(x_n / x₁,…,x_n-1)= P(x_n / x_n-s,…,x_n-1),

то есть условная вероятность текущего значения при известных s предшествующих не зависит от всех других предшествующих значениях.

Описание марковского процесса задается начальным распределением вероятностей на последовательностях из первых s значений и условными вероятностями вида P(x_n | x_n-s,…,x_n-1) для всевозможных последовательностей (x_n-s,…,x_n). Если указанные условные вероятности не изменяются при сдвиге последовательностей (x_n-s,…,x_n) во времени, марковская цепь называется однородной.

Однородная марковская цепь связности s=1называется простой цепью Маркова. Для описания простой цепи Маркова с множеством состояний X={1,2,…,N}достаточно указать начальное распределение вероятностей {P(x_i),x_iÎX} и условные вероятности

,

называемые переходными вероятностями цепи Маркова.

Переходные вероятности удобно записывать в виде квадратной матрицы размерности N×N:

называемой матрицей переходных вероятностей. Эта матрица – стохастическая (неотрицательная, сумма элементов каждой строки равна 1).

Обозначим через стохастический вектор, компоненты которого – вероятности состояний цепи Маркова в момент времени m, то есть , где P_m(i) есть вероятность состояния i в момент времени m, i = 1, ..., N. Из формулы полной вероятности следует, что

или в матричной форме

. (11.5)

Отсюда для произвольного числа шагов n получаем

.

Значит, вероятности перехода за n шагов могут быть вычислены как элементы матрицы Pⁿ.

Из (11.5) видим, что распределение вероятностей в момент времени m зависит от величины m и от начального распределения . Отсюда следует, что в общем случае рассматриваемый случайный процесс нестационарен. Предположим, однако, что существует стохастический вектор , удовлетворяющий уравнению

. (11.6)

Положим = . Тогда, воспользовавшись (11.5), получим = и, в конечном итоге, = при всех m. Таким образом, однородная марковская цепь стационарна, если в качестве начального распределения выбрано решение уравнения (11.6).

Стохастический вектор , удовлетворяющий уравнению (11.6), называется стационарным распределением для цепи Маркова, задаваемой матрицей переходных вероятностей P.

Финальным распределением вероятностей называют вектор

(11.7)

(если предел существует).

Из этого определения следует, что финальное распределение – распределение вероятностей в момент времени m бесконечно далекий от начального момента времени m = 1. Было бы естественно ожидать, что оно не зависит от начального распределения . Оно не зависит также и от времени. Таким образом, распределение тоже (как и), в некотором смысле, – стационарное распределение. Как же соотносятся между собой и ?

Оказывается, для широкого класса простых цепей Маркова предел в (11.7) не зависит от начального распределения и равен единственному решению уравнения (11.6), то есть = . Такие цепи называют эргодическими.

Как определить по матрице P эргодична ли соответствующая цепь Маркова? Ответ заведомо положительный, если все элементы матрицы P положительны (не равны нулю). Более точное (но и сложнее проверяемое) условие состоит в том, что должна существовать некоторая положительная степень n₀матрицы P такая, что все элементы матрицы Pⁿ положительны при любых n ≥ n₀.

Чтобы сформулировать необходимое и достаточное условие эргодичности, придется ввести несколько определений.

Состояние цепи i достижимо из состояния j, если для некоторого n вероятность перехода из состояния j в состояние i за n шагов положительна. Множество состояний C называется замкнутым, если никакое состояние вне C не может быть достигнуто из состояния, входящего в C .

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

Состояние i называется периодическим, если существует такое m > 1, что вероятность перехода из i в i за n шагов равна нулю при всех n не кратных m. Цепь, не содержащая периодических состояний, называется непериодической.

Непериодическая неприводимая цепь Маркова эргодична.

Не нашли, что искали? Воспользуйтесь поиском по сайту: