Уравнения Маркова
Муниципальное общеобразовательное учреждение «Лицей» г. Абакана
Адрес: 655016, Республика Хакасия, г. Абакан, ул.
Телефон: 8 (3902)28-21-49
Выполнила: Швайко Валентина, Ученица 11 класса Б
учитель высшей квалификационной категории.
4. Понятие о случайном процессе…………………………………………………. 9
5. Процессы с управляемыми параметрами……………………………………. 10-11
6. Цепи Маркова в теории случайного процесса………………………………. 12-21
7. Использование цепей Маркова в моделировании
8. Деревья решений. Управления Маркова………………………………………26-28
— Я учусь в физико-математическом классе, с удовольствием занимаюсь математикой. Читая дополнительную литературу, меня заинтересовала Книга «Диофант и диофантовы уравнения». И я решила углубить свои знания по данной теме. В процессе работы я прочитала о Маркове, его научных успехах. И я решила подробно изучить его работы: уравнения, цепи, алгоритмы и т. д. Сама проанализировала деревья решений, решала задачи из разных областей знаний с использованием Марковских цепей. Моя цель:
— 1) Показать разносторонность применений открытий Маркова в разных областях знаний
— 2) Показать их практическое применение в моделировании социально-экономических процессов
— 3) Исследовать деревья решений уравнений Маркова
-русский математик, представитель петербургской математической школы. Он родился в Рязани. В 1874г. поступил на физико-математический факультет Петербургского университета, где под влиянием занялся теорией непрерывных дробей и теорией чисел.
В 1884г. Марков защитил докторскую диссертацию, посвященную непрерывным дробям, в которой доказал и обобщил некоторые неравенства Чебышева, опубликованные раньше без доказательств. Маркову принадлежат также многочисленные работы по различным разделам математического анализа. В 1890 г. за глубокие научные исследования Марков был избран академиком Петербургской академии наук.
С конца 90-х гг. XIX в. главным предметом исследований ученого стала теория вероятностей. Здесь он продолжил работу своего учителя и ввел новый объект исследования — последовательности зависимых случайных величин, получившие в дальнейшем название марковских цепей. Так называют последовательности случайных величин, для которых вероятность появления того или иного значения на (h + 1 )-м шагу зависит лишь от того, какое значение эта величина приняла на h-м шагу, и не зависит от значений величины на 1-м, 2-м. (h – 1 )-м шагах.
Марковские цепи сразу после их открытия не нашли практических приложений, и ученому пришлось применять свои результаты к распределению гласных и согласных букв в поэме А. С: Пушкина «Евгений Онегин». Ведь за согласной чаще идет гласная, а за гласной — согласная, и в первом приближении можно считать, что вероятность появления гласной на (h + 1)-м месте зависит лишь от того, гласной или согласной является буква, стоящая на h,-м месте. Но, как всегда бывает с глубокими научными результатами, в дальнейшем были обнаружены гораздо более важные для практики области приложения марковских цепей (например, теория массового обслуживания). Из теории марковских цепей возникла общая
теория случайных процессов, которая применяется при изучении лавинных процессов и других проблем.
был страстным и убежденным борцом против произвола и несправедливости царского режима, выступал против попыток подчинить преподавание математики в школе религиозным взглядам. Он отказался от царских орденов, подал в Синод просьбу об отлучении от церкви, указав что не сочувствует всем религиям, которые, подобно православию, поддерживаются огнем и мечом и сами служат им. Резкие выпады против веры в чудеса содержатся в учебнике «Исчисление вероятностей», опубликованном в дореволюционное время. После выхода книги ученого обвинили в безбожии и «подрыве основ». От преследований его избавил лишь крах царского режима.
Первые задачи теории вероятностей были рассмотрены Л. Пачоли (1445-ок. 1514),—Д. Кардано (1501-1576), Н. Тарталья (ок. 1499-1557), Б. Паскалем (1623-1662), П. Ферма (1601-1665), X. Гюйгенсом (1629-1695). В качестве самостоятельной научной дисциплины теория вероятностей стала оформляться в работах Я. Бернулли (1654-1705), А. Муавра (1667-1754), П. Лапласа (1749-1827), С. Пуассона (1781-1840). Ее последующее развитие связано с именами , , (1857-1918), (1894-1959), (1880-1968), (род. 1903) и др.
Случайный процесс, протекающий в системе, называется Марковским процессом, если он обладает свойством: для каждого момента времени t0 вероятность любого состояния системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t„) и не зависит от того, когда и каким образом система пришла в это состоянии (т. е. как развивался процесс в прошлом).
Характерное свойство марковских случайных процессов можно увидеть уже на таком простом примере, как известная игра «тише едешь – дальше будешь». В этой игре фишка играющего должна пройти некоторое конечное число пунктов 1,2,. . m. Переход из одного пункта в другой каждый раз определяется исходом бросания игральной кости. Именно, если на данном шаге фишка находится в пункте i, то правилами игры устанавливается пункт перехода ее на следующем шаге в зависимости от числа выпавших на игральной кости очков. Из любого пункта i фишка с некоторой вероятностью рii переходит в один из пунктов j независимо от характера движения до попадания в пункт i.
На практике часто встречаются случайные процессы, которые с той или иной степенью приближения можно считать Марковским.
Любой Марковский процесс описывают с помощью вероятностей состояний и переходных вероятностей.
Вероятности состояний Рк Марковский случайного процесса – это вероятности того, что случайный процесс (система) в момент времени t находится в состоянии Sk:
Переходные вероятности Марковского процесса — это вероятности перехода процесса (системы) из одного состояния в любое другое:
Марковский процесс называют однородным, если вероятности перехода за единицу времени не зависят от того, где на оси времени происходит переход. Наиболее простым процессом является цепь Маркова – Марковский случайный процесс с дискретным временем и дискретным конечным множеством состояний.
При анализе цепи Маркова составляют граф состояний, на котором отмечают все состояния цепи (системы) и ненулевые вероятности перехода за один шаг.
Марковскую цепь можно представить себе так, как будто точка, изображающая систему, случайным образом перемещается по графу состояний, перескакивая за один шаг из состояния в состояние или задерживаясь на несколько шагов в одном и том же состоянии.
Переходные вероятности цепи Маркова за одид шаг рij записывают в виде матрицы Р = || рij || которую называют матрицей вероятностей перехода или просто переходной матрицей.
неотрицательны, их суммы по строкам равны единице. Матрицы с таким свойством часто называют стохастическими. Матрицы переходов позволяют вычислить вероятность любой траектории (реализации) цепи Маркова с помощью теоремы умножения вероятностей. Для однородных цепей Маркова матрицы переходов не зависят от времени. При изучении цепей Маркова наибольший интерес представляют: распределение по состояниям на шаге m —> оо; среднее время пребывания в определенном состоянии; среднее время возвращения в это состояние.
На практике явления протекают во времени и в пространстве, поэтому приходится иметь дело не с отдельными случайными величинами, а с семействами случайных величин, зависящих от параметра. Случайный процесс — это семейство случайных величин X(t), где параметр t € Т — множеству значений параметра.
Многие важные процессы в природе и на производстве являются примерами случайных процессов: турбулентные течения жидкостей и газов, распространение радиоволн при наличии помех, движение транспортных потоков, обслуживание клиентов в ремонтной мастерской и др. Параметр t в определении случайного процесса обычно интерпретируют как время. Если зафиксировать значение времени 10,то X(tn) — обычная случайная величина
На случайный процесс можно смотреть либо как на совокупность случайных величин, зависящих от параметра t, либо как на совокупность реализаций процесса реализация представляет собой одно возможное осуществление случайного процесса.
Если параметр t принимает дискретные значения (обычно t = 0,1;2;. ), то X(t) — случайный процесс с дискретным временем, если же t изменяется на некотором интервале (конечном или бесконечном), то X(t>
случайный процесс с непрерывным временем.
В свою очередь, если случайные величины семейства принимают дискретные значения, то имеет место случайный процесс с дискретными значениями, если же непрерывные — то с непрерывными значениями.
К процессам с дискретными значениями относятся, например, процессы образования очередей, распространения мутаций генов в биологической популяции и т. д. К процессам с непрерывными значениями относятся процесс изменения напряжения в осветительной сети, процесс перемешивания шихты во время плавки в доменной печи и т. д.
При решении практических задач обычно предполагают, что случайный процесс протекает в некоторой системе. Под системой может пониматься что угодно: техническое устройство, ремонтная мастерская, железнодорожный узел, биологическая популяция. Состояние системы, или состояние случайного процесса — это возможное значение случайных величин, образующих случайный процесс.
Начало общей теории случайных процессов было положено работами и , относящимися к 30-м годам XX века. Зарождение же теории случайных процессов связано с работами начала XX века по изучению так называемых цепей Маркова.
-10-
В Хакасии через длительные периоды времени то идет снег, то безоблачно. Если идет снег, то с вероятностью 0,7 он будет идти на следующий день; если в какой-то день безоблачная погода, то с вероятностью 0,6 она сохранится и на следующий день. Известно, что в среду 06 февраля 2008 года погода безоблачная. Какова вероятность того, что будет снег в пятницу 8 февраля 2008 года?
Записать все состояния цепи Маркова
Б- погода безоблачная С-снег
Построить граф состояний
Разметить граф состояний переходными вероятностями
Составить матрицу вероятностей перехода
0,6 0,4
Вычислить по матрице искомые вероятности
p=P(Спят / Бср) = P(Спят / Счетв)*P(Счетв/ Бср) +
+ P(Спят / Бчетв)*P(Бчетв/ Бср)=0,7 * 0,4 + 0,4 * 0,6 = 0.52
Автомашина может находиться в одном из четырех состояний:
Если машина исправна, то с вероятностью 0.8 она может сломаться; если машина неисправна, то она с вероятностью 0.7 ремонтируется или с вероятностью 0.3 списывается; если же машина ремонтируется, то она с вероятностью 0.6 становится исправной, либо с вероятностью 0.4 продолжается ремонтироваться. Остальные переходы считать невозможными. Найти вероятность того, что машина будет исправна в субботу, если известно, что она была исправна в среду.
В некоторой местности климат весьма изменчив. Здесь никогда не бывает двух ясных дней подряд. Если сегодня ясно, то завтра с одинаковой вероятностью пойдет дождь или снег. Если сегодня снег (или дождь), то с одинаковой вероятностью 1А погода не изменится. Если все же она изменится, то в половине случаев снег заменяется дождем или наоборот и лишь в половине случаев на следующий день будет ясная погода. Определить вероятность хорошей погоды через три дня после дождя.
Предположим, что мужчин можно разделит по их профессиям на работников умственного труда, квалифицированных рабочих и неквалифицированных рабочих. Допустим, 80% сыновей работников умственного труда становятся работниками умственного труда, 10% — квалифицированными рабочими и 10 % — неквалифицированными рабочими. Пусть из сыновей квалифицированных рабочих 60% становятся квалифицированными рабочими, 20% — работниками умственного труда и 20% — неквалифицированными рабочими. Наконец, 50% сыновей неквалифицированных рабочих пусть будут квалифицированными рабочими и по 25% пусть приходится на долю других категорий. В предположении, что каждый мужчина имеет одного сына, построить цепь Маркова с тремя состояниями, чтобы проследить за несколькими поколениями какой — либо семьи. Выпишите матрицу вероятностей перехода. Найти вероятность того, что внук неквалифицированного рабочего станет работником умственного труда.
В задаче 3.3 предполагалось, что у каждого мужчины есть сын. Теперь допустим, что для каждого мужчины вероятность иметь сына равна 0.8. Образуя Марковскую цепь с четырьмя состояниями. Первые три состояния пусть будут те же, что и задаче 3.3, а четвертое состояние отвечает случаю, когда мужчина не имеет сына, и процесс на этом кончается. Это состояние представляют те семьи, в которых мужская линия вымерла. Выпишите матрицу вероятностей перехода и найдите вероятность того, что внук неквалифицированного рабочего будет работником умственного труда.
Все основные определения, относящиеся к цепям Маркова т. е. вероятности состояний рk(t), переходной вероятности рij, матрица вероятностей перехода или переходная матрица р = ||рij||, предельные вероятности состояний рj, в данном разделе рассмотрим лишь несколько примеров, относящихся к различным областям применения цепей Маркова. Первые два примера показывают, как можно использовать «обычные» цепи Маркова (в их классическом понимании), а последний пример описывает одну из экономических задач, где применяется оптимальное управление цепями Маркова.
Пример 1 . В некоторой стране у власти находится одна из двух партий, например лейбористы и консерваторы. Допустим, что нас интересует вопрос, какая из двух партий соберет больше голосов на выборах. Мы хотим сделать предсказания, рассчитанные на длительный срок, и поэтому не, рассматриваем специфических условий избирательной компании в том или ином году. Наши предсказания будут основаны только на истории предшествующих выборов, каждый раз дающих перевес либо лейбористам, либо консерваторам. Ясно, что знание результатов предшествующих выборов должно влиять на наши предсказания, относящиеся к будущему времени. В качестве первого приближения мы принимаем, что при оценке вероятности того или иного исхода выборов играет роль лишь знание результата только одних предшествующих выборов. В этих условиях мы приходим к марковской цепи с двумя состояниями Л и К и переходной матрицей
Л 1-а а
Числа а и Ь могут быть оценены по известным нам результатам предшествующих выборов следующим образом. За а можно принять долю тех прошлых лет, исход выборов которых был в пользу лейбористов, в то время как на следующих выборах он оказывался уже в пользу консерваторов (т. е. переход Л — >К), а в качестве Ь — долю противоположных перемен (т. е. К — » Л). Если числа а и Ь отличны от 0 и 1 , то для такой цепи Маркова существуют предельные вероятности состояний рл и рк, которые находятся с помощью уравнения
(рл, рк) * b 1-b = (рл, рк)
Запишем это матричное уравнение с помощью системы двух линейных уравнений и найдем предельные вероятности отношений:
-23-
службы, и вначале каждого периода мы должны принять одно из двух решений: заменить устройство на новое или продолжать эксплуатировать старое. Вероятность поломки устройства и доход от его эксплуатации зависят от времени службы. При замене мы несем расходы на новое оборудование, при поломке сверх того терпим определенные убытки. Целью управления является получение возможно большей суммарной прибыли (поскольку она случайна – рассматривается ее математическое ожидание).
Рассмотрим математическую модель, которая получается в этом случае. Под состоянием системы будем понимать время работы действующего оборудования. Считаем, что это время описывается целым неотрицательным числом х. Получаем цепь Маркова с состоянием 0;1;……; К.
В каждом состоянии х возможны два решения: с— сохранить старое оборудование и b – провести замену. Если принято решение В, то система переходит в состояние 0; если же принято решение С, то происходит переход из состояния х в состояние х+1, при этом не должна случиться поломка оборудования. Когда такая поломк4а произойдет, то оборудование придется заменить и совершиться переход из состояния х в состояние 0. Вероятность поломки зависит, вообще говоря, от срока службы х. Обозначим ее qх и положим рх = 1- qх. Естественно предположить, что qх не убывает с увеличением х. Допустим, что при некотором х = К будут принимать только значения 0;1;2;….;К. Переходная функция модели опрделяеться формулами
Вероятность таких переходов равна 0.
Далее;, пусть hх – доход при переходе х с х+1 ( т. е. при благополучной эксплуатации оборудования, уже прослужившего время х); по смыслу задачи hх не возрастает с увеличением х. Обозначим через а доход за период, когда происходит плановая замена оборудования (переход х b 0)
Пусть у – доход при переходе х в 0. Поскольку замена оборудования при поломке обходится дороже планомерной замены, то γ
Цепи Маркова. Переходные вероятности
Примеры решений
Задача 1. Для заданной матрицы переходных вероятностей Р найти вероятности перехода за 2 шага и стационарные вероятности, если они существуют.
Задача 2. Задана матрица $P_1$ вероятностей перехода дискретной цепи Маркова из состояния $i (i=1,2)$ в состояние $j (j=1,2)$ за один шаг. Распределение вероятностей по состояниям в момент $t=0$ определяется вектором $\bar$. Найти:
1) матрицу $P_2$ перехода из состояния $i$ в состояние $j$ за два шага;
2) распределение вероятностей по состояниям в момент $t=2$;
3) вероятность того, что в момент $t=1$ состоянием цепи будет $i=2$;
4) стационарное распределение.
Задача 3. В заданной матрице $L$ элемент $\lambda_
А) построить граф переходов между состояниями, ребра которого помечены соответствующими интенсивностями переходов.
Б) написать систему уравнений для определения предельных вероятностей различных состояний.
В) решить эту систему уравнений, найти предельную вероятность каждого состояния.
Задача 4. Найти стационарные вероятности и математическое ожидание для марковского процесса N, заданного графом переходов состояний.
Задача 5. Дан размеченный граф состояний системы. 
Найти:
А) матрицы перехода за один и два шага,
Б) вероятности состояний системы после первого, второго, третьего шага, если в начальный момент система находилась в состоянии $S_1$,
В) финальные вероятности.
Задача 6. Система имеет три состояния. Построить граф состояний системы, написать уравнения Колмогорова и найти стационарное распределение.
Краткое введение в цепи Маркова
В 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 (не единственная) заключается в имитации веб-пользователя, случайным образом перемещающегося от страницы к странице; при этом показателем ранжирования становится индуцированное стационарное распределение страниц (грубо говоря, на самые посещаемые страницы в устоявшемся состоянии должны ссылаться другие часто посещаемые страницы, а значит, самые посещаемые должны быть наиболее релевантными)
В заключение ещё раз подчеркнём, насколько мощным инструментом являются цепи Маркова при моделировании задач, связанных со случайной динамикой. Благодаря их хорошим свойствам они используются в различных областях, например, в теории очередей (оптимизации производительности телекоммуникационных сетей, в которых сообщения часто должны конкурировать за ограниченные ресурсы и ставятся в очередь, когда все ресурсы уже заняты), в статистике (хорошо известные методы Монте-Карло по схеме цепи Маркова для генерации случайных переменных основаны на цепях Маркова), в биологии (моделирование эволюции биологических популяций), в информатике (скрытые марковские модели являются важными инструментами в теории информации и распознавании речи), а также в других сферах.
Разумеется, огромные возможности, предоставляемые цепями Маркова с точки зрения моделирования и вычислений, намного шире, чем рассмотренные в этом скромном обзоре. Поэтому мы надеемся, что нам удалось пробудить у читателя интерес к дальнейшему изучению этих инструментов, которые занимают важное место в арсенале учёного и эксперта по данным.
http://www.matburo.ru/ex_tv.php?p1=tvmark
http://habr.com/ru/post/455762/