Лучшее вводное руководство по цепям Маркова, написанное для Xiaobai.

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

Эта статья приняла участие"Проект "Звезда раскопок"", чтобы выиграть творческие подарочные пакеты и бросить вызов творческим поощрениям.

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

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

Мы знаем, что человеческое познание мира начинается с движения, от макроскопического небесного движения к микроскопическому молекулярному движению, это процесс изменения «вещей» с течением времени, появление Ньютона хорошо объяснило нам систематическим образом. знакомы людям и позволяют людям точно рассчитывать и предсказывать некоторые движения. Однако в мире существует еще большое количество процессов "движения" с неопределенными факторами. Причина, по которой движение взято в кавычки, состоит в том, что оно является общим описанием. Оно классифицируется как "движение", т. е. изменение вещей во времени. Все мы знаем, что вероятность появления каждого числа от 1 до 6 в бесконечной выборке равна 1/6, но если мы хотим узнать результат каждого броска игральной кости, мы никогда не сможем точно рассчитать прогноз. использовать: вероятность (теория), чтобы описать этот результат. Точно так же, как роль закона Ньютона в механике для механического анализа, случайный процесс в теории вероятностей, метод изучения движения вещей изменяется, и точное математическое описание движения в условиях неопределенности. Точно так же, как математические определения таких понятий, как скорость и ускорение в механике, два наиболее важных понятия также определяются в случайных процессах: вероятностное пространство и случайные величины, которые не будут подробно обсуждаться здесь.

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

Зная, что такое случайный процесс, мы можем представить себе простейший случайный процесс, Этот процесс состоит из N шагов, каждый шаг имеет два варианта выбора (0, 1), затем есть 2 возможных пути к степени N, этот случайный процесс описывается по вероятности экспоненциального числа 2 ^ N, давайте посмотрим на экспоненциальный уровень! ? Не взорвется ли он при таком большом измерении? ? ? в настоящее время,Вводятся марковские процессы: результат каждого шага стохастического процесса связан и связан только с предыдущим шагом и никак иначе.

Процесс Макова выражается математическим языком какЦепь Маркова. В цепи Маркова изменение случайного процесса зависит только от текущего изменения, а не от истории, что мгновенно упрощает огромные вычисления.

2 Конкретные примеры цепей Маркова

Мы используем конкретный пример из реальной жизни для описания такого процесса, как цепь Маркова. Предположим, что Джинджин каждый день находится в трех состояниях: игра, учеба, сон (этоГосударственное распределение). Зная, что он играет сегодня, какова вероятность того, что завтра он будет учиться, играть и спать? Какова вероятность учиться, играть и спать послезавтра или даже через N дней?

Конечно, чтобы узнать, какова вероятность обучения, игры и сна через N дней, нам нужны два условия:

Условие предвидения: знание состояния входа в первый день (Матрица распределения состояний S),

Гипотеза: то есть переход моего состояния закономерен, то есть вероятность учиться сегодня, играть или спать или продолжать учиться завтра определена, Короче говоря, у нас есть определенное состояние предсказания.Матрица вероятности перехода состояния P.Приведенная выше матрица определяетсяматрица вероятности перехода P, она однородна во времени, иными словами, матрица вероятности перехода P остается неизменной, матрица вероятности перехода из первого дня во второй день и матрица вероятности перехода из второго дня в третий день одинаковы.

С помощью этой матрицы вероятности перехода P плюс известной матрицы распределения состояний в первый день (вероятность игры, обучения или сна в первый день) можно рассчитать распределение состояний N-го дня (вероятность игры, обучения или сна). в N-й день).

хорошо, теперь у нас есть все условия, чтобы вычислить, играем ли мы, учимся или спим через n дней, то естьМатрица распределения начального состояния Sиматрица вероятности перехода P. Предположим, вы входите в первый деньМатрица распределения состояний S1= [0,3, 0,4, 0,3], числа внутри представляют вероятность играть, учиться и спать в первый день.

Так

Матрица распределения состояний S2 = S1 * P (перемножение двух матриц) на следующий день.

На третий день матрица распределения состояний S3 = S2 * P (относится только к S2).

На четвертый день матрица распределения состояний S4 = S3 * P (относится только к S3).

...

Матрица распределения состояний Sn = Sn-1 * P (только в отношении Sn-1) на n-й день.

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

3. Свойства цепей Маркова

Продолжая приведенный выше пример, в приведенном выше примере матрица распределения начальных состояний S1 = [0,3, 0,4, 0,3], то есть вероятность игры в первый день составляет 30%, вероятность обучения составляет 40% и вероятность сна составляет 30%.Вероятность составляет 30%, и мы используем это для расчета распределения вероятности игры, обучения или сна через 100 дней, то есть на 100-й день.

код показывает, как показано ниже:

import numpy as np

matrix = np.matrix([[0.05, 0.75, 0.2],
                    [0.8, 0.05, 0.15],
                    [0.25, 0.5, 0.25]])
vector1 = np.matrix([[0.3, 0.4, 0.3]])

for i in range(100):
    vector1 = vector1 * matrix
    print('第{}轮'.format(i+1))
    print(vector1)

Результаты приведены ниже:

...
第96轮
[[0.39781591 0.41341654 0.18876755]]
第97轮
[[0.39781591 0.41341654 0.18876755]]
第98轮
[[0.39781591 0.41341654 0.18876755]]
第99轮
[[0.39781591 0.41341654 0.18876755]]
第100轮
[[0.39781591 0.41341654 0.18876755]]

Из результатов можно узнать, что начальное состояние и матрица переходов одного дня, как известно, вычисляются позже, а когда расчет начинается в определенный день, то распределение вероятностей состояния в будущем останется неизменным, и оно будет остаются [0,39781591, 0,41341654, 0,18876755]. Может ли это быть совпадением? Если матрица распределения исходного состояния S1 не равна [0,3, 0,4, 0,3], будет ли результат по-прежнему равен [0,39781591, 0,41341654, 0,18876755]? Проведем второй эксперимент, на этот раз запустим матрицу распределения состояний S1 = [0,2, 0,6, 0,2].

код показывает, как показано ниже:

import numpy as np

matrix = np.matrix([[0.05, 0.75, 0.2],
                    [0.8, 0.05, 0.15],
                    [0.25, 0.5, 0.25]])
vector1 = np.matrix([[0.2, 0.6, 0.2]])

for i in range(100):
    vector1 = vector1 * matrix
    print('第{}轮'.format(i+1))
    print(vector1)

результат операции:

...
第96轮
[[0.39781591 0.41341654 0.18876755]]
第97轮
[[0.39781591 0.41341654 0.18876755]]
第98轮
[[0.39781591 0.41341654 0.18876755]]
第99轮
[[0.39781591 0.41341654 0.18876755]]
第100轮
[[0.39781591 0.41341654 0.18876755]]

Произошло нечто удивительное! При различных начальных распределениях вероятностей распределение вероятностей конечного состояния стремится к одному и тому же устойчивому распределению вероятностей [0,39781591, 0,41341654, 0,18876755].

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

Теперь мы можем суммировать свойства сходимости цепей Маркова на математическом языке:

Если апериодическая цепь Маркова имеет матрицу перехода состоянийP,и любые два его состояния связаны, то $\text{lim}_{\text{n} \rightarrow \infty } p^{n}_{ij}$ Независимо от i имеем:

один. $\text{lim}_{\text{n} \rightarrow \infty } p^{n}_{ij}=\pi \left( j\right)$

два. $\lim_{n\rightarrow \infty } p^{n}=\begin{bmatrix}\pi \left( 1\right) &\pi \left( 2\right) &...&\pi \left( j\right) &...\\ \pi \left( 1\right) &\pi \left( 2\right) &...&\pi \left( j\right) &...\\ ...&...&...&...&...\\ \pi \left( 1\right) &\pi \left( 2\right) &...&\pi \left( j\right) &...\\ ...&...&...&...&...\end{bmatrix}$

три. $\text{lim}_{\text{n} \rightarrow \infty } p^{n}_{ij}=\pi \left( j\right)$

4. π — единственное неотрицательное решение уравнения πP = P, где:

$\pi =\left[ \pi \left( 1\right) ,\pi \left( 2\right) ,...,\pi \left( j\right) ,...\right] \ \sum^{\infty }_{i=0} \pi \left( i\right) =1$

Среди вышеперечисленных свойств, которые необходимо объяснить, следующие:

Апериодическая цепь Маркова: в основном это означает, что переход состояния цепи Маркова не является циклическим, и если он циклический, он никогда не сойдется. К счастью, цепи Маркова, с которыми мы сталкиваемся, обычно апериодичны. Математически это так: для любого состояния i d есть множество $\left\{ n|n\geq 1,p^{n}_{ij}>0\right\}$ Наибольший общий делитель , если ?=1 , состояние апериодическое
Любые два состояния связаны: это означает, что любое состояние может достичь любого другого состояния за конечные шаги, и не будет ситуации, когда условная вероятность всегда равна 0, что приводит к недостижимости.
Количество состояний в цепи Маркова может быть конечным или бесконечным. Следовательно, его можно использовать для непрерывного распределения вероятностей и дискретного распределения вероятностей.
? часто называют стационарным распределением цепи Маркова.

Справочная статья:

Как глубоко понять смысл случайного процесса?

Какая, к черту, цепь Маркова?

MCMC (2) Цепь Маркова