Что такое цепи Маркова и установившиеся вероятности

Где будущее только зависит от настоящего

Что такое цепи Маркова и установившиеся вероятности

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

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

Резюме:

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

1. Случайная переменная:

• Случайная переменная – это переменная, результат которой зависит от случайного явления. Например, подбрасывание монеты или температура в течение всего года.
• Непрерывная случайная величина — это переменная, которая может принимать бесконечное число возможных значений. Температуры в течение года могут принимать бесконечные значения в пределах диапазона и могут рассматриваться как непрерывная случайная величина.

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

2. Случайный процесс:

• Случайный процесс — это набор случайных величин. Обычно индексируется по времени.
• Когда у нас есть случайный процесс X(t), где t может принимать действительные значения в интервале на реальной линии, тогда X(t) является непрерывным во времени случайным процессом.

• Точно так же дискретный по времени случайный процесс — это процесс

Где J — счетное (конечное) множество.

• Случайный процесс с непрерывным значением — это процесс, в котором каждая случайная величина в процессе является непрерывной случайной величиной.
• Точно так же случайный процесс с дискретным значением — это процесс, в котором каждая случайная величина является дискретной случайной величиной.

Цепь Маркова:

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

Где для каждого момента времени n процесс принимает значение из дискретного набора, определяемого формулой

• Для цепи Маркова свойство Маркова утверждает, что распределение вероятностей следующего состояния (будущего) зависит только от распределения вероятностей текущее состояние.

Математически,

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

Визуальное объяснение цепи Маркова от Виктора Пауэлла и Льюиса Лехе — лучшее, что я встречал до сих пор. Видно, что цепь Маркова может переходить из данного состояния в другое состояние (включая себя) с вероятностью 0,5.

Матрица перехода пространства состояний (матрица перехода AKA):

• Матрица перехода в пространство состояний представляет собой квадратную матрицу размера n x n, которая описывает стохастическое поведение цепи Маркова.
• Например, цепь Маркова с двумя состояниями может быть математически выражена с использованием переходной матрицы 2 x 2.
• Рассмотрим цепь Маркова с состояниями A, B и C. Цепь Маркова может переходить из одного состояния в другое с определенной вероятностью.

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

Вектор состояния:

• Вектор состояния на любом шаге n — это вектор вероятностей каждого состояния, сумма которых равна 1.

Переход цепи Маркова:

Учитывая матрицу перехода, соответствующую цепи Маркова, и начальный вектор состояния, мы можем найти вектор состояния на шаге 1, используя следующую формулу:

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

Устойчивая вероятность:

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

Математически,

Нахождение вероятностей устойчивого состояния:

• Часто желательно понять долгосрочное поведение цепи Маркова.
• Для вычисления стационарных вероятностей цепи Маркова мы воспользуемся некоторыми старыми друзьями из линейной алгебры — собственными значениями и собственными векторами.
• Собственный вектор — это вектор, направление которого остается неизменным при применении к нему линейного преобразования.

Математически,

• Сравнивая уравнения установившихся вероятностей и собственных векторов, легко увидеть, что вектор установившегося состояния — это собственный вектор с собственным значением 1.
• Программно вычислить собственные векторы матрицы довольно просто.

[Бонус] Все ли цепи Маркова сходятся к уникальному устойчивому состоянию независимо от начального состояния?

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

• Редактировать: Как указал Xmaster, важно отметить, что неприводимость подразумевает, что независимо от текущего состояния мы можем достичь любого другого состояния за конечное время. Ссылка: здесь
• Неприводимая цепь Маркова называется периодической, если существует некоторое t такое, что существует состояние «s», которое можно посетить только за время t, 2t, 3t, … шагов. Если цепь Маркова не периодична, ее называют апериодической.

Давайте поговорим: