Матрица перехода однородной цепи маркова имеет вид. Однородные цепи маркова

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

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

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

Марковская цепь

Что все это значит? Давайте разбираться.

Основы

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

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

И выпишем количество появлений каждого из звеньев в тексте:

На картинке выше видно, что слово «fish» появляется в тексте в 4 раза чаще, чем каждое из других слов («One», «two», «red», «blue» ). То есть вероятность встретить в нашем корпусе слово «fish» в 4 раза выше, чем вероятность встретить каждое другое слово из приведенных на рисунке. Говоря на языке математики, мы можем определить закон распределения случайной величины и вычислить, с какой вероятностью одно из слов появится в тексте после текущего. Вероятность считается так: нужно разделить число появлений нужного нам слова в корпусе на общее число всех слов в нем. Для слова «fish» эта вероятность - 50%, так как оно появляется 4 раза в предложении из 8 слов. Для каждого из остальных звеньев эта вероятность равна 12,5% (1/8).

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

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

Суть определения

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

Любое предложение содержит эти невидимые «начало» и «конец», добавим их в качестве звеньев к нашему распределению:

Вернемся к определению, данному в начале статьи:

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

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

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

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

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

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

Представим эту информацию другим способом - каждому звену поставим в соответствие массив из всех слов, которые могут появиться в тексте после этого звена:

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

Пример. Начнем со слова «Start» . Далее выбираем слово «One» , так как по нашей схеме это единственное слово, которое может следовать за началом предложения. За словом «One» тоже может следовать только одно слово - «fish» . Теперь новое предложение в промежуточном варианте выглядит как «One fish» . Дальше ситуация усложняется - за «fish» могут с равной вероятностью в 25% идти слова «two», «red», «blue» и конец предложения «End» . Если мы предположим, что следующее слово - «two» , реконструкция продолжится. Но мы можем выбрать и звено «End» . В таком случае на основе нашей схемы будет случайно сгенерировано предложение, сильно отличающееся от корпуса - «One fish» .

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

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

Расширяем словарную базу

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

Возьмем еще четыре цитаты того же автора (также на английском, нам это не помешает):

«Today you are you. That is truer than true. There is no one alive who is you-er than you.»

«You have brains in your head. You have feet in your shoes. You can steer yourself any direction you choose. You’re on your own.»

«The more that you read, the more things you will know. The more that you learn, the more places you’ll go.»

«Think left and think right and think low and think high. Oh, the thinks you can think up if only you try.»

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

Проще всего это объясняется с точки зрения программы. Мы знаем, что для каждого звена существует набор слов, которые могут за ним следовать. А также, каждое слово характеризуется числом его появлений в тексте. Нам нужно каким-то образом зафиксировать всю эту информацию в одном месте; для этой цели лучше всего подойдет словарь, хранящий пары «(ключ, значение)». В ключе словаря будет записано текущее состояние системы, то есть одно из звеньев корпуса (например, «the» на картинке ниже); а в значении словаря будет храниться еще один словарь. Во вложенном словаре ключами будут слова, которые могут идти в тексте после текущего звена корпуса («thinks» и «more» могут идти в тексте после «the» ), а значениями - число появлений этих слов в тексте после нашего звена (слово «thinks» появляется в тексте после слова «the» 1 раз, слово «more» после слова «the» - 4 раза):

Перечитайте абзац выше несколько раз, чтобы точно разобраться. Обратите внимание, что вложенный словарь в данном случае - это та же гистограмма, он помогает нам отслеживать звенья и частоту их появления в тексте относительно других слов. Надо заметить, что даже такая словарная база очень мала для надлежащей генерации текстов на естественном языке - она должна содержать более 20 000 слов, а лучше более 100 000. А еще лучше - более 500 000. Но давайте рассмотрим ту словарную базу, которая получилась у нас.

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

То есть если текущим словом является слово «more» , после него могут с равной вероятностью в 25% идти слова «things» и «places» , и с вероятностью 50% - слово «that» . Но вероятности могут быть и все равны между собой:

Think:

Работа с окнами

До настоящего момента мы с вами рассматривали только окна размером в одно слово. Можно увеличить размер окна, чтобы генератор текста выдавал более «выверенные» предложения. Это значит, что чем больше окно, тем меньше будет отклонений от корпуса при генерации. Увеличение размера окна соответствует переходу цепи Маркова к более высокому порядку. Ранее мы строили цепь первого порядка, для окна из двух слов получится цепь второго порядка, из трех - третьего, и так далее.

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

Расширение привело к тому, что у каждого окна теперь только один вариант следующего состояния системы - что бы мы ни делали, мы всегда будем получать одно и то же предложение, идентичное нашему корпусу. Поэтому, чтобы экспериментировать с окнами, и чтобы генератор текста возвращал уникальный контент, запаситесь словарной базой от 500 000 слов.

Реализация на Python

Структура данных Dictogram

Dictogram (dict - встроенный тип данных словарь в Python) будет отображать зависимость между звеньями и их частотой появления в тексте, то есть их распределение. Но при этом она будет обладать нужным нам свойством словаря - время выполнения программы не будет зависеть от объема входных данных, а это значит, мы создаем эффективный алгоритм.

Import random class Dictogram(dict): def __init__(self, iterable=None): # Инициализируем наше распределение как новый объект класса, # добавляем имеющиеся элементы super(Dictogram, self).__init__() self.types = 0 # число уникальных ключей в распределении self.tokens = 0 # общее количество всех слов в распределении if iterable: self.update(iterable) def update(self, iterable): # Обновляем распределение элементами из имеющегося # итерируемого набора данных for item in iterable: if item in self: self += 1 self.tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Возвращаем значение счетчика элемента, или 0 if item in self: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # Другой способ: # random.choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Сгенерировать псевдослучайное число между 0 и (n-1), # где n - общее число слов random_int = random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # вывести "случайный индекс:", random_int for i in range(0, self.types): index += self] # вывести индекс if(index > random_int): # вывести list_of_keys[i] return list_of_keys[i]

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

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

Структура цепи Маркова

from histograms import Dictogram def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Просто присоединяем к уже существующему распределению markov_model].update(]) else: markov_model] = Dictogram(]) return markov_model

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

Структура цепи Маркова N-го порядка

from histograms import Dictogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Создаем окно window = tuple(data) # Добавляем в словарь if window in markov_model: # Присоединяем к уже существующему распределению markov_model.update(]) else: markov_model = Dictogram(]) return markov_model

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

Парсинг модели

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

From histograms import Dictogram import random from collections import deque import re def generate_random_start(model): # Чтобы сгенерировать любое начальное слово, раскомментируйте строку: # return random.choice(model.keys()) # Чтобы сгенерировать "правильное" начальное слово, используйте код ниже: # Правильные начальные слова - это те, что являлись началом предложений в корпусе if "END" in model: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice(model.keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) sentence = for i in range(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = random_weighted_word sentence.append(current_word) sentence = sentence.capitalize() return " ".join(sentence) + "." return sentence

Что дальше?

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

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

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

Таким образом, случайное блуждание? пример однородной цепи Маркова с дискретным временем.

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

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

Пусть число состояний конечно и равно.

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

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

Приведем пример матрицы перехода системы, которая может находиться в трех состояниях; переход из состояния в состояние происходит по схеме однородной цепи Маркова; вероятности перехода задаются матрицей:

Здесь видим, что если система находилось в состоянии, то после изменения состояния за один шаг она с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,2 перейдет в состояние, то после перехода она может оказаться в состояниях; перейти же из состояния в она не может. Последняя строка матрицы показывает нам, что из состояния перейти в любое из возможных состояний с одной и той же вероятностью 0,1.

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

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

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния.

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

Маркова цепь (Markov Chain) - марковский процесс с дискретным временем, заданный в измеримом пространстве.

Введение

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

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

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

Простой пример: бросание монеты

Прежде чем дать описание общей схемы, обратимся к простому примеру. Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ...

При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные значения j = k ± 1 c одинаковой вероятностью 1/2.

Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.

Формулы и определения

Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.

Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.

Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е. P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n.

Ясно, что P ij - квадратная матрица с неотрицательными элементами и единичными суммами по строкам.

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

На практике: доставка оборудования по округам

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

1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;

3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.

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

Матрица вероятностей перехода будет выглядеть следующим образом:

Например, р 12 = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А.

Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С.

Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1.

Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождние курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей из С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С-->B и B-->B;

3) С-->A и A-->B.

Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Подставляя числовые значения:

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

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

Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.

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

Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).

2 способ. Вычислить матрицу P 3:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С.

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

Задача 1. Задана матрица вероятностей перехода дискретной цепи Маркова из i -го состояния в j -ое за один шаг (i , j =1, 2). Распределение вероятностей по состояниям в начальный момент t =0 определяется вектором =(0,1; 0,9). Найти:

1. матрицу Р2 перехода цепи из состояния i в состояние j за два
шага;

2. распределение вероятностей по состояниям в момент t =2;

3. вероятность того, что в момент t =1 состоянием цепи будет А2 ;

4. стационарное распределение.

Решение. Для дискретной цепи Маркова в случае ее однородности справедливо соотношение

где Р1 – матрица переходных вероятностей за один шаг;
Рn - матрица переходных вероятностей за n шагов;

1. Найдем матрицу Р2 перехода за два шага

Пусть распределение вероятностей по состояниям на S -ом шаге определяется вектором
.
Зная матрицу Pn перехода за n шагов, можно определить распределение вероятностей по состояниям на (S+ n) –ом шаге . (5)

2. Найдем распределение вероятностей по состояниям системы в момент t =2. Положим в (5) S =0 и n =2. Тогда .

Получим .

3. Найдем распределение вероятностей по состояниям системы в момент t =1.

Положим в (5) s =0 и n =1, тогда .
Откуда видно, что вероятность того, что в момент t =1 состоянием цепи будет А2 ,равна р2(1) =0,69.
Распределение вероятностей по состояниям называется стационарным, если оно не меняется от шага к шагу, то есть
Тогда из соотношения (5) при n =1 получим

4. Найдем стационарное распределение. Так как =2 имеем =(р1; р2). Запишем систему линейных уравнений (6) в координатной форме

Последнее условие называется нормировочным. В системе (6) всегда одно уравнение является линейной комбинацией других. Следовательно, его можно вычеркнуть. Решим совместно первое уравнение системы и нормировочное. Имеем 0,6р1 =0,3р2 , то есть р2 =2р1 . Тогда р1 +2 р1 =1 или , то есть . Следовательно, .
Ответ:
1) матрица перехода за два шага для данной цепи Маркова имеет вид ;
2) распределение вероятностей по состояниям в момент t =2 равно ;
3) вероятность того, что в момент t =1 состоянием цепи будет А2 , равна р2(t) =0,69;
4) стационарное распределение имеет вид

Задана матрица интенсивностей переходов непрерывной цепи Маркова. Составить размеченный граф состояний, соответствующий матрице Λ; составить систему дифференциальных уравнений Колмогорова для вероятностей состояний; найти предельное распределение вероятностей. Решение. Однородная цепь Маркова с конечным числом состояний А1 , А2 ,…А характеризуется матрицей интенсивностей переходов ,

где - интенсивность перехода цепи Маркова из состояния Аi в состояние Аj ; рij(Δt) -вероятность перехода Ai→ Aj за интервал времени Δ t .

Переходы системы из состояния в состояние удобно задавать с помощью размеченного графа состояний, на котором отмечаются дуги, соответствующие интенсивностям λ ij >0. Составим размеченный граф состояний для заданной матрицы интенсивностей переходов

Пусть - вектор вероятностей р j(t) ,
j =1, 2,…,, нахождения системы в состоянии А j в момент t .

Очевидно, что 0≤р j(t) ≤1 и . Тогда по правилу дифференцирования векторной функции скалярного аргумента получим . Вероятности р j(t) удовлетворяют системе дифференциальных уравнений Колмогорова (СДУК), которая в матричной форме имеет вид . (7)

Если в начальный момент система находилась в состоянии Аj , то СДУК следует решать при начальных условиях
р i (0)=1, рj(0)=0, j≠i, j=1, 2,…, . (8)
Совокупность СДУК (7) и начальных условий (8) однозначно описывает однородную цепь Маркова с непрерывным временем и конечным числом состояний.
Составим СДУК для заданной цепи Маркова. Поскольку =3, то j =1, 2, 3.

Из соотношения (7) получим

.
Отсюда будем иметь

Последнее условие называется нормировочным.
Распределение вероятностей по состояниям называется стационарным , если оно не меняется с течением времени, то есть , где р j= const , j =1,2,…,. Отсюда .

Тогда из СДУК (7) получаем систему для нахождения стационарного распределения
(9)
Для данной задачи из СДУК будем иметь

Из нормировочного условия получим 3р2+р2+р2=1 или . Следовательно, предельное распределение имеет вид .
Заметим, что этот результат можно получить непосредственно по размеченному графу состояний, если воспользоваться правилом: для стационарного распределения сумма произведений λ ji pi , j≠ i , для стрелок, выходящих из i -го состояния, равна сумме произведений λ ji pi , j≠ i , для стрелок, входящих в i -ое состояние. Действительно,

Очевидно, что полученная система эквивалентна той, которая составлена по СДУК. Следовательно, она имеет то же решение.
Ответ: стационарное распределение имеет вид .

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

Примером однородной цепи Маркова могут служить случайные блуждания. Пусть на прямой Oxв точке с целочисленной координатойx=nнаходится материальная частица. В определенные моменты времени
частица скачкообразно меняет свое положение (например, с вероятностьюpможет сместиться вправо и с вероятностью 1 –p– влево). Очевидно, координата частицы после скачка зависит от того, где находилась частица после непосредственно предшествующего скачка, и не зависит от того, как она двигалась в предшествующие моменты времени.

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

Переходные вероятности. Матрица перехода.

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

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

, где представляют вероятности перехода за один шаг.

Отметим некоторые особенности матрицы перехода.

Равенство Маркова

Обозначим через
вероятность того, что в результатеnшагов (испытаний) система перейдет из состоянияв состояние. Например,
- вероятность перехода за 10 шагов из третьего состояния в шестое. Отметим, что приn= 1 эта вероятность сводится просто к переходной вероятности
.

Возникает вопрос, как, зная переходные вероятности
, найти вероятности перехода состоянияв состояниезаnшагов. С этой целью вводится в рассмотрение промежуточное (междуи) состояниеr. Другими словами, полагают, что из первоначального состояниязаmшагов система перейдет в промежуточное состояниеrс вероятностью
, после чего за оставшиесяn–mшагов из промежуточного состоянияrона перейдет в конечное состояниес вероятностью
. Используя формулу полной вероятности, можно показать, что справедлива формула

Эту формулу называют равенством Маркова .

Зная все переходные вероятности
, т.е. зная матрицу переходаиз состояния в состояние за один шаг, можно найти вероятности
перехода из состояние в состояние за два шага, а значит, и саму матрицу перехода, далее – по известной матрице- найтии т.д.

Действительно, полагая в равенстве Маркова n= 2,m= 1 получим

или
. В матричном виде это можно записать как
.

Полагая n=3,m=2, получим
. В общем случае справедливо соотношение
.

Пример . Пусть матрица переходаравна

Требуется найти матрицу перехода
.

Умножая матрицу саму на себя, получим
.

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

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

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

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