Маркова цепь

- марковский процесс с конечным или счетным множеством состояний. Теория М. ц. возникла на основе исследований А. А. Маркова, к-рый в 1907 положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин [1]. Пусть пространство состояний - множество натуральных чисел Nили его конечное подмножество. Пусть x(t) - состояние М. ц. в момент времени t. Основным для М. Ц. является марковское свойство, к-рое для М. ц. с дискретным временем (т. с. в случае, когда время tпринимает лишь целые неотрицательные значения) определяется следующим образом: для любых t, [img: http://localhost:8080/file/031405-113.jpg] любых целых неотрицательных t1<t2<...<tk<t и любых натуральных i1, i2,..., ik имеет место равенство [img: http://localhost:8080/file/031405-114.jpg] Марковское свойство (1) можно переформулировать следующим образом. Момент времени tи связанные с ним события вида {x(t)=j}назовем "настоящим" процесса; события, определяемые значениями x(u) с u<t, -"прошлым" процесса; события, определяемые значениями x(u) с u>t, - "будущим" процесса. Тогда свойство (1) равносильно следующему: для любого [img: http://localhost:8080/file/031405-115.jpg] при фиксированном "настоящем" x(t)=j любые "прошлое" Аи "будущее" Всобытия условно независимы, т. е. [img: http://localhost:8080/file/031405-116.jpg] Для вероятностного описания М. ц. x(t) большую роль играют переходные вероятности [img: http://localhost:8080/file/031405-117.jpg] В случае, когда переходные вероятности (2) не зависят от t, М. ц. наз. однородной (во времени); в противном случае - неоднородной. Далее рассматриваются лишь однородные М. ц. Пусть [img: http://localhost:8080/file/031405-118.jpg] Матрица [img: http://localhost:8080/file/031405-119.jpg] с элементами pij наз. матрицей переходных вероятностей. Вероятность любой траектории [img: http://localhost:8080/file/031405-120.jpg] выражается через переходные вероятности р ij и начальное распределение [img: http://localhost:8080/file/031405-121.jpg] следующим образом: [img: http://localhost:8080/file/031405-122.jpg] Наряду с переходными вероятностями р ij в М. ц. рассматриваются также переходные вероятности Pij(t).за tшагов: [img: http://localhost:8080/file/031405-123.jpg] Эти переходные вероятности удовлетворяют Колмогорова- Чепмена уравнению [img: http://localhost:8080/file/031405-124.jpg] С помощью переходных вероятностей можно произвести следующую классификацию состояний. Два состояния i и j наз. сообщающимися, если найдутся такие t1>0, t2>0, что pij(t1)>0и р ij(t2)>0. Состояние kназ. несущественным, если найдется такое состояние l, что pkl(t1)>0 для нек-рого [img: http://localhost:8080/file/031405-125.jpg] для всех [img: http://localhost:8080/file/031405-126.jpg] Все остальные состояния наз. существенными. Таким образом, все множество состояний М. ц. разбивается на несущественные и существенные состояния. Множество всех существенных состояний разбивается на непересекающиеся классы сообщающихся состояний так, что любые два состояния из одного класса сообщаются между собой, а для любых двух состояний i и j из разных классов [img: http://localhost:8080/file/031405-127.jpg] М. ц., все состояния к-рой составляют один класс сообщающихся состояний, наз. неразложимой (см. Маркова цепь неразложимая);в противном случае М. ц. наз. разложимой (см. Маркова цепь разложимая). Если множество состояний конечно, то разбиение его на эти классы в значительной степени определяет асимптотич. свойства М. ц. Напр., для конечной неразложимой М. ц. всегда существует предел [img: http://localhost:8080/file/031405-128.jpg] причем [img: http://localhost:8080/file/031405-129.jpg] Если, кроме того, М. ц. непериодическая, т. е. при нек-ром t0 для всех [img: http://localhost:8080/file/031405-130.jpg] и всех состояний iи j pij(t)>0 (см. также Маркова цепь периодическая), то имеет место более сильное утверждение [img: http://localhost:8080/file/031405-131.jpg] (см. также Маркова цепь эргодическая). Если множество состояний М. ц. счетно, то ее асимптотич. свойства зависят от более тонких свойств классов сообщающихся состояний. Ряд [img: http://localhost:8080/file/031405-132.jpg] расходится или сходится сразу для всех состояний данного класса. Класс состояний наз. возвратным, если для любого состояния i этого класса ряд (5) расходится, и невозвратным, если ряд (5) сходится. В возвратном классе с вероятностью 1 М. ц. возвращается в любое свое состояние, в невозвратном классе вероятность возвращения меньше 1. Если среднее время возвращения в возвратном классе конечно, то класс наз. положительным; в противном случае класс наз. нулевым (см. Маркова цепи положительный класс состояний, Маркова цепи нулевой класс состояний). Если iи j принадлежат одному положительному классу состояний, то существует предел (3), а в непериодическом случае и предел (4). Если j принадлежит нулевому классу состояний или несущественно, то [img: http://localhost:8080/file/031405-133.jpg] Пусть f(Х) - действительная функция, определенная на состояниях М. ц. x(t). Если М. ц. неразложима и ее состояния образуют положительный класс, то для сумм [img: http://localhost:8080/file/031405-134.jpg] справедлива центральная предельная теорема: [img: http://localhost:8080/file/031405-135.jpg] при нек-рых Аи B>0. Для выполнения (6) достаточно дополнительно потребовать [img: http://localhost:8080/file/031405-136.jpg] Если время tпринимает любые значения из [img: http://localhost:8080/file/031405-137.jpg] то М. ц. является М. ц. с непрерывным временем, к-рая определяется аналогично с помощью марковского свойства (1). Обычно для М. ц. с непрерывным временем требуют дополнительно, чтобы существовали конечные правые производные [img: http://localhost:8080/file/031405-138.jpg] к-рые наз. плотностями вероятностей перехода. Для конечной М. ц. с непрерывным временем из уравнения Колмогорова - Чепмена можно получить две системы дифференциальных уравнений Колмогорова: [img: http://localhost:8080/file/031405-139.jpg] и [img: http://localhost:8080/file/031405-140.jpg] к к-рым присоединяются начальные условия р ij(0)=dij, где dij - символ Кронекера. При нек-рых дополнительных предположениях системы уравнений (7) и (8) справедливы и для счетных М. ц. Если М. ц. с непрерывным временем имеет стационарное распределение [img: http://localhost:8080/file/031405-141.jpg] (т. е. распределение x(t), не зависящее от времени t), то это распределение {р i} удовлетворяет следующей системе линейных уравнений: [img: http://localhost:8080/file/031405-142.jpg] М. ц. широко используются при решении различных прикладных задач. Напр., в теории массового обслуживания для расчета распределения вероятностей числа занятых приборов в системе М|М|п с отказами (т. е. в системе, состоящей из пприборов с пуассоновским потоком требований и показательным законом времени обслуживания) используется конечная М. ц. с непрерывным временем, состояниями 0, 1,..., n и со следующими плотностями вероятностей перехода: [img: http://localhost:8080/file/031405-143.jpg] если |i-j|>1 (здесь l - интенсивность пуассоновского потока требований, m-1 - среднее время обслуживания). С помощью (9) в этом случае определяется следующее стационарное распределение числа занятых приборов: [img: http://localhost:8080/file/031405-144.jpg] к-рое наз. распределением Эрланга. См. также Маркова цепь сложная, Маркова цепь возвратная, Поглощающее состояние, Стохастическая матрица. Переход с запрещениями.