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

9

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

Например, в статье « Оптимальное сосредоточение в пространстве состояний в цепях Маркова» они дают следующее определение CTMC (непрерывной цепи Маркова):

Рассмотрим конечный CTMC с пространством состояний S = { x 1 , x 2 , , x n } матрицей переходных скоростей Q : S × SR + .(S,Q)S={x1,x2,,xn}Q:S×SR+

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

В другой статье « О реляционных свойствах единственности марковские цепи» определяются аналогично

Марковская цепь будет представлена ​​в виде триплета ( S , P , π ), где S - конечный набор состояний M , P - матрица вероятностей перехода, указывающая вероятность перехода из одного состояния в другое, а π - начальная вероятность. распределение, представляющее вероятность запуска системы в определенном состоянии.M(S,P,π)SMPπ

Опять же, нет упоминания о прошлом или будущем или независимости.

Есть третья статья Простая O (m logn) Цепочка Маркова Времени, где они не только никогда не утверждают, что веса на ребрах являются вероятностями, но даже говорят:

Во многих приложениях значения неотрицательны. Мы не делаем это предположение, однако, потому что есть также приложения , где W ( s , S ) намеренно выбран - W ( S , S { s } ) , что делает его , как правило , отрицательный.W(s,s)W(s,s)W(s,S{s})

Более того, заявлено, что сосредоточение должно быть способом уменьшения количества состояний при сохранении свойства Маркова (путем объединения «эквивалентного» состояния в большее состояние). Тем не менее, мне кажется, что это просто суммирование вероятностей, и оно даже не должно гарантировать, что результирующие возможности переходов в / из агрегированных состояний находятся в диапазоне . Что же на самом деле сохраняет шишка?[0,1]

Итак, я вижу две возможности:

  • Я не понял, что такое цепь Маркова, или
  • Использование термина цепь Маркова в этих работах является поддельным

Может ли кто-то прояснить ситуацию?

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

Bakuriu
источник
В Интернете существуют тонны учебников и ресурсов, которые объясняют (а) что такое цепь Маркова и (б) каково точное математическое определение. Мы ожидаем, что вы проведете значительный объем исследований и самообучения, прежде чем спрашивать. Итак, вы обращались к любому из этих ресурсов? Что ты там нашел? PS Я полагаю, что в литературных статьях предполагается, что вы знаете определение цепочки Маркова, и эти предложения не обязательно должны быть предназначены для точного формального определения цепочки Маркова, а скорее просто для установления обозначения, которое они используют при разговоре. об одном.
DW
Прошлое или будущее или независимость - это свойства, которые следуют, iirc. Там должны быть некоторые ограничения по весу, хотя; возможно, некоторые вещи могут оставаться неявными, например, присвоение отсутствующего исходящего веса ребру, которое приводит к состоянию приемника (см. различные определения DFA).
Рафаэль
4
@DW Да, я сделал. Я обнаружил, что понятие цепи Маркова в учебнике, похоже, не имеет ничего общего с ее концепцией, используемой в таких работах. Именно поэтому я спрашиваю это.
Бакуриу
4
Опять же, есть третья возможность. Я думаю, что ошибка, которую вы совершаете, состоит в том, чтобы интерпретировать утверждение в этих статьях как определение цепи Маркова. Я предполагаю, что это, вероятно, не цель этих заявлений. Я предполагаю, что авторы предполагают, что вы уже знакомы с определением цепочки Маркова и просто пытаетесь установить некоторые обозначения (существует несколько видов обозначений, которые вы можете использовать для одной и той же концепции). Итак, взгляните еще раз с этой точки зрения и посмотрите, найдете ли вы что-либо, что противоречит этому, в документах (если вы найдете что-нибудь, добавьте это к вопросу).
DW
4
@DW Похоже, что ОП провел достойное исследование и приемлемо структурировал свой вопрос. Да, мы можем использовать Google, чтобы учиться. Но вы заметили, как высоко оцениваются сайты SE в Google? Это потому, что мы сжимаем информацию в (обычно) отдельные, четко определенные вопросы. Совместные усилия нашего сообщества создают очень богатый и ценный контент, который во много раз более полезен, чем страницы и страницы информации, что приводит к более эффективному обучению.
БАР

Ответы:

10

NN×N

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

Pπ

[0,1]P1π1

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

1

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

Блуждающая логика
источник
8

Цепи Маркова бывают двух видов: непрерывное и дискретное.

Цепи Маркова с непрерывным временем (CTMC) и цепочки Марка с дискретным временем (DTMC) представлены в виде ориентированных взвешенных графов.

Для DTMC переходы всегда занимают одну единицу времени. В результате нет никакого выбора для того, каким должен быть ваш вес на дуге - вы устанавливаете вероятность перехода в «j», учитывая, что вы находитесь в «i».

Для CTMC время перехода между любыми двумя состояниями обязательно задается экспоненциальной случайной величиной. В этом ключевое отличие CTMC от DTMC: у DTMC всегда есть время перехода единиц. CTMC имеют случайное время перехода.

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

Отрицательные цены

Хотя все CTMC, которые я помню, были представлены с положительными показателями по краям, отрицательные показатели все же встречаются в анализе CTMC.

Скажем, мы находимся в состоянии A, которое связано с B, C и D, как показано ниже.

A -> B (ставка в A из B отрицательна) A -> C (скорость в A из C отрицательна) D -> A (ставка в A из D положительна)

Это, вероятно, не совсем то, на что ссылается ваша статья; Я поднимаю это, чтобы показать, что отрицательные веса не обязательно смешны, если кто-то работал с подходящим соглашением.

Марков Имущество

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

Райли
источник
W(s,s)-W(s,S{s})s
Последняя статья довольно таинственна для меня, потому что они не используют терминологию цепей Маркова в большей части статьи. Возможно, что они решают более общую проблему, хотя мотивация - цепи Маркова. Тем не менее, W(s,s)=W(s,S{s})