(Андрей Андреевич Марков (1856-1922) – русский математик, академик)

(Андрей Андреевич Марков (1856-1922) – русский математик, академик)

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

Цепь Маркова это один из самых простых случаев последовательности случайных событий.

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

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

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

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

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

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

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

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

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

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

События называют состояниями системы, а испытания – изменениями ее состояний.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть P_ij(n) – вероятность того, что в результате n испытаний система перейдет из состояния i в состояние j, r – некоторое промежуточное состояние между состояниями i и j. Вероятности перехода из одного состояния в другое p_ij(1) = p_ij.

Тогда вероятность P_ij(n) может быть найдена по формуле, называемой равенством Маркова:

Здесь т – число шагов (испытаний), за которое система перешла из состояния i в состояние r.

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

Зная переходные вероятности (т.е. зная матрицу перехода Р₁), можно найти вероятности перехода из состояния в состояние за два шага P_ij(2), т.е. матрицу Р₂, зная ее – найти матрицу Р₃, и т.д.

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

Тогда в общем виде можно записать:

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

Пример 1. Задана матрица переходов Р₁. Найти матрицу Р₂.

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

Воспользуемся формулой .

Перемножив матрицы, окончательно получим:

.

Пример 2. Задана матрица переходов Р₁. Найти матрицу Р₂.

Пример 3. Задана матрица переходов Р₁. Найти матрицу Р₃.

Определение. Матрицы, суммы элементов всех строк которых равны единице, называются стохастическими. Если при некотором п все элементы матрицы Р^п не равны нулю, то такая матрица переходов называется регулярной.

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

Теорема. (теорема о предельных вероятностях) Пусть дана регулярная цепь Маркова с п состояниями и Р – ее матрица вероятностей перехода. Тогда существует предел и матрица Р^(¥) имеет вид:

Т.е. матрица состоит из одинаковых строк.

Теперь о величинах u_i. Числа u₁, u₂, …, u_n называются предельными вероятностями. Эти вероятности не зависят от исходного состояния системы и являются компонентами собственного вектора матрицы Р^Т (транспонированной к матрице Р).

Этот вектор полностью определяется из условий:

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

C учетом того, что u₁ + u₂ = 1, получаем:

Получаем:

Дата добавления: 2015-09-30