🔁 Ланцюг Маркова

Ланцюг Маркова — стохастичний процес, що задовольняє властивість Маркова: наступний стан залежить лише від поточного, але не від попередніх. Він повністю описується матрицею переходів P, де Pᵢⱼ = P(стан j | стан i), причому сума кожного рядка = 1. Повторне множення матриці πP збігається до стаціонарного розподілу π — власного вектора з власним числом 1 матриці Pᵀ. Застосування: PageRank, MCMC, приховані марковські моделі, генерація тексту. 🇬🇧 English

Пресети

Матриця переходів P

Рядки нормалізуються автоматично до суми 1
Ітерація0
Поточний стан—

Стаціонарний розподіл та збіжність

Для ергодичного (незвідного + аперіодичного) ланцюга розподіл π(t) = π(0)·Pᵗ збігається до єдиного стаціонарного розподілу π* незалежно від початкової точки. Саме на цьому базується метод Монте-Карло з ланцюгами Маркова (MCMC), що широко застосовується в байєсівській статистиці, машинному навчанні та фізиці. Швидкість збіжності визначається другим за величиною власним числом матриці P — спектральним зазором: великий зазор означає швидке перемішування.

Про симулятор ланцюга Маркова

Цей симулятор візуалізує ланцюг Маркова з дискретним часом як орієнтований граф станів, пов’язаних ймовірностями переходів. Система повністю визначається матрицею переходів P, де кожен елемент Pᵢⱼ задає ймовірність переходу зі стану i до стану j, а сума кожного рядка дорівнює 1. На кожній ітерації розподіл ймовірностей π оновлюється добутком вектора на матрицю π(t+1) = π(t)·P, а розміри вузлів відбивають еволюцію розподілу.

Ви редагуєте матрицю прямо в таблиці (рядки нормуються автоматично), обираєте готові пресети, такі як Погода, PageRank, Гравець та Випадковий, і задаєте, скільки кроків виконується за один кадр анімації. Окремого випадкового мандрівника також можна провести ланцюгом крок за кроком, щоб показати окремі вибіркові траєкторії. Такі ланцюги лежать в основі PageRank, моделювання погоди, теорії масового обслуговування та MCMC-вибірки в статистиці та машинному навчанні.

Поширені запитання

Що таке ланцюг Маркова?

Ланцюг Маркова — це випадковий процес, який перескакує між скінченною множиною станів, де ймовірність наступного стану залежить лише від поточного стану, а не від попередньої історії. Ця відсутність пам’яті називається властивістю Маркова. Ланцюг повністю задається своєю матрицею переходів P.

Що робить матриця переходів?

Кожен елемент Pᵢⱼ — це ймовірність переходу зі стану i до стану j за один крок. Сума кожного рядка має дорівнювати 1, бо ланцюг мусить кудись перейти. У цьому симуляторі ви можете ввести будь-які невід’ємні значення в таблицю, і рядки автоматично перенормуються, щоб залишатися коректними ймовірностями.

Як розподіл змінюється на кожному кроці?

Симулятор зберігає розподіл ймовірностей π по станах і оновлює його за правилом π(t+1) = π(t)·P, яке є звичайним множенням вектора на матрицю. Повторення цього еквівалентне обчисленню π(0)·Pᵗ. Відсотки, показані на вузлах і стовпчастій діаграмі, — це поточні значення цього розподілу.

Що таке стаціонарний розподіл?

Стаціонарний розподіл π* задовольняє π* = π*·P, тобто він залишається незмінним після ще одного кроку ланцюга. Це лівий власний вектор P для власного значення 1, рівнозначно власний вектор Pᵀ для власного значення 1. Для ергодичного ланцюга розподіл збігається до цього єдиного π* незалежно від початкового стану.

Що показують чотири пресети?

Погода — це класична модель із 3 станів: сонячно/хмарно/дощово. PageRank — це веб-граф із 4 вузлів, який ілюструє, як Google ранжує сторінки за стаціонарною ймовірністю. Гравець — це ланцюг руїни гравця з двома поглинаючими станами при $0 та $3. Випадковий генерує новий ланцюг із 3–5 станів із випадково згенерованими та нормованими рядками.

Що робить кнопка кроку мандрівника?

Мандрівник — це одиничний маркер, який виконує один реальний випадковий перехід щоразу, коли ви на нього натискаєте, обираючи наступний стан шляхом виборки з поточного рядка P. Його траєкторія ілюструє одну конкретну реалізацію ланцюга, на відміну від плавного розподілу π, який представляє середню поведінку по нескінченній кількості таких мандрівників.

Що керує параметр «Кроків за кадр»?

Цей повзунок задає, скільки оновлень розподілу (та кроків мандрівника) застосовується під час кожного кадру анімації, від 1 до 50. Більше значення пришвидшує ланцюг, щоб ви могли швидше побачити його збіжність до стаціонарного розподілу, тоді як значення 1 дозволяє детально спостерігати кожну ітерацію.

Коли ланцюг збігається до єдиного стаціонарного розподілу?

Збіжність до єдиного стаціонарного розподілу з будь-якого початку гарантована, коли ланцюг є ергодичним, тобто нерозкладним (кожен стан може досягти будь-якого іншого) та аперіодичним. Пресет руїни гравця не є ергодичним, бо $0 та $3 поглинаючі, тому його довгострокова поведінка залежить від початкового стану.

Що визначає швидкість збіжності?

Швидкість збіжності (або перемішування) визначається модулем другого за величиною власного значення P. Різниця між 1 і цим значенням — це спектральна щілина: велика спектральна щілина означає, що похибки швидко зменшуються і ланцюг швидко перемішується, тоді як мала щілина означає повільну збіжність. Саме тому одні ланцюги встановлюються за кілька кроків, а інші потребують багатьох.

Як це пов’язано з PageRank та MCMC?

PageRank розглядає веб-сторінки як стани, а випадкового серфера — як мандрівника; важливість сторінки — це її стаціонарна ймовірність. Метод Монте-Карло на ланцюгах Маркова перевертає ідею, будуючи ланцюг, стаціонарний розподіл якого є цільовим, із якого ви хочете вибирати, а потім бере вибірки, запускаючи ланцюг — наріжний камінь баєсівської статистики та фізики.