Новости
Теория
Визуализаторы
Что почитать
Ссылки
О нас
![]() ![]() |
Настоящая статья носит реферативный характер, написана на основе приведенных в конце источников, которые местами цитируются. Введение в теорию марковских цепейЦепью Маркова называют такую последовательность случайных событий, в которой вероятность каждого события зависит только от состояния, в котором процесс находится в текущий момент и не зависит от более ранних состояний. Конечная дискретная цепь определяется:
∑j=1…n
pij = 1
Пример матрицы переходных вероятностей с множеством состояний S = {S1, …, S5}, вектором начальных вероятностей p(0) = {1, 0, 0, 0, 0}: ![]() С помощью вектора начальных вероятностей и матрицы переходов можно вычислить стохастический вектор p(n) — вектор, составленный из вероятностей p(n)(i) того, что процесс окажется в состоянии i в момент времени n. Получить p(n) можно с помощью формулы:
p(n) = p(0)×P
n
Векторы p(n) при росте
n в некоторых случаях стабилизируются — сходятся к некоторому вероятностному вектору
ρ, который можно назвать стационарным распределением цепи.
Стационарность проявляется в том, что взяв p(0) = ρ, мы
получим p(n) = ρ для любого n. Марковская цепь изображается в виде графа переходов, вершины которого соответствуют состояниям цепи, а дуги — переходам между ними. Вес дуги (i, j), связывающей вершины si и sj будет равен вероятности pi(j) перехода из первого состояния во второе. Граф, соответствующий матрице, изображенной выше: ![]() Классификация состояний марковских цепей
При рассмотрении цепей Маркова нас может интересовать поведение
системы на коротком отрезке времени. В таком случае абсолютные вероятности вычисляются
с помощью формул из предыдущего раздела. Однако более важно
изучить поведение системы на большом интервале времени, когда число переходов стремится к бесконечности.
Далее вводятся определения
состояний марковских цепей, которые необходимы для изучения поведения системы в долгосрочной перспективе. Поглощающие марковские цепи используются в качестве временных моделей программ и вычислительных процессов. При моделировании программы состояния цепи отождествляются с блоками программы, а матрица переходных вероятностей определяет порядок переходов между блоками, зависящий от структуры программы и распределения исходных данных, значения которых влияют на развитие вычислительного процесса. В результате представления программы поглощающей цепью удается вычислить число обращений к блокам программы и время выполнения программы, оцениваемое средними значениями, дисперсиями и при необходимости — распределениями. Используя в дальнейшем эту статистику, можно оптимизировать код программы — применять низкоуровневые методы для ускорения критических частей программы. Подобный метод называется профилированием кода. Например, в алгоритме Дейкстры присутствуют следующие состояния цепи:
Остается задать вероятности переходом между вершинами, и можно изучать продолжительности переходов
между вершинами, вероятности попадания в различные состояния и другие средние характеристики процесса. Аналогично, вычислительный процесс, который сводится к обращениям за ресурсами системы в порядке, определяемом программой, можно представить поглощающей марковской цепью, состояния которой соответствуют использованию ресурсов системы – процессора, памяти и периферийных устройств, переходные вероятности отображают порядок обращения к различным ресурсам. Благодаря этому вычислительный процесс представляется в форме, удобной для анализа его характеристик.
Цепь Маркова называется неприводимой, если любое состояние Sj
может быть достигнуто из любого другого состояния Si
за конечное число переходов. В этом случае все состояния цепи называются сообщающимися, а
граф переходов является компонентой сильной связности.
Процесс, порождаемый эргодической цепью, начавшись в некотором состоянии,
никогда не завершается, а последовательно переходит из одного состояния в другое,
попадая в различные состояния с разной частотой, зависящей от переходных вероятностей.
Поэтому основная характеристика эргодической цепи – Примеры использованияСистема обслуживания с отказамиСервер, состоит из нескольких блоков, например модемов или сетевых карт, к которым поступают запросы от пользователей на обслуживание. Если все блоки заняты, то запрос теряется. Если один из блоков принимает запрос, то он становится занятым до конца его обработки. В качестве состояний возьмем количество незанятых блоков. Время будет дискретно. Обозначим за α вероятность поступления запроса. Также мы считаем, что время обслуживания также является случайным и состоящим из независимых продолжений, т.е. запрос с вероятностью β обслуживается за один шаг, а с вероятностью (1 - β) обслуживается после этого шага как новый запрос. Это дает вероятность (1 - β) β для обслуживания за два шага, (1 - β)2 β для обслуживания за три шага и т.д. Рассмотрим пример с 4 устройствами, работающими параллельно. Составим матрицу переходных вероятностей для выбранных состояний:
Можно заметить, что она имеет единственный эргодический класс, и, следовательно, система p × P = p в классе вероятностных векторов имеет единственное решение. Выпишем уравнения системы, позволяющей находить это решение:
p0 (1 - α) +
p1 β = p0,
p0 α + p1 (1 - α - β) + p2 2β = p1, p1 α + p2 (1 - α - 2β) + p3 3β = p2, p2 α + p3 (1 - α - 3β) + p4 4β = p3, p3 α + p4 (1 - 4β) = p4. Отсюда получаем (при γ = α / β):
p1 = γ p0,
p2 = γ2 p0/2, p3 = γ3 p0/3, p4 = γ4 p0/4, из условия нормировки следует:
p0 = С = (1 + γ + γ2/2 +
γ3/3 + γ4/4)-1.
Теперь известен набор вероятностей πi того, что в
стационарном режиме в системе будет занято i блоков. Тогда
долю времени p4 = С γ4/4
в системе заняты все блоки, система не отвечает на запросы. Полученные результаты распространяются
на любое число блоков. Теперь можно воспользоваться ими: можно сопоставить затраты на дополнительные
устройства и уменьшение времени полной занятости системы. Процессы принятия решений с конечным и бесконечным числом этаповРассмотрим процесс, в котором есть несколько матриц переходных вероятностей. Для каждого момента времени выбор той или иной матрицы зависит от принятого нами решения. Понять вышесказанное можно на следующем примере. Садовник в результате анализа почвы оценивает ее состояние одним из трех чисел: (1) — хорошее, (2) — удовлетворительное или (3) — плохое. При этом садовник заметил, что продуктивность почвы в текущем году зависит только от ее состояния в предыдущем году. Поэтому вероятности перехода почвы без внешних воздействий из одного состояния в другое можно представить следующей цепью Маркова с матрицей P1:
Логично, что продуктивность почвы со временем ухудшается. Например, если в прошлом году состояние почвы было удовлетворительное, то в этом году оно может только остаться таким же или стать плохим, а хорошим никак не станет. Однако садовник может повлиять на состояние почвы и изменить переходные вероятности в матрице P1 на соответствующие им из матрицы P2:
Теперь можно сопоставить каждому переходу из одного состояния в другое некоторую функцию дохода, которая определяется как прибыль или убыток за одногодичный период. Садовник может выбирать использовать или не использовать удобрения, именно от этого будет зависеть его конечный доход или убыток. Введем матрицы R1 и R2, определяющие функции дохода в зависимости от затрат на удобрения и качества почвы:
Наконец перед садовником стоит задача, какую стратегию нужно выбрать для максимизации среднего ожидаемого дохода. Может рассматриваться два типа задач: с конечным и бесконечным количеством этапов. В данном случае когда-нибудь деятельность садовника обязательно закончится. Кроме того, визуализаторы решают задачу принятия решений для конечного числа этапов. Пусть садовник намеревается прекратить свое занятие через N лет. Наша задача теперь состоит в том, чтобы определить оптимальную стратегию поведения садовника, то есть стратегию, при которой его доход будет максимальным. Конечность числа этапов в нашей задаче проявляется в том, что садовнику не важно, что будет с его сельскохозяйственным угодьем на N+1 год (ему важны все года до N включительно). Теперь видно, что в этом случае задача поиска стратегии превращается в задачу динамического программирования. Если через fn(i) обозначить максимальный средний ожидаемый доход, который можно получить за этапы от n до N включительно, начиная из состояния с номером i, то несложно вывести рекуррентное соотношение, связывающее fn(i) с числами fn+1(j)
fn(i) =
maxk{∑j=1mpijk[rijk +
fn+1(j)]},
n = 1, 2, …, N
Здесь k — номер используемой стратегии. Это
уравнение основывается на том, что суммарный доход
rijk + fn+1(j)
получается в результате перехода из состояния i на этапе
n в состояние j на этапе n+1
с вероятностью
pijk. Моделирование сочетаний слов в тексте
Рассмотрим текст, состоящий из слов w. Представим
процесс, в котором состояниями являются слова, так что когда он
находится в состоянии (Si)
система переходит в состояние (sj) согласно
матрице переходных вероятностей. Прежде всего, надо «обучить» систему: подать на вход достаточно
большой текст для оценки переходных вероятностей. А затем можно строить траектории марковской цепи.
Увеличение смысловой нагрузки текста, построенного при помощи алгоритма цепей
Маркова возможно только при увеличении порядка, где состоянием является
не одно слово, а множества с большей мощностью — пары (u, v),
тройки (u, v, w) и т.д. Причем что в цепях первого, что
пятого порядка, смысла будет еще немного. Смысл начнет появляться при увеличении
размерности порядка как минимум до среднего количества слов в типовой фразе
исходного текста. Но таким путем двигаться нельзя, потому, что рост смысловой
нагрузки текста в цепях Маркова высоких порядков происходит значительно медленнее,
чем падение уникальности текста. А текст, построенный на марковских цепях, к примеру,
тридцатого порядка, все еще будет не настолько осмысленным, чтобы представлять интерес
для человека, но уже достаточно схожим с оригинальным текстом, к тому же число состояний в
такой цепи будет потрясающим. Цепи Маркова и лотереи
В некоторых случаях вероятностная модель используется в прогнозе номеров в
различных лотереях. По-видимому, использовать цепи Маркова для
моделирования последовательности различных тиражей нет смысла. То, что
происходило с шариками в тираже, никак не повлияет на результаты следующего
тиража, поскольку после тиража шары собирают, а в следующем тираже их укладывают
в лоток лототрона в фиксированном порядке. Связь с прошедшим тиражом при этом теряется.
Другое дело последовательность выпадения шаров в пределах одного тиража.
В этом случае выпадение очередного шара определяется состоянием лототрона
на момент выпадения предыдущего шара. Таким образом, последовательность
выпадений шаров в одном тираже является цепью Маркова, и можно использовать такую модель.
При анализе числовых лотерей здесь имеется большая трудность.
Состояние лототрона после выпадения очередного шара определяет дальнейшие
события, но проблема в том, что это состояние нам неизвестно. Все что нам
известно, что выпал некоторый шар. Но при выпадении этого шара, остальные
шары могут быть расположены различным образом, так что имеется группа из
очень большого числа состояний, соответствующая одному и тому же наблюдаемому
событию. Поэтому мы можем построить лишь матрицу вероятностей переходов между
такими группами состояний. Эти вероятности являются усреднением вероятностей
переходов между различными отдельными состояниями, что конечно, снижает
эффективность применения модели марковской цепи к числовым лотереям. Литература
Визуализаторы
Макаров Н. |