МАРКОВА ЦЕПЬ

- марковский процесс с конечным или счетным множеством состояний. Теория М. ц. возникла на основе исследований А. А. Маркова, к-рый в 1907 положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин [1].

Пусть пространство состояний - множество натуральных чисел Nили его конечное подмножество. Пусть x(t) - состояние М. ц. в момент времени t. Основным для М. Ц. является марковское свойство, к-рое для М. ц. с дискретным временем (т. с. в случае, когда время tпринимает лишь целые неотрицательные значения) определяется следующим образом: для любых t,любых целых неотрицательных t₁<t₂<...<t_k<t и любых натуральных i₁, i₂, ..., i_k имеет место равенство

Марковское свойство (1) можно переформулировать следующим образом. Момент времени tи связанные с ним события вида {x(t)=j}назовем "настоящим" процесса; события, определяемые значениями x(u) с u<t, -"прошлым" процесса; события, определяемые значениями x(u) с u>t, - "будущим" процесса. Тогда свойство (1) равносильно следующему: для любого при фиксированном "настоящем" x(t)=j любые "прошлое" Аи "будущее" Всобытия условно независимы, т. е.

Для вероятностного описания М. ц. x(t) большую роль играют переходные вероятности

В случае, когда переходные вероятности (2) не зависят от t, М. ц. наз. однородной (во времени); в противном случае - неоднородной. Далее рассматриваются лишь однородные М. ц. Пусть

Матрица с элементами p_ij наз. матрицей переходных вероятностей. Вероятность любой траектории выражается через переходные вероятности р _ij и начальное распределение следующим образом:

Наряду с переходными вероятностями р _ij в М. ц. рассматриваются также переходные вероятности P_ij(t).за tшагов:

Эти переходные вероятности удовлетворяют Колмогорова- Чепмена уравнению

С помощью переходных вероятностей можно произвести следующую классификацию состояний. Два состояния i и j наз. сообщающимися, если найдутся такие t₁>0, t₂>0, что p_ij(t₁)>0и р _ij(t₂)>0. Состояние kназ. несущественным, если найдется такое состояние l, что p_kl(t₁)>0 для нек-рого для всех Все остальные состояния наз. существенными. Таким образом, все множество состояний М. ц. разбивается на несущественные и существенные состояния. Множество всех существенных состояний разбивается на непересекающиеся классы сообщающихся состояний так, что любые два состояния из одного класса сообщаются между собой, а для любых двух состояний i и j из разных классов М. ц., все состояния к-рой составляют один класс сообщающихся состояний, наз. неразложимой (см. Маркова цепь неразложимая);в противном случае М. ц. наз. разложимой (см. Маркова цепь разложимая). Если множество состояний конечно, то разбиение его на эти классы в значительной степени определяет асимптотич. свойства М. ц. Напр., для конечной неразложимой М. ц. всегда существует предел

причем Если, кроме того, М. ц. непериодическая, т. е. при нек-ром t₀ для всех и всех состояний iи j p_ij(t)>0 (см. также Маркова цепь периодическая), то имеет место более сильное утверждение

(см. также Маркова цепь эргодическая).

Если множество состояний М. ц. счетно, то ее асимптотич. свойства зависят от более тонких свойств классов сообщающихся состояний. Ряд

расходится или сходится сразу для всех состояний данного класса. Класс состояний наз. возвратным, если для любого состояния i этого класса ряд (5) расходится, и невозвратным, если ряд (5) сходится. В возвратном классе с вероятностью 1 М. ц. возвращается в любое свое состояние, в невозвратном классе вероятность возвращения меньше 1. Если среднее время возвращения в возвратном классе конечно, то класс наз. положительным; в противном случае класс наз. нулевым (см. Маркова цепи положительный класс состояний, Маркова цепи нулевой класс состояний). Если iи j принадлежат одному положительному классу состояний, то существует предел (3), а в непериодическом случае и предел (4). Если j принадлежит нулевому классу состояний или несущественно, то

Пусть f(Х) - действительная функция, определенная на состояниях М. ц. x(t). Если М. ц. неразложима и ее состояния образуют положительный класс, то для сумм

справедлива центральная предельная теорема:

при нек-рых Аи B>0. Для выполнения (6) достаточно дополнительно потребовать

Если время tпринимает любые значения из то М. ц. является М. ц. с непрерывным временем, к-рая определяется аналогично с помощью марковского свойства (1). Обычно для М. ц. с непрерывным временем требуют дополнительно, чтобы существовали конечные правые производные

к-рые наз. плотностями вероятностей перехода. Для конечной М. ц. с непрерывным временем из уравнения Колмогорова - Чепмена можно получить две системы дифференциальных уравнений Колмогорова:

и

к к-рым присоединяются начальные условия р _ij(0)=d_ij, где d_ij - символ Кронекера. При нек-рых дополнительных предположениях системы уравнений (7) и (8) справедливы и для счетных М. ц.

Если М. ц. с непрерывным временем имеет стационарное распределение (т. е. распределение x(t), не зависящее от времени t), то это распределение {р _i} удовлетворяет следующей системе линейных уравнений:

М. ц. широко используются при решении различных прикладных задач. Напр., в теории массового обслуживания для расчета распределения вероятностей числа занятых приборов в системе М|М|п с отказами (т. е. в системе, состоящей из пприборов с пуассоновским потоком требований и показательным законом времени обслуживания) используется конечная М. ц. с непрерывным временем, состояниями 0, 1, ..., n и со следующими плотностями вероятностей перехода:

если |i-j|>1 (здесь l - интенсивность пуассоновского потока требований, m^-1 - среднее время обслуживания). С помощью (9) в этом случае определяется следующее стационарное распределение числа занятых приборов:

к-рое наз. распределением Эрланга.

См. также Маркова цепь сложная, Маркова цепь возвратная, Поглощающее состояние, Стохастическая матрица. Переход с запрещениями.

Лит.:[1] М а р к о в А. А., "Изв. Петерб. АН" (6), 1907, т. 1, № 3, с. 61-80; [2] Д у б Д ж., Вероятностные процессы, пер. с англ., М., 1956; [3] Ч ж у н К а й - л а й, Однородные цепи Маркова, пер. с англ., М., 1964; [4] Феллер В., Введение в теорию вероятностей и ее приложения, пер. с англ., 2 изд. т. 1, М., 1967. Б. А. Севастьянов.