Введение в цепь Маркова и ее свойства
Цепь Маркова — относительно простая концепция в области случайных процессов. Мы можем думать о случайном процессе как о наборе случайных величин, индексированных по времени. В качестве простого примера мы можем рассматривать серию подбрасывания монеты как случайный процесс. Каждое из подбрасываний является случайной величиной Бернулли (может принимать одно из двух состояний), и мы можем их индексировать в соответствии с порядком подбрасывания.
Как правило, результат случайной величины X(n+1) может зависеть от предыдущих результатов {X(0), … , X(n)}
но в некоторых случаях P(X(n+1)) зависит только от предыдущего состояния, P(X( п)), а не по всей истории
Это свойство называется марковским свойством. Свойство говорит, что будущее состояние (X(n+1)) зависит только от текущего состояния (X(n )) а не на прошлые состояния. (Дискретный) случайный процесс, удовлетворяющий марковскому свойству в любой момент времени, называется марковской цепью.
Соответственно, мы можем описать цепь Маркова как конечный автомат — у нас есть несколько состояний (возможных результатов случайного процесса) и некоторая переходная вероятность перехода из одного состояния в другое. Например, давайте подумаем об автомате казино, который может выводить три числа {1,2,3}, как показано на следующей диаграмме:
Стрелки представляют вероятность перехода из состояния в состояние. Поскольку это цепь Маркова, вероятность перехода в определенное состояние зависит только от текущего состояния. Например, если сейчас автомат казино показывает число 1, вероятность получить 2 в следующем раунде равна 0,6. Обратите внимание, что поскольку мы имеем дело с вероятностью, сумма веса всех стрелок, выходящих из определенного состояния, должна быть равна 1.
Приведенную выше диаграмму можно представить с помощью матрицы P, которая называется матрицей перехода. Каждая строка матрицы описывает вероятность перехода в другие состояния (стрелки на диаграмме). В нашем случае матрица перехода
Вы снова видите, что сумма каждой строки равна 1. Запись (i, j) — это вероятность перехода из состояния i в состояние j. Предположим, что сейчас мы находимся в состоянии 1. Мы можем записать его в виде вектора состояния π = (1, 0, 0), и, умножив его на матрицу перехода, мы получим вероятности следующего состояния
Это означает, что если мы знаем, что находимся в состоянии 1, в следующем раунде у нас есть вероятности 0,2, 0,6 и 0,2 оказаться в состоянии 1, 2 или 3 соответственно.
Что насчет следующего состояния? Опять же, мы можем взять наш новый вектор состояния вероятности и умножить его на матрицу перехода, чтобы получить вероятности после двух раундов, когда мы начинаем с состояния 1. Мы можем продолжать столько раз, сколько захотим.
Из приведенного выше примера видно, что если мы начнем с известного состояния π, мы можем узнать, каковы вероятности различных состояний после m раундов, просто умножив π на P в степени m. .
Стационарное состояние
В некоторых случаях после большого количества раундов вероятность состояний будет постоянной. Если этот вектор состояния постоянной вероятности равен π, он должен быть таким:
Это уравнение является уравнением на собственный вектор с собственным значением, равным 1. Мы можем решить это уравнение вместе с тем фактом, что сумма π должна быть равна 1 (как вектор вероятности), чтобы найти стационарное состояние.
В нашем примере мы можем решить и увидеть, что π = (0,3521, 0,2112, 0,4366) (попробуйте умножить на матрицу перехода).
Прошлое Забвение
Вообще говоря, стационарное состояние цепи Маркова зависит от начального состояния. Рассмотрим следующую схему:
Мы видим, что если наше начальное состояние равно 1, мы не можем перейти в какое-либо другое состояние, поэтому после каждого шага мы все еще находимся в состоянии 1. То же самое верно и для состояния 4. Если мы начнем с состояния 2 или 3, мы можем закончить в состоянии 1 или в состоянии 4. Но бывают случаи, когда начальное состояние не имеет значения.
Мы говорим, что цепь Маркова забывает прошлое, если после бесконечных шагов вероятность перехода в состояние j не зависит от начального условия.
Если это так, то существует вектор состояния вероятности π(∞), такой как
поэтому π(∞) является стационарным состоянием. Поскольку π(0) не зависит от начального состояния, а предел должен существовать (и быть одинаковым) для любого π(0), мы можем посмотреть на стандартном базисе eᵢ = ( 0, 0, …, 0, 1, 0, …, 0), т.е. 1 только в i-й позиции:
и в результате, если цепь Маркова забывает прошлое, мы получаем
Это означает, что в столбце есть только одно значение, поэтому вероятность перехода в определенное состояние одинакова независимо от текущего состояния, как мы определили его в начале.
Классификация состояний в цепи Маркова
Возможности перехода из состояния в состояние приводят к нескольким классам состояний:
- Доступность — состояние j называется доступным из i, если существует конечное множество шагов, ведущих из i на j. Например, состояние 3 доступно из состояния 1, но состояние 1 недоступно из состояния 5.
- Связность — состояния связаны, если между ними существует двусторонняя доступность. Например, 1 и 3 связаны, потому что 3 доступен из 1, а 1 доступен из 3.
- Класс — группа связанных состояний. {1, 2, 3, 4} и {5} — это классы на приведенной выше схеме.
- Рекуррентное состояние — состояние, доступное из всех доступных из него состояний. Состояние 5 является повторяющимся состоянием.
- Переходное состояние — состояние, которое не повторяется. Есть шанс, что после многих шагов мы не сможем вернуться к такому состоянию. 1, 2, 3 и 4 — переходные состояния, потому что, если мы перейдем в состояние 5, мы никогда не сможем вернуться ни к одному из них.
