§ 2. Конечные однородные цепи Маркова

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

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

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

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

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

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

Случай б). Существуют целое число и совокупность из значений для которых

В этом случае существуют числа такие, что

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

Таким образом, в случае б) свойства вероятностей перехода за большое число шагов аналогичны их свойствам в случае а). Действительно, независимо от начального распределения, вероятность того, что система через большое число шагов будет находиться в состоянии равна примерно Доказательство. Определим и Ыравенствами

Тогда

так что

Если теперь фиксировать значения и обозначить через суммирование по всем значениям , для которых соответственно,

и если имеется значений , входящих в и включенных в

Используя эти два соотношения, находим, что при

Далее,

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

Поэтому [см. (2.4)] и должны иметь общий предел при и

Если то Если положить в (и учесть, что неотрицательны и равны в сумме 1), то получаемое таким путем соотношение в точности совпадает с условием того, чтобы образовывали стационарное распределение вероятностей. На этом исследование случая б) заканчивается.

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

Теорема 2.1. Для любой стохастической матрицы существует стохастическая матрица такая, что

При этом .

Подчеркнем, что здесь не налагаются никакие ограничения на стохастическую матрицу Наша теорема утверждает, что существуют предельные средние по времени значения вероятностей того, что система, вышедшая из состояния находится в состоянии В дальнейшем запись где последовательность матриц, означает, что для всех Если — две матрицы, то В обозначает матрицу и если -постоянное число, то обозначает матрицу Тогда (2.11) можно записать в виде

Матрицы

являются стохастическимй матрицами. Так как элементы стохастической матрицы ограничены по модулю (не превосходят 1), то каждая последовательность такпх матриц содержит сходящуюся подпоследовательность. Следовательно, для того чтобы доказать существование предела в (2.11), достаточно показать, что все сходящиеся подпоследовательности рассматриваемых средних имеют один и тот же предел. Предположим, что А — предел некоторой сходящейся подпоследовательности, т. е. что для соответствующей последовательности целых чисел

Умножая это соотношение на слева и справа, находим, что

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

которые стремятся к нулю при Поэтому

Отсюда следует, что для любого

Следовательно, если В — некоторая предельная матрица подпоследовательности средних в (2.11), то

Так как в этом соотношении две любые предельные матрицы, то, поменяв их местами, будем иметь

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

Нам потребуется следующая лемма.

Лемма 2.2. Пусть совокупность положительных целых чисел и наибольший общий делитель чисел из Если при любых также и то все достаточно большие целые кратные числа входят в

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

Перенося в этом соотношении члены с отрицательными вправо, мы видим, что в входят два целых числа вида Тогда при любом положительном целые числа

также входят в т. е. если то в содержатся все целые числа вида

В эту совокупность чисел, очевидно, входят все кратные числа большие чем

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

Случай в). Для любых состояние является последующим за состоянием

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

то если в эту совокупность порядков входят числа то в нее входит также число Следовательно, по нашей лемме, в эту совокупность порядков входят все достаточно большие кратные числа Далее,

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

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

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

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

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

И вообще, если то

Отсюда следует, что

и этот предел не зависит от Таким образом, каково бы ни было начальное состояние существует предельное среднее значение вероятности того, что система будет в состоянии после большого числа переходов; точнее, вероятность находиться в состоянии после большого числа переходов или равна 0, или же близка к в зависимости от того, будет ли (если или нет. При больших ненулевые клетки матрицы состоят только из положительных элементов.

Случай г). Общий случай. Все состояния могут быть разделены на два типа: существенные состояния — состояния, являющиеся последующими за любым из своих последующих состояний, и несущественные состояния — состояния, не являющиеся последующими за каким-нибудь из своих последующих состояний. Если состояние является последующим за существенным состоянием то оно и само является существенным. Действительно, если к является последующим за состоянием то оно также последующим за состоянием к и, следовательно, должно быть последующим за к существенное состояние), Но тогда является последующим за к, к что и требовалось доказать. Совокупность цественных состояний обозначим буквой Существенные состояни. далее, на эргодичужие классы состояний, являющихся последующими друг за другом; при этом если

Если перенумеровать состояния так, чтобы сначала шли состояния из потом из и последними — состояния, входящие в то матрица примет указанный выше вид (на схеме показано три эргодических класса). Положительные элементы могут быть только в клетках Степени матрицы имеют тот же самый вид. Предположим теперь, что и покажем, что по крайней мере одно из состояний, последующих за лежит в эргодическом классе, т. е. по крайней мере одно из состояний, последующих за является существенным. Пусть множество состояний, последующих за Тогда в входят все последующие за входящими в него состояния, т. е. если то пусть есть то из которое состоит из наименьшего числа состояний. Из этого свойства минимальности вытекает, что должно совпадать с совокупностью состояний, последующих за любым из входящих в состояний. Но тогда состоит из существенных состояний и является в действительности эргодическим классом; все состояния из этого класса являются последующими за состоянием Это означает, во-первых, что всегда существуют существенные состояния и, во-вторых, что для каждой из строк, соответствующих состояниям из найдется такое что матрица содержит ненулевой элемент в столбце, соответствующем какому-нибудь из При каждом а класс определяет некоторую стохастическую матрицу,

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

где

Следовательно,

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

Если то не может увеличиваться при возрастании Эта сумма представляет собой вероятность перехода за шагов из состояния в состояния, принадлежащие т. е. вероятность оставаться в в течение всех шагов, так как, однажды выйдя из система остается навсегда вне Далее, как мы уже видели, при больших эта сумма меньше 1. Выберем теперь настолько большим, чтобы при и всех эти суммы были меньше 1,

Тогда

так что

Так как сумма изменяется при растущем монотонно, то

Итак, сумма слева, являющаяся вероятностью остаться в после шагов, стремится к нулю при Таким образом, мы получили следующую теорему:

Теорема 2.3. С вероятностью 1 система остается в несущественных состояниях лишь в течение конечного числа шагов.

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

(суммы, стоящие под знаком предела, не убывают с ростом так как, однажды попав в система остается там навсегда; поэтому сумма совпадает с вероятностью попасть в за первые шагов). Если то если то Далее, если то

Вторая из этих двух сумм не превосходит а как мы видели, эта последняя сумма стремится к при Следовательно, если положить в этом соотношении и если то мы получим, что

В обидам случае, когда пусть вероятность того, что система, находившаяся вначале в состоянии будет в конце концов находиться в подклассе в моменты с номерами

Тогда

Если

где берется по модулю Полагая в этом соотношении мы находим, что

[Соотношение (2.12) является частным случаем при Следовательно,

Мы снова доказали, таким образом, теорему 2.1 и при этом глубже разобрались в переходах из состояния в состояние, совершаемых системой. Существует подробно разработанная терминология для выделения важных типов стохастических матриц, которые мы сейчас рассмотрим; мы не будем пользоваться этой терминологией. Эта терминология вряд ли была бы создана, если бы окончательные результаты и их значение для эргодической теории были известны раньше.

Приведенная выше схема для матрицы иллюстрирующая разбиение состояний на эргодические классы, верна также для матрицы где пределы (2.11) и однако клетка является здесь также нулевой. В каждой клетке все ее строки одинаковы:

Лежащая под этой клеткой часть строки, соответствующей как нибудь состоянию из пропорциональна строке этой клетки с коэффициентом пропорциональности

Случай д). Предел в теореме 2.1 не зависит от тогда и только тогда, когда имеется единственный эргодический класс. Про этот случай

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

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

тогда и только тогда, когда каждый из эргодических классов не содержит циклических подклассов.

Случай ж). Предел в теореме 2.1 положителен при всех тогда и только тогда, когда все состояния являются существенными и имеется единственный эргодический класс. Элементы не зависят в этом случае от

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

Случай г). при всех (это условие остается, конечно, выполненным, как бы ни перенумеровать состояния). При таком условии не может быть циклических подклассов, так что в силу е)

при всех Таким образом, в этом случае можно заменить предел по Чезаро в теореме 2.1 на обычный предел. Однако использованное здесь условие возможности такой замены может быть значительно ослаблено.

Случай и). Если то матрица все ее степени, а следовательно, и предельная матрица являются симметрическими матрицами. Это условие также не нарушится, если перенумеровать по-другому состояния системы. В этом случае в каждом из эргодических классов не может быть больше двух циклических подклассов и совсем не может быть несущественных состояний (в противном случае матрица не будет симметрической). Поэтому, если предположить дополнительно, что ни для одного из классов не равно 2, то

Так как матрица симметрична, то отсюда следует, что

где число состояний в классе В частности, если имеется только один эргодический класс, то

Случай к). В некоторых приложениях основная стохастическая матрица удовлетворяет условию

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

не может быть несущественных состояний (эти состояния дают в матрице нулевой столбец). Соотношение (2.11) переходит здесь в соотношение

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

Возможные стационарные распределения вероятностей полностью описываются следующей теоремой.

Теорема 2.4. При любом величины [определяемые соотношением (2.11)] образуют стационарное распределение вероятностей. Обратно, любое стационарное распределение вероятностей является линейной комбинацией (с неотрицательными коэффициентами, равными в сумме 1) этих распределений и, более того, линейной комбинацией тех из распределений, для которых Вообще, любое решение системы уравнений

является линейной комбинацией этих распределений с

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

Чтобы доказать сформулированную теорему, заметим, что в силу теоремы т. е.

и что поэтому является стационарным распределением вероятностей. Обратно, если стационарное распределение вероятностей, то для любых

а, следовательно, также и

Поэтому

и эти соотношения показывают, что является линейной комбинацией строк матрицы (с коэффициентами что и требовалось доказать.

Эти соображения применимы и в более общем случае, когда вероятности заменены любым набором чисел удовлетворяющих (2.14).

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

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

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

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

и, действительно, эти выражения удовлетворяют уравнениям для Следовательно,

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