Уравнение чепмена колмогорова для цепей маркова примеры

Марковские случайные процессы. Уравнения Колмогорова для вероятностей состояний.

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

Большой класс случайных процессов составляют процессы без последействия, которые в математике называют марковскими процессами в честь Андрея Андреевича Маркова — старшего (1856 — 1922), выдающегося русского математика, разработавшего основы теории таких процессов.

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

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

Марковские процессы делятся на два класса:

· дискретные марковские процессы (марковские цепи);

· непрерывные марковские процессы.

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

Непрерывным марковским процессомназывается случайный процесс, при котором смена дискретных состояний происходит в случайные моменты времени.

Рассмотрим ситуацию, когда моделируемый процесс обладает следующими особенностями.

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

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

Известны вероятности перехода системы за один шаг из состояния в состояние .

Цель моделирования: определить вероятности состояний системы после -го шага.

Обозначим эти вероятности (не путать с вероятностями ).

Если в системе отсутствует последействие, то есть вероятности не зависят от предыстории нахождения системы в состоянии , а определяются только этим состоянием, то описанная ситуация соответствует модели дискретной марковской цепи.

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

Значения обычно сводятся в матрицу переходных вероятностей:

Значения могут также указываться на графе состояний системы. На рис. показан размеченный граф для четырех состояний системы. Обычно вероятности переходов «в себя» — , и т. д. на графе состояний можно не проставлять, так как их значения дополняют до 1 сумму переходных вероятностей, указанных на ребрах (стрелках), выходящих из данного состояния.

Не указываются также нулевые вероятности переходов. Например, на рис. это вероятности , и др.

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

где — вероятность -го состояния системы после -го шага, ;

— вероятность -го состояния системы после -го шага, ;

— число состояний системы;

-переходные вероятности.

Рис.Размеченный граф состояний системы

Для неоднородной марковской цепи вероятности состояний системы находятся по формуле:

где — значения переходных вероятностей для -го шага.

Сформулируем методику моделирования по схеме дискретных марковских процессов (марковских цепей).

1. Зафиксировать исследуемое свойство системы.

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

2. Определить конечное число возможных состояний системы и убедиться в правомерности моделирования по схеме дискретных марковских процессов.

3. Составить и разметить граф состояний.

4. Определить начальное состояние.

5. По рекуррентной зависимости определить искомые вероятности.

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

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

Поэтому вместо переходных вероятностей вводятся в рассмотрение плотности вероятностей переходов :

где — вероятность того, что система, находившаяся в момент времени в состоянии за время перейдет в состояние .

С точностью до бесконечно малых второго порядка из приведенной формулы можно представить:

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

Целью моделирования,как и в случае дискретных процессов, является определение вероятностей состояний системы Эти вероятности находятся интегрированием системы дифференциальных уравнений Колмогорова.

Сформулируем методику моделирования по схеме непрерывных марковских процессов.

1. Определить состояния системы и плотности вероятностей переходов .

2. Составить и разметить граф состояний.

3. Составить систему дифференциальных уравнений Колмогорова. Число уравнений в системе равно числу состояний. Каждое уравнение формируется следующим образом.

4. B левой части уравнения записывается производная вероятности -го состоянии

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

6. Определить начальные условия и решить систему дифференциальных уравнений.

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

Рис. Размеченный граф состояний

Очевидно, .

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

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

Дата добавления: 2015-04-03 ; просмотров: 7822 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Краткое введение в цепи Маркова

В 1998 году Лоуренс Пейдж, Сергей Брин, Раджив Мотвани и Терри Виноград опубликовали статью «The PageRank Citation Ranking: Bringing Order to the Web», в которой описали знаменитый теперь алгоритм PageRank, ставший фундаментом Google. Спустя чуть менее двух десятков лет Google стал гигантом, и даже несмотря на то, что его алгоритм сильно эволюционировал, PageRank по-прежнему является «символом» алгоритмов ранжирования Google (хотя только немногие люди могут действительно сказать, какой вес он сегодня занимает в алгоритме).

С теоретической точки зрения интересно заметить, что одна из стандартных интерпретаций алгоритма PageRank основывается на простом, но фундаментальном понятии цепей Маркова. Из статьи мы увидим, что цепи Маркова — это мощные инструменты стохастического моделирования, которые могут быть полезны любому эксперту по аналитическим данным (data scientist). В частности, мы ответим на такие базовые вопросы: что такое цепи Маркова, какими хорошими свойствами они обладают, и что с их помощью можно делать?

Краткий обзор

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

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

Что такое цепи Маркова?

Случайные переменные и случайные процессы

Прежде чем вводить понятие цепей Маркова, давайте вкратце вспомним базовые, но важные понятия теории вероятностей.

Во-первых, вне языка математики случайной величиной X считается величина, которая определяется результатом случайного явления. Его результатом может быть число (или «подобие числа», например, векторы) или что-то иное. Например, мы можем определить случайную величину как результат броска кубика (число) или же как результат бросания монетки (не число, если только мы не обозначим, например, «орёл» как 0, а «решку» как 1). Также упомянем, что пространство возможных результатов случайной величины может быть дискретным или непрерывным: например, нормальная случайная величина непрерывна, а пуассоновская случайная величина дискретна.

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

Разные виды случайных процессов (дискретные/непрерывные в пространстве/времени).

Марковское свойство и цепь Маркова

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

Одно из свойств, сильно упрощающее исследование случайного процесса — это «марковское свойство». Если объяснять очень неформальным языком, то марковское свойство сообщает нам, что если мы знаем значение, полученное каким-то случайным процессом в заданный момент времени, то не получим никакой дополнительной информации о будущем поведении процесса, собирая другие сведения о его прошлом. Более математическим языком: в любой момент времени условное распределение будущих состояний процесса с заданными текущим и прошлыми состояниями зависит только от текущего состояния, но не от прошлых состояний (свойство отсутствия памяти). Случайный процесс с марковским свойством называется марковским процессом.

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

На основании этого определения мы можем сформулировать определение «однородных цепей Маркова с дискретным временем» (в дальнейшем для простоты мы их будем называть «цепями Маркова»). Цепь Маркова — это марковский процесс с дискретным временем и дискретным пространством состояний. Итак, цепь Маркова — это дискретная последовательность состояний, каждое из которых берётся из дискретного пространства состояний (конечного или бесконечного), удовлетворяющее марковскому свойству.

Математически мы можем обозначить цепь Маркова так:

где в каждый момент времени процесс берёт свои значения из дискретного множества E, такого, что

Тогда марковское свойство подразумевает, что у нас есть

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

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

Характеризуем динамику случайности цепи Маркова

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

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

Однако благодаря марковскому свойству динамику цепи Маркова определить довольно просто. И в самом деле. нам нужно определить только два аспекта: исходное распределение вероятностей (то есть распределение вероятностей в момент времени n=0), обозначаемое

и матрицу переходных вероятностей (которая даёт нам вероятности того, что состояние в момент времени n+1 является последующим для другого состояния в момент n для любой пары состояний), обозначаемую

Если два этих аспекта известны, то полная (вероятностная) динамика процесса чётко определена. И в самом деле, вероятность любого результата процесса тогда можно вычислить циклически.

Пример: допустим, мы хотим знать вероятность того, что первые 3 состояния процесса будут иметь значения (s0, s1, s2). То есть мы хотим вычислить вероятность

Здесь мы применяем формулу полной вероятности, гласящую, что вероятность получения (s0, s1, s2) равна вероятности получения первого s0, умноженного на вероятность получения s1 с учётом того, что ранее мы получили s0, умноженного на вероятность получения s2 с учётом того, что мы получили ранее по порядку s0 и s1. Математически это можно записать как

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

получив таким образом

Так как они полностью характеризуют вероятностную динамику процесса, многие сложные события можно вычислить только на основании исходного распределения вероятностей q0 и матрицы переходной вероятности p. Стоит также привести ещё одну базовую связь: выражение распределения вероятностей во время n+1, выраженное относительно распределения вероятностей во время n

Цепи Маркова в конечных пространствах состояний

Представление в виде матриц и графов

Здесь мы допустим, что во множестве E есть конечное количество возможных состояний N:

Тогда исходное распределение вероятностей можно описать как вектор-строку q0 размером N, а переходные вероятности можно описать как матрицу p размером N на N, такую что

Преимущество такой записи заключается в том, что если мы обозначим распределение вероятностей на шаге n вектором-строкой qn, таким что его компоненты задаются

тогда простые матричные связи при этом сохраняются

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

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

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

Динамику случайности цепи Маркова в конечном пространстве состояний можно с лёгкостью представить как нормированный ориентированный граф, такой что каждый узел графа является состоянием, а для каждой пары состояний (ei, ej) существует ребро, идущее от ei к ej, если p(ei,ej)>0. Тогда значение ребра будет той же вероятностью p(ei,ej).

Пример: читатель нашего сайта

Давайте проиллюстрируем всё это простым примером. Рассмотрим повседневное поведение вымышленного посетителя сайта. В каждый день у него есть 3 возможных состояния: читатель не посещает сайт в этот день (N), читатель посещает сайт, но не читает пост целиком (V) и читатель посещает сайт и читает один пост целиком (R ). Итак, у нас есть следующее пространство состояний:

Допустим, в первый день этот читатель имеет вероятность 50% только зайти на сайт и вероятность 50% посетить сайт и прочитать хотя бы одну статью. Вектор, описывающий исходное распределение вероятностей (n=0) тогда выглядит так:

Также представим, что наблюдаются следующие вероятности:

• когда читатель не посещает один день, то имеет вероятность 25% не посетить его и на следующий день, вероятность 50% только посетить его и 25% — посетить и прочитать статью
• когда читатель посещает сайт один день, но не читает, то имеет вероятность 50% снова посетить его на следующий день и не прочитать статью, и вероятность 50% посетить и прочитать
• когда читатель посещает и читает статью в один день, то имеет вероятность 33% не зайти на следующий день (надеюсь, этот пост не даст такого эффекта!), вероятность 33% только зайти на сайт и 34% — посетить и снова прочитать статью

Тогда у нас есть следующая переходная матрица:

Из предыдущего подраздела мы знаем как вычислить для этого читателя вероятность каждого состояния на следующий день (n=1)

Вероятностную динамику этой цепи Маркова можно графически представить так:

Представление в виде графа цепи Маркова, моделирующей поведение нашего придуманного посетителя сайта.

Свойства цепей Маркова

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

Разложимость, периодичность, невозвратность и возвратность

В этом подразделе давайте начнём с нескольких классических способов характеризации состояния или целой цепи Маркова.

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

Иллюстрация свойства неразложимости (несокращаемости). Цепь слева нельзя сократить: из 3 или 4 мы не можем попасть в 1 или 2. Цепь справа (добавлено одно ребро) можно сократить: каждого состояния можно достичь из любого другого.

Состояние имеет период k, если при уходе из него для любого возврата в это состояние нужно количество этапов времени, кратное k (k — наибольший общий делитель всех возможных длин путей возврата). Если k = 1, то говорят, что состояние является апериодическим, а вся цепь Маркова является апериодической, если апериодичны все её состояния. В случае неприводимой цепи Маркова можно также упомянуть, что если одно состояние апериодическое, то и все другие тоже являются апериодическими.

Иллюстрация свойства периодичности. Цепь слева периодична с k=2: при уходе из любого состояния для возврата в него всегда требуется количество шагов, кратное 2. Цепь справа имеет период 3.

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

Иллюстрация свойства возвратности/невозвратности. Цепь слева имеет такие свойства: 1, 2 и 3 невозвратны (при уходе из этих точек мы не можем быть абсолютно уверены, что вернёмся в них) и имеют период 3, а 4 и 5 возвратны (при уходе из этих точек мы абсолютно уверены, что когда-нибудь к ним вернёмся) и имеют период 2. Цепь справа имеет ещё одно ребро, делающее всю цепь возвратной и апериодической.

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

Стационарное распределение, предельное поведение и эргодичность

В этом подразделе мы рассмотрим свойства, характеризующие некоторые аспекты (случайной) динамики, описываемой цепью Маркова.

Распределение вероятностей π по пространству состояний E называют стационарным распределением, если оно удовлетворяет выражению

Так как у нас есть

Тогда стационарное распределение удовлетворяет выражению

По определению, стационарное распределение вероятностей со временем не изменяется. То есть если исходное распределение q является стационарным, тогда оно будет одинаковых на всех последующих этапах времени. Если пространство состояний конечно, то p можно представить в виде матрицы, а π — в виде вектора-строки, и тогда мы получим

Это снова выражает тот факт, что стационарное распределение вероятностей со временем не меняется (как мы видим, умножение справа распределения вероятностей на p позволяет вычислить распределение вероятностей на следующем этапе времени). Учтите, что неразложимая цепь Маркова имеет стационарное распределение вероятностей тогда и только тогда, когда одно из её состояний является положительным возвратным.

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

Ещё раз подчеркнём тот факт, что мы не делаем никаких допущений об исходном распределении вероятностей: распределение вероятностей цепи сводится к стационарному распределению (равновесному распределению цепи) вне зависимости от исходных параметров.

Наконец, эргодичность — это ещё одно интересное свойство, связанное с поведением цепи Маркова. Если цепь Маркова неразложима, то также говорится, что она «эргодическая», потому что удовлетворяет следующей эргодической теореме. Допустим, у нас есть функция f(.), идущая от пространства состояний E к оси (это может быть, например, цена нахождения в каждом состоянии). Мы можем определить среднее значение, перемещающее эту функцию вдоль заданной траектории (временное среднее). Для n-ных первых членов это обозначается как

Также мы можем вычислить среднее значение функции f на множестве E, взвешенное по стационарному распределению (пространственное среднее), которое обозначается

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

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

Вернёмся к примеру с читателем сайта

Снова рассмотрим пример с читателем сайта. В этом простом примере очевидно, что цепь неразложима, апериодична и все её состояния положительно возвратны.

Чтобы показать, какие интересные результаты можно вычислить с помощью цепей Маркова, мы рассмотрим среднее время возвратности в состояние R (состояние «посещает сайт и читает статью»). Другими словами, мы хотим ответить на следующий вопрос: если наш читатель в один день заходит на сайт и читает статью, то сколько дней нам придётся ждать в среднем того, что он снова зайдёт и прочитает статью? Давайте попробуем получить интуитивное понятие о том, как вычисляется это значение.

Сначала мы обозначим

Итак, мы хотим вычислить m(R,R). Рассуждая о первом интервале, достигнутом после выхода из R, мы получим

Однако это выражение требует, чтобы для вычисления m(R,R) мы знали m(N,R) и m(V,R). Эти две величины можно выразить аналогичным образом:

Итак, у нас получилось 3 уравнения с 3 неизвестными и после их решения мы получим m(N,R) = 2.67, m(V,R) = 2.00 и m(R,R) = 2.54. Значение среднего времени возвращения в состояние R тогда равно 2.54. То есть с помощью линейной алгебры нам удалось вычислить среднее время возвращения в состояние R (а также среднее время перехода из N в R и среднее время перехода из V в R).

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

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

Стационарное распределение в примере с читателем сайта.

Можно также заметить, что π( R ) = 1/m(R,R), и если немного поразмыслить, то это тождество довольно логично (но подробно об этом мы говорить не будем).

Поскольку цепь неразложима и апериодична, это означает, что в длительной перспективе распределение вероятностей сойдётся к стационарному распределению (для любых исходных параметров). Иными словами, каким бы ни было исходное состояние читателя сайта, если мы подождём достаточно долго и случайным образом выберем день, то получим вероятность π(N) того, что читатель не зайдёт на сайт в этот день, вероятность π(V) того, что читатель зайдёт, но не прочитает статью, и вероятность π® того, что читатель зайдёт и прочитает статью. Чтобы лучше уяснить свойство сходимости, давайте взглянем на следующий график, показывающий эволюцию распределений вероятностей, начинающихся с разных исходных точек и (быстро) сходящихся к стационарному распределению:

Визуализация сходимости 3 распределений вероятностей с разными исходными параметрами (синяя, оранжевая и зелёная) к стационарному распределению (красная).

Классический пример: алгоритм PageRank

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

Произвольный веб-пользователь

PageRank пытается решить следующую задачу: как нам ранжировать имеющееся множество (мы можем допустить, что это множество уже отфильтровано, например, по какому-то запросу) с помощью уже существующих между страницами ссылок?

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

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

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

Искусственный пример

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

Ради понятности вероятности каждого перехода в показанной выше анимации не показаны. Однако поскольку подразумевается, что «навигация» должна быть исключительно случайной (это называют «случайным блужданием»), то значения можно легко воспроизвести из следующего простого правила: для узла с K исходящими ссылками (странице с K ссылками на другие страницы) вероятность каждой исходящей ссылки равна 1/K. То есть переходная матрица вероятностей имеет вид:

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

Сделав так, мы получим следующие значения PageRank (значения стационарного распределения) для каждой страницы

Значения PageRank, вычисленные для нашего искусственного примера из 7 страниц.

Тогда ранжирование PageRank этого крошечного веб-сайта имеет вид 1 > 7 > 4 > 2 > 5 = 6 > 3.

Выводы

Основные выводы из этой статьи:

• случайные процессы — это наборы случайных величин, часто индексируемые по времени (индексы часто обозначают дискретное или непрерывное время)
• для случайного процесса марковское свойство означает, что при заданном текущем вероятность будущего не зависит от прошлого (это свойство также называется «отсутствием памяти»)
• цепь Маркова с дискретным временем — это случайные процессы с индексами дискретного времени, удовлетворяющие марковскому свойству
• марковское свойство цепей Маркова сильно облегчает изучение этих процессов и позволяет вывести различные интересные явные результаты (среднее время возвратности, стационарное распределение…)
• одна из возможных интерпретаций PageRank (не единственная) заключается в имитации веб-пользователя, случайным образом перемещающегося от страницы к странице; при этом показателем ранжирования становится индуцированное стационарное распределение страниц (грубо говоря, на самые посещаемые страницы в устоявшемся состоянии должны ссылаться другие часто посещаемые страницы, а значит, самые посещаемые должны быть наиболее релевантными)

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

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

Марковские цепи с непрерывным временем

Уравнения Колмогорова

На практике значительно чаще встречаются ситуации, когда переходы системы из состояния в состояние происходит в случайные моменты времени, которые заранее указать невозможно: например, выход из строя любого элемента аппаратуры, окончание ремонта (восстановление) этого элемента. Для описания таких процессов в ряде случаев может быть с успехом применена схема марковского случайного процесса с дискретными состояниями и непрерывным временем – непрерывная цепь Маркова. Покажем, как выражаются вероятности состояний для такого процесса. Пусть S=. Обозначим через pi(t) — вероятность того, что в момент t система S будет находиться в состоянии ). Очевидно . Поставим задачу – определить для любого t pi(t). Вместо переходных вероятностей Pij введем в рассмотрение плотности вероятностей перехода

.

Если не зависит от t, говорят об однородной цепи, иначе — о неоднородной. Пусть нам известны для всех пар состояний (задан размеченный граф состояний). Оказывается, зная размеченный граф состояний можно определить p1(t),p2(t)..pn(t) как функции времени. Эти вероятности удовлетворяют определенного видадифференциальным уравнениям, (уравнения Колмогорова).

Интегрирование этих уравнений при известном начальном состоянии системы даст искомые вероятности состояний как функции времени. Заметим, чтоp1+p2+p3+p4=1 и можно обойтись тремя уравнениями.

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

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

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

Рассмотрим некоторую произвольную систему, граф состояний которой приведен на рис.1. Система имеет n состояний S₁,S₂. S_n. Процесс перехода из одного состояния в другое описывает­ся непрерывной цепью Маркова. Пусть P_i(t) — вероятность того, что в момент времени t система будет находиться в состоянии S_i (i=1,2,…,n). Поскольку система не может находиться одновременно в двух состояниях, то события, заключающиеся в нахождении системы в состояниях S₁,S₂,…,S_n, несовместны и образуют полную сис­тему событий. Отсюда следует

(51)

Это соотношение называется условием нормировки. Задача заключает­ся в определении вероятности любого состояния P_i(t) в любой мо­мент времени t.

Введем понятие вероятности перехода системы из состояния i, где она находилась в момент времени t, в состояние j за время Dt P_ij(t,Dt). Очевидно, что P_ij(t,Dt) представляет собой условную вероятность того, что в момент времени t + Dt система окажется в состоянии S_j при условии, что в момент времени t она находилась в состоянии S_i: p_ij(t,Dt)= p(S_j(t+Dt)/S_i(t)).

Предел отношения вероятности перехода p_ij(t,Dt) к длине интервала времени Dt назовем плотностью вероятности перехода

. (52)

Плотность вероятности перехода определим только для случаев i¹j.

Если l_ij(t)=const, то марковская цепь называется однородной. В противном случае, когда l_ij(t) являются функциями времени, цепь называется неоднородной. При расчетах вероятностей состояний марковской цепи предполагается, что все эти плотности вероятнос­тей переходов l_ij известны. Если у каждой дуги графа состояний системы проставить плотность вероятности перехода по данной дуге, то полученный граф назовем размеченным графом состояний (см.рис.1). Уравнения Колмогорова составляются в соответствии с разме­ченным графом состояний. Рассмотрим фрагмент размеченного графа состояний (рис.1), обведенный штрихпунктирной линией. Отбро­сим вначале дуги, изображенные пунктиром, и определим вероятность нахождения системы в состоянии S_i в момент времени t+Dt. С уче­том того, что вершина S_iсвязана только с вершинами S_k и S_j, ука­занное событие будет иметь место в двух случаях:

— система находилась в состоянии S_i в момент времени t и за время Dt из этого состояния не вышла;

— система находилась в состояния s_k в момент времени t и за время Dt перешла из S_kв S_i.

Если отрезок Dt достаточно мал, то вероятность перехода p_ij(t,Dt) может быть определена приближенно с помощью (52)

С учетом (53) и свойства марковости процесса вероятность первого случая (отсутствие перехода по дуге (S_i,S_j))

Вероятность второго случая с учетом (53)

Тогда можно определить искомую вероятность как

(54)

Переходя в (53) к пределу при Dt ® 0, получим

. (55)

Теперь добавим к вершине Si дуги, обозначенные на рис.1 пункти­ром. Тогда при вычислении p_i(t+Dt) необходимо учитывать возможный переход из S_i в S_j и S_r и переходы из S_k и S_l в S_i. В этом случае

Повторяя вышеописанные рассуждения, получим

. (56)

На основании (55) и (56) можно сформулировать правила сос­тавления уравнений Колмогорова по размеченному графу состояний непрерывной марковской цепи:

1. Система дифференциальных уравнений Колмогорова имеет форму Коши. Каждое уравнение составляется с помощью рассмотрения ве­роятности состояния, представленного соответствующей вершиной в размеченном графе. Число уравнений системы равно числу вершин графа.

2. Число слагаемых правой части каждого уравнения равно чис­лу дуг, инцидентных соответствующей вершине.

3. Дугам с положительной инциденцией соответствуют отрица­тельные слагаемые, а дугам с отрицательной инциденцией — положи­тельные.

4. Каждое слагаемое правой части равно произведению вероят­ности состояния, соответствующего началу рассматриваемой дуги, на плотность вероятности перехода по данной дуге.

Начальные условия для системы уравнений Колмогорова опреде­ляются начальным состоянием системы. Например, если начальное состояние было S₂ , то начальные условия имеют вид: p₁(0)=0; р₂(0)=1; р₃(0)=0;…;р_n(0)=0. Уравнения (55) и (56) были вы­ведены для общего случая неоднородной марковской цепи. Для одно­родной марковской цепи все l_ij(i,j=l,…,n) постоянны.

Рассмотрим одно важное свойство уравнений Колмогорова (55), которое может быть представлено в виде

, (57)

где — n-мерный вектор вероятностей состояний системы; р =1(t),…,p_n(t)>; L — n´n-матрица плотностей перехода.

В соответствии с вышеописанными правилами составления урав­нений Колмогорова одна и та же плотность вероятности перехода l_ij будет входить в одно из уравнений со знаком «+», а в другое — со знаком «-«, поскольку для двух смежных вершин дуга, соединяющая их, будет обладать положительной инциденцией по отношению к одной вершине и отрицательной по отношению к другой. Это приведет к то­му, что сумма всех элементов в каждом столбце матрицы будет равна нулю. Тогда любая строка матрицы L будет равна сумме остальных строк. Следовательно, матрица L является всегда вырожденной. Бо­лее строго это свойство доказывается в [7].

Рассмотрим систему с размеченным графом состояний, изобра­женным на рис.2. Система уравнений Колмогорова и матрица L для этого случая в соответствии с правилами 1-4 будут иметь вид:

Исключение любого уравнения из этой системы нарушает указанное соотношение для строк матрицы L, следовательно, ранг матрицы L будет равен n-1. Для того чтобы система уравнений Колмогорова имела единственное решение при заданных начальных условиях, не­обходимо исключить любое из уравнений системы (58) и заме­нить его условием нормировки (51).

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

Получить это решение можно с помощью любых численных методов (например, Рунге-Кутта, Эйлера-Коши и т.д.), реализуемых на ЭВМ. Только в самых простых случаях система уравнений Колмогорова мо­жет быть проинтегрирована в квадратурах. В большинстве практичес­ких случаев для расчета вероятностей состояний используются не решения систем уравнений Колмогорова в любой момент времени, а асимптотические оценки этих решений при t®¥.

Лекция 15. Предельные вероятности состояний. Простейший поток событий.

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

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

Определение 2. Пусть марковский процесс характеризуется ве­роятностями перехода из состояния i в состояние j за время t

Процесс называется транзитивным, если существует такое t>0, что p_ij(t)>0 (0£i£n; 0£j£n). Из определений 1 и 2 следует, что процессы в марковских цепях с эргодическим свойством являются транзитивными.

Теорема Маркова. Для любого транзитивного марковского процесса предел существует и не зависит от начального состояния i.

Это означает, что при t®¥ в системе устанавливается неко­торый предельный стационарный режим, характеризующийся постоян­ной, не зависящей от времени, вероятностью каждого из состояний системы. При этом данная вероятность представляет собой среднее относительное время пребывания системы в данном состоянии. Это значит, что если время работы всей системы 100 ч, а вероятность состояния S1 равна p1=0,15, то система будет находиться в состоянии S1 в среднем 15 ч.

Пределы, к которым стремятся вероятности каждого из состоя­ний марковской цепи с эргодическим свойством при t®¥, называ­ются предельными вероятностями. При рассмотрении СМО мы будем иметь дело только с эргодическими марковскими цепями. Пусть V — некоторое подмножество множества состояний системы S , а V’ — его дополнение до S . Если множество V обладает эргодическим свойс­твом и ни из одного состояния множества V нельзя перейти ни в од­но из состояний множества V’, то множество называется замкнутым или эргодическим множеством. Эргодические системы состоят из од­ного единственного эргодического множества (S=V, V’=Æ) и называются поэтому неразложимыми. Если в системе S множество V’¹Æ или в этой системе можно выделить несколько эргодических множеств S = V₁ÈV₂È…ÈV_n, то такая система называется разложимой. Примеры таких систем приведены на рис.3.

На рис.3,а представлена сис­тема с двумя эргодическими множест­вами V₁=(S₂,S₃,S₄) и V₂(S₅,S₆). На рис.3, б эргодическое множество состоит лишь из одного состояния (S₄). Если эргодическое множест­во состоит лишь из одного состоя­ния, то это состояние называется поглощающим, так как попав в не­го однажды, процесс остается нав­сегда в поглощающем состоянии. Ха­рактерная особенность графа состо­яний неразложимой эргодической мар­ковской системы заключается в том, что каждой вершине этого графа ин­цидентны дуги как с положительной, так и с отрицательной инцидент­ностью (т.е. у каждой вершины име­ются дуги, направленные как к вер­шине, так и от нее, см., например, рис. 1 и 2).

Вычисление предельных вероят­ностей состояний для таких систем упрощается в связи с тем, что, поскольку все эти вероятности яв­ляются постоянными величинами, то их производные по времени рав­ны 0 (dp_i/dt=0 для всех i). Поэтому левые части системы уравнений Колмогорова (58) приравниваются нулю и она превращается в систе­му линейных алгебраических уравнений

. (59)

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

(60)

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

Пример. Для системы, изображенной на рис.2, из уравнений Колмогорова (58) следует

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

Предельные вероятности состояний используются в ТМО значи­тельно чаще, чем решения уравнений Колмогорова, причем, зная ре­шение системы уравнений Колмогорова, можно определить момент окончания переходного процесса изменения вероятностей состояний во времени. Это дает возможность рассчитать, промежуток времени начиная от включения системы в работу, по истечении которого ве­роятности состояний достигнут своих предельных значений и будут справедливы оценки, использующие эти значения. В заключение этого параграфа рассмотрим один частный, но практически очень важный класс марковских процессов, широко применяемых при исследовании СМО. Это — процессы «размножения и гибели». К ним относятся мар­ковские цепи, представимые размеченным графом, который состоит из вытянутой цепочки состояний, изображенной на рис.4.

Матрица плотностей вероятностей переходов такой системы яв­ляется якобиевой (тридиагональной):

Рассматривая начальное состояние S₀ , получим в соответствии с (59)

Для состояния S₁ имеем

Вычитая из (63) равенство (62), получим

Продолжая этот процесс до n-гo состояния включительно, получим

Из (62) теперь можно выразить p₁ через р₀:

Подставляя (64) в (65), получим

Очевидно, что для произвольного k (1£k£n) будет справедливо вы­ражение

. (66)

В соответствии с (66) и размеченным графом состояний, представленным на рис.4, можно сформулировать правило, с по­мощью которого можно выразить предельные вероятности состояний процесса «размножения и гибели» через вероятность начального сос­тояния р₀. Это правило гласит: вероятность произвольного состоя­ния p_k (l£k£n) равна вероятности начального состояния р₀, умно­женной на дробь, числитель которой равен произведению плотностей вероятностей перехода для дуг, переводящих состояние системы сле­ва направо, а знаменатель — произведение плотностей вероятностей перехода справа налево от начального до k-гo состояний включи­тельно.

Вероятность р₀ находится из условия нормировки и выражений (66) следующим образом:

(67)

Выражения (66) и (67) полностью определяют предельные вероят­ности процесса «размножения и гибели».

Цепи Маркова с непрерывным временем являются математическими моделями СМО. Для анализа СМО необходимо также иметь математичес­кие модели входных потоков заявок на обслуживание. Эти математи­ческие модели представляют собой потоки события, являющиеся от­дельным классом случайных процессов. Потоком событий называется последовательность однородных событий, следующих одно за другим в случайные моменты времени. Этот поток количественно может быть охарактеризован числом событий x(t), имевших место в течение определенного промежутка времени (0,t). Тогда случайный поток со­бытий можно определить как случайный процесс x(t) (t³0), в кото­ром функция x(t) является неубывающей функцией времени, способной принимать лишь целые неотрицательные значения. Иными словами, график функции x(t) является ступенчатой кривой с постоянной вы­сотой ступеньки, равной единице, причем ширина ступеньки — слу­чайная величина. Примерами таких потоков могут служить: поток вызовов на АТС, поток запросов в вычислительный центр коллективного пользования и т.п. Моменты появления событий можно отобразить точками на временной оси, поэтому поток событий часто представляется и как последовательность таких точек. Поток событий называется регулярным, если события следуют одно за другим через одинаковые, строго фиксированные промежутки времени.

В ТМО такие потоки практи­чески, не используются, однако они представляют интерес как предельный случай. Значительно чаще имеют дело с потоками, в которых времена поступления со­бытий и, следовательно, проме­жутки времени между ними являются случайными (иррегулярными). При этом наиболее простые рас­четные соотношения получаются при использовании простейших потоков событий, которые широко применяются при исследовании CMО.

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

1. Поток событий называется стационарным, если вероятность p_k(l) того, что за отрезок времени t произойдет k событий, зави­сит только от его длины t и не зависит от его расположения на временной оси, т.е. p_k(t’,t’+t)=p_k(t). Из определения однородной марковской цепи следует, что стационар­ность — это однородность потока по времени.

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

3. Поток событий называется потоком без последействия, если вероятность попадания событий на некоторый участок временной оси не зависит от того, сколько событий попало на другие участки. Иными словами, условная вероятность наступления k событий за про­межуток времени (t’,t’+t), вычисленная при любом условии чередо­вания событий до момента t’, равна безусловной вероятности p_k(t) того же события, т.е.

p[(t’,t’+t),k/(t»,t»+t),m]=p_k(t),tÇt_k=Æ, t» T), т.е. вероятность того, что случайная величина Т при­мет значение, меньшее чем t. Для этого необходимо определить ве­роятность того, что в интервал времени t, отсчитываемый от момента t₀ появления некоторого события, попадет еще хотя бы одно событие (см.рис.5,б). Эту вероятность можно определить, зная вероятность отсутствия событий в интервале t, равную вероятности p₀(t) состояния S₀ на графе рис.5, а. В соответствии с (72)

F(t)=p(t>T)=1-e -lt , t>0 . (73)

Дифференцируя (73) по времени, получим искомый закон распреде­ления

(74)

Закон распределения (74) называется показательным (экспоненци­альным). Определим первые два момента показательного распределе­ния:

(75)

(76)

Интегрируя (75) и (76) по частям, получим

. (77)

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

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

Разлагая e -lDt в ряд по степеням lDt и ограничиваясь только первой степенью (в силу малости Dt), получим

Выражение в правой части (78) называется элементом вероятности появления события в простейшем потоке.

Марковские цепи являются математи­ческими моделями некоторых реальных систем, а потоки событий яв­ляются моделями внешних воздействий на эти системы. В дальнейшем будем считать, что переход системы из одного состояния i в другое j в соответствии с размеченным графом состояний происходит под действием потока событий с интенсивностью l_ij, равной соответс­твующей плотности вероятности перехода. Эта интенсивность определяется как среднее число переходов из состояния i в состояние j за единицу времени.

Если все потоки событий являются пуассоновскими, то процесс в системе будет марковским.

Уравнения Колмогорова составляют основу аналитических моделей СМО. Их можно получить следующим образом.

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

(1)

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

Разделив выражение (1) на и перейдя к пределу при , получим

откуда следуют уравнения Колмогорова

В стационарном состоянии и уравнения Колмогорова составляют систему алгебраических уравнений, в которой -й узел представлен уравнением

(2)

Прибавляя к левой и правой частям уравнения (2) и учитывая что получаем т.е.

где — финальные вероятности.

Условия существования стационарного режима:

— цепь Маркова должна быть однородной;

— множество состояний системы должно быть эргодическим, т.е. из любого состояния Si можно за конечное число шагов перейти в состояниеSj .

Предельные вероятности состояний представляют собой среднее время пребывания системы в данном состоянии. Например, если у системы S три возможных состояния: S1, S2, S3 , причем их предельные вероятности равны 0.2, 0.3, 0.5, то это означает, что после перехода к установившемуся режиму система S в среднем две десятых времени будет находиться в состоянии S1, три десятых – в состоянии S2, половину времени – в S3.

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

Последнее изменение этой страницы: 2019-04-19; Просмотров: 451; Нарушение авторского права страницы