Настройки
Действия
Параметры Отображения
Редактор Матрицы Переходов
Каждая строка должна суммироваться до 1.0 (стохастическая матрица)
Распределение Вероятности
Сходимость к Стационарному Распределению
Математический Анализ
Текущее Распределение p_t
Стационарное Распределение π
π удовлетворяет π = πP
Собственные Значения P
λ₁ = 1 гарантировано для стохастических матриц
Свойства Цепи
Оценка Времени Смешивания
Шаги для достижения расстояния ε = 0.01 от π
Расстояние Полной Вариации
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Что такое Цепь Маркова?
Цепь Маркова - это стохастический процесс с свойством отсутствия памяти: будущее состояние зависит только от текущего состояния, а не от последовательности предшествующих событий.
Свойство Маркова
P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t)
Формула Перехода
p_{t+1} = p_t P
где p_t - вектор распределения в момент времени t, а P - матрица переходов
Ключевые Концепции
- Пространство Состояний S: Множество всех возможных состояний
- Матрица Переходов P: P[i][j] = P(X_{t+1}=j | X_t=i)
- Стохастическая Матрица: Каждая строка суммируется до 1.0
- Вероятность Пути: Произведение вероятностей перехода вдоль пути
Стационарное Распределение π
Стационарное распределение π - это распределение вероятностей, которое остаётся неизменным в цепи Маркова: как только система достигает π, она остаётся там навсегда.
Стационарное Уравнение
π = πP
или эквивалентно: π(P - I) = 0
Интерпретация Левого Собственного Вектора
π - это левый собственный вектор P, соответствующий собственному значению 1
πP = λπ where λ = 1
Существование и Единственность
- Существование: Каждая конечная цепь Маркова имеет хотя бы одно стационарное распределение
- Единственность: Гарантирована для неприводимых цепей (все состояния сообщаются)
- Перрон-Фробениус: Для регулярных цепей π имеет все положительные элементы
Расстояние Полной Вариации
δ(t) = 0.5 × Σ|p_t(i) - π(i)|
Измеряет насколько близко текущее распределение к стационарному
Свойства Сходимости
При каких условиях цепь Маркова сходится к своему стационарному распределению?
Типы Цепей
- Регулярная (Апериодическая + Неприводимая): Сходится к единственному π из любого начального распределения
- Периодическая: Состояния циклически переходят в периодическом шаблоне
- Приводимая: Содержит поглощающие состояния или несколько сообщающихся классов
Скорость Сходимости
Определяется второй по величине величиной собственного значения (SLEM):
|p_t - π| ≈ C × |λ_2|^t
Спектральный разрыв = 1 - |λ₂|, больший разрыв = более быстрая сходимость
Время Смешивания
Время чтобы быть в пределах ε от стационарного распределения:
t_mix(ε) = log(ε) / log(|λ_2|)
Обнаружение Периодичности
Состояние имеет период d, если все циклы из этого состояния имеют длины, делящиеся на d
- Апериодическая: d = 1 (может вернуться в любое время)
- Периодическая: d > 1 (циклы синхронизированы)
Детальное Равновесие (Обратимые Цепи)
π(i)P(i,j) = π(j)P(j,i)
Достаточное условие для π быть стационарным
Практические Применения
Алгоритм PageRank
PageRank от Google моделирует веб-серфинг как случайное блуждание. Стационарное распределение даёт важность каждой страницы.
P = (1-d)M + d(1/n)J
M: матрица ссылок, d: коэффициент затухания, J: матрица единиц
Случайные Блуждания на Графах
Используется в анализе сетей, системах рекомендаций и сэмплинге графов. Стационарное распределение связано со степенями узлов.
Методы Сэмплинга MCMC
Методы Монте-Карло с цепями Маркова генерируют выборки из сложных распределений вероятностей, строя цепи с целью в качестве стационарного распределения.
- Metropolis-Hastings algorithm
- Gibbs sampling
- Boltzmann machines
Скрытые Модели Маркова (HMM)
Используются в распознавании речи, биоинформатике и финансах. HMM имеют базовую цепь Маркова со скрытыми состояниями.
Теория Массового Обслуживания
Процессы рождения и смерти моделируют очереди. Стационарное распределение даёт долгосрочную вероятность наличия n клиентов в системе.
Настольные Игры
Игры вроде Монополии и Змей и Лестниц могут быть смоделированы как цепи Маркова для вычисления ожидаемой продолжительности игры и частот посещений.