UK 
EnglishТипова
Polski🎲 Ланцюг Маркова — симулятор матриці переходів
Інтерактивна візуалізація ланцюгів Маркова. Редагуйте матрицю переходів, стежте за еволюцією розподілу станів, знаходьте стаціонарний розподіл. Пресети: погода, PageRank, задача гравця.
Про симулятор ланцюгів Маркова
Цей симулятор візуалізує ланцюг Маркова з дискретним часом як орієнтований граф станів, з'єднаних імовірностями переходу. Система повністю визначається матрицею переходів 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 трактує вебсторінки як стани, а випадкового серфера — як блукача; важливість сторінки — це її стаціонарна ймовірність. Ланцюги Маркова Монте-Карло (MCMC) обертають цю ідею: будують ланцюг, чий стаціонарний розподіл є цільовим розподілом, з якого потрібна вибірка, а потім отримують семпли, запускаючи ланцюг — наріжний камінь баєсівської статистики та фізики.