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

Биография Маркова

Марков Андрей Андреевич. 2 (14) июня 1856—20 июля 1922 — русский математик, специалист по теории чисел, теории вероятностей и математическому анализу.

С 1886 — адъюнкт, с 1890 — экстраординарный, а с 1896 — ординарный академик Императорской Санкт-Петербургской Академии Наук.

Андрей Марков родился в семье мелкого чиновника в Рязанской губернии. В 1878 окончил Петербургский университет со степенью кандидата и в том же году получил золотую медаль за работу "Об интегрировании дифференциальных уравнений при помощи непрерывных дробей". С 1880 — приват-доцент, с 1886 — профессор, а с 1905 — заслуженный профессор Петербургского университета.

Научные исследования Марков тесно примыкают по своей тематике к работам старших представителей Петербургской математической школы — П.Л. Чебышева, Е.И. Золотарева и А.Н. Коркина. Блестящих результатов в области теории чисел Марков достиг в магистерской диссертации "О бинарных квадратичных формах положительного определителя" (1880). Результаты, полученные им в этой работе, послужили основой дальнейших исследований в этой области в СССР и за рубежом. В 1905 вышел в отставку. В этом же году ему присвоено звание заслуженного профессора Петербургского университета. Написал около 70 работ по теории чисел, теории приближения функций, теории дифференциальных уравнений, теории вероятностей, в т. ч. и 2 классических произведения — "Исчисление конечных разностей" и "Исчисление вероятностей". Труды Маркова по теории чисел касаются главным образом теории неопределенных квадратичных форм. Почти все они посвящены нахождению экстремальных квадратичных форм данного определителя.

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

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

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

Он был материалистом и убежденным атеистом, бескомпромиссным борцом против религии. 12.02.1912 Марков подал в Синод прошение об отлучении его от церкви. Марков протестовал против решения царского правительства, отказывавшегося утвердить избрание А.М. Горького почетным членом Петербургской Академии Наук. АН СССР учредила премию им. А.А. Маркова за лучшие работы по математике. Именем Маркова назван кратер краевой зоны Луны.

Свой последний мемуар он представил Академии наук всего лишь за несколько месяцев до смерти. Тяжелый недуг свалил его в постель, и 20 июля 1922 г. он умер.

Цепи Маркова

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

Определение 6. Цепью Маркова называется последовательность испытаний, в каждом из которых появляется только одно из k несовместных событий A_i из полной группы. При этом условная вероятность p_ij(s) того, что в s –ом испытании наступит событие A_j при условии, что в (s – 1) – ом испытании наступило событие A_i, не зависит от результатов предшествующих испытаний.

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

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

Определение 8. Однородной называется цепь Маркова, если условная вероятность pij перехода системы из состояния i в состояние j не зависит от номера испытания. Вероятность p_ij называется переходной вероятностью.

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

 

 

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

Пример 7. По заданной матрице перехода построить граф состояний

 

 

Т. к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния. S1 0,2 0,7 S2 0,4 S4 0,6 0,5 0,1 0,5 S3.

На графе не отмечаются вероятности перехода системы из одного состояния в то же самое. При рассмотрении конкретных систем удобно сначала построить граф состояний, затем определить вероятность переходов системы из одного состояния в то же самое (исходя из требования равенства единице суммы элементов строк матрицы), а потом составить матрицу переходов системы. Пусть Pij(n) – вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r – некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое pij(1) = pij. Тогда вероятность Pij(n) может быть найдена по формуле, называемой равенством Маркова:

 

 

Здесь т – число шагов (испытаний), за которое система перешла из состояния i в состояние r. В принципе, равенство Маркова есть ни что иное как несколько видоизменная формула полной вероятности. Зная переходные вероятности (т.е. зная матрицу перехода Р1), можно найти вероятности перехода из состояния в состояние за два шага Pij(2), т.е. матрицу Р2, зная ее – найти матрицу Р3, и т.д. Непосредственное применений полученной выше формулы не очень удобно, поэтому, можно воспользоваться приемами матричного исчисления (ведь эта формула по сути – не что иное как формула перемножения двух матриц). Тогда в общем виде можно записать:

 

 

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

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

Задача, которую мы рассмотрим, интересна сама по себе, а отчасти рассматриваем мы ее из-за того, что ее изложение не требует введения большого количества новых терминов.

Рассмотрим задачу об осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 1).

Осел стоит между двумя копнами: "Рожь" и "Пшеница" (рис. 1). Каждую минуту он либо передвигается на десять метров в сторону первой копны (с вероятностью ), либо в сторону второй копны (с вероятностью ), либо остается там, где стоял (с вероятностью ); такое поведение называется одномерным случайным блужданием. Будем предполагать, что обе копны являются "поглощающими" в том смысле, что если осел подойдет к одной из копен, то он там и останется. Зная расстояние между двумя копнами и начальное положение осла, можно поставить несколько вопросов, например: у какой копны он очутится с большей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попасть туда?

 

Рис. 1

 

Чтобы исследовать эту задачу подробнее, предположим, что расстояние между копнами равно пятидесяти метрам и что наш осел находится в двадцати метрах от копны "Пшеницы". Если места, где можно остановиться, обозначить через ( — сами копны), то его начальное положение можно задать вектором , -я компонента которого равна вероятности того, что он первоначально находится в . Далее, по прошествии одной минуты вероятности его местоположения описываются вектором , а через две минуты — вектором . Ясно, что непосредственное вычисление вероятности его нахождения в заданном месте по прошествии минут становится затруднительным. Оказалось, что удобнее всего ввести для этого матрицу перехода.

 

Рис. 2

 

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

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

Нас будет интересовать следующее: можно ли попасть из одного данного состояния в другое, и если да, то за какое наименьшее время. Например, в задаче об осле из в можно попасть за три минуты и вообще нельзя попасть из в . Следовательно, в основном мы будем интересоваться не самими вероятностями , а тем, положительны они или нет. Тогда появляется надежда, что все эти данные удастся представить в виде орграфа, вершины которого соответствуют состояниям, а дуги указывают на то, можно ли перейти из одного состояния в другое за одну минуту. Более точно, если каждое состояние представлено соответствующей ему вершиной , то, проводя из в для тех и только тех вершин, для которых , мы и получим требуемый орграф. Кроме того, этот орграф можно определить при помощи его матрицы смежности, если заменить каждый ненулевой элемент матрицы на единицу. Мы будем называть этот орграф ассоциированным орграфом данной цепи Маркова. Ассоциированный орграф одномерного случайного блуждания, связанного с задачей об осле, изображен на (рис. 3).

Другой пример: если цепь Маркова имеет матрицу перехода, приведенную на рис. 4, то ассоциированный орграф этой цепи выглядит так, как показано на (рис. 5).

 

Рис. 3

 

Рис. 4

 

Рис. 5

 

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

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

Другой прием классификации состояний опирается на понятие периодичности состояний. Состояние цепи Маркова называется периодическим с периодом , если в можно вернуться только по истечении времени, кратного . Если такого не существует, то состояние называется непериодическим. Очевидно, что каждое состояние , для которого , непериодическое. Следовательно, каждое поглощающее состояние — непериодическое. В задаче об осле не только поглощающее состояние , но и все остальные являются непериодическими. С другой стороны, во втором примере (рис. 5) поглощающее состояние — единственное непериодическое состояние, поскольку имеют период два, а — период три. Используя терминологию орграфов, легко показать, что состояние является периодическим с периодом тогда и только тогда, если в ассоциированном орграфе длина каждой замкнутой орцепи, проходящей через , кратна .

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

Пример 8. Частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты t₁, t₂, t₃,...Частица может находиться в точках с целочисленными координатами 1, 2, 3, 4, 5; в точках 1 и 5 находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью q, если частицы не находятся у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка [1,5]. Найти матрицу перехода P и ей соответствующий граф.

Решение. Пусть Ei=(t),i = 1, 2, 3, 4, 5. Тогда граф перехода выглядит следующим образом:

 

Рис. 6

 

а матрица перехода –

 

 

Пример 9. Вероятности перехода за один шаг в цепях Маркова задаются матрицей:

 

 

Требуется:

а) найти число состояний;

б) установить, сколько среди них существенных и несущественных;

в) построить граф, соответствующий матрице P.

Решение.

а) 4 состояния.

б) состояния E₁, E₂ несущественны, поскольку остальные состояния достижимы из них, но E₁ недостижимо из E₄, а E₂ недостижимо из E₃; состояния E₃ и E₄ являются существенными.

 

Рис. 7. в)

Пример 10 (задача о скрещивании). В близко родственном скрещивании две особи, и среди их прямых потомков случайным образом выбираются две особи разного пола. Они вновь скрещиваются, и процесс этот продолжается бесконечно. Каждый родительский ген может передаваться с вероятностью 1/2, и последовательные испытания независимые. Имея три генотипа AA, Aа, аа для каждого родителя, мы можем различать шесть комбинаций родителей, которые пометим следующим образом:

 

У₁=ФФ*ФФб У₂= ФФ*Фаб У₃ = ФФ*ааб У₄ = Фа*Фаб У₅= Фа*ааб У₆=

аа*ааю

 

Найдите граф и матрицу перехода.

Решение.

 

 

Рассмотрим, какое потомство и с какой вероятностью может быть у особей разного пола, если они выбираются из E₂.

Пусть B_i= {i-й потомок}, i= 1, 2 и B₁,B₂ - разного пола, тогда варианты потомков и их вероятности можно найти по следующему графу:

 

Рис. 8

Получаем, что

 

 

Аналогично, находим и вероятности других переходов:

 

 

Тогда искомый граф перехода выглядит следующим образом:

Рис. 9

 

 

а матрица перехода –

 

 

Пример 11. Матрица вероятностей перехода цепи Маркова имеет вид:

 

 

Распределение по состояниям в момент времени t= 0 определяется вектором . Найти распределения по состояниям в момент t= 2.

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

 

Рис. 10

 

По этому графу находим распределение по состояниям в момент t= 2:

 

P(E1)= (0,6*(0,2)²+ 0,6*0,3*0,5+0,6*0,5*0,6)+(0,1*0,5*0,2+0,1*0,2*0,5

+0,1*0,3*0,6) +(0,3*0,6*0,2+(0,3)²*0,6)+(0,3*0,1*0,5)=0,437;

P(E2)= (0,1*(0,2)²+0,1*0,5*0,3+0,1*0,3*0,1)+0,6*0,3*0,2+0,6*0,2*0,3

+0,6*0,5*0,1)+(0,3*0,1* 0,2+(0,3)²*0,1+0,3*0,6*0,3)=0,193;

P(E3)= 0,37.

Пример 12. Доказать, что P⁽ⁿ⁾ = Pⁿ для двух состояний цепи Маркова.

Решение. Пусть цепь Маркова с двумя состояниями E₁ и E₂ задана своей матрицей перехода P:

 

 

Докажем утверждение методом математической индукции.

Пусть n= 2. Тогда

 

 

Вероятности перехода за два шага удобно находить по графу перехода:

 

Рис. 11

 

 

Следовательно, P⁽²⁾ = P², и первый шаг метода математической индукции выполняется. Предположим далее, что при проверяемое утверждение истинно, т.е. P^(k) = P^k, тогда матрица перехода за k+1 шаг P^(k+1) = P^(k) * P = P^k * P = P, что и требовалось доказать.