Схема Бернулли. Цепи Маркова (стр. 5 из 11)

Определение 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).