Ця симуляція анімує ланцюг Маркова з дискретним часом на скінченній множині станів. Випадковий блукач переходить між станами відповідно до матриці переходів P, де кожен рядок містить імовірності переходу до кожного іншого стану й у сумі дорівнює 1. Діаграма станів малює вузли по колу зі стрілками, товщина яких залежить від імовірності, а стовпчикова діаграма порівнює спостережувані частоти відвідувань зі стаціонарним розподілом π, обчисленим методом степеневих ітерацій рівняння π = πP.
Меню пресетів завантажує готові ланцюги (Погода, PageRank, Розорення гравця, Гарді — Вайнберг, випадковий ланцюг із 4 станів), повзунок затримки кроку задає темп від 50 до 2000 мс, а кнопки Крок, Запуск і Скидання керують блуканням. Ланцюги Маркова лежать в основі алгоритму PageRank від Google, розпізнавання мовлення, моделей черг і популяційної генетики, що робить їх одним із найбільш широко застосовуваних інструментів теорії ймовірностей.
Що таке ланцюг Маркова?
Ланцюг Маркова — це стохастичний процес, який переходить між множиною станів, де ймовірність наступного стану залежить лише від поточного стану, а не від шляху, яким його було досягнуто. Цю властивість відсутності пам'яті називають властивістю Маркова. Кожен крок визначається матрицею переходів, завантаженою з обраного пресету.
Що показує стовпчикова діаграма внизу?
Фіолетові стовпчики показують емпіричні частоти відвідувань, які фактично накопичив блукач, а золоті стовпчики показують теоретичний стаціонарний розподіл π. Що більше кроків виконано, то ближче фіолетові стовпчики мають збігатися із золотими, ілюструючи довгострокову поведінку ланцюга.
Як обчислюється стаціонарний розподіл?
Симуляція використовує метод степеневих ітерацій: вона починає з рівномірного розподілу й багаторазово множить його на матрицю переходів P, доки зміна між ітераціями не стане меншою за 1e-8, але не більше ніж 2000 ітерацій. Результатом є вектор π, що задовольняє рівняння π = πP, — рівноважні ймовірності ланцюга.
Крок просуває блукання рівно на один перехід. Запуск розпочинає безперервне крокування із заданою затримкою й перемикається на Паузу. Скидання перезавантажує поточний пресет, очищаючи лічильник кроків та історію відвідувань, щоб ви могли почати випадкове блукання заново.
Він задає час між автоматичними переходами під час роботи — від 50 мс (швидко) до 2000 мс (повільно) з кроком 50 мс, а за замовчуванням 600 мс. Зміна під час роботи перезапускає таймер у новому темпі, тож ви можете спостерігати кожен перехід або прискорити збіжність.
Щойно виконано понад 20 кроків, вона повідомляє середню абсолютну різницю між емпіричними частками відвідувань і стаціонарним розподілом π, показану у відсотках. Менші значення означають, що випадкове блукання тісно відповідає теоретичній рівновазі.
Розорення гравця має два поглинаючі стани, $0 і $4, до яких ланцюг може увійти, але ніколи не вийти. Такі ланцюги не мають єдиного внутрішнього стаціонарного розподілу у звичайному сенсі, тож блукання зрештою застрягає на одній із меж, моделюючи гравця, який розорюється або досягає своєї цілі.
Він моделює вебсерфера, який випадково переходить за посиланнями між чотирма сторінками. PageRank, алгоритм, що стояв за раннім пошуком Google, розглядає вебмережу як гігантський ланцюг Маркова й ранжує сторінки за їхньою стаціонарною ймовірністю, тобто за тим, як часто випадковий серфер потрапляє на них у довгостроковій перспективі.
Так, щодо показаних методів: переходи коректно вибираються з кожного рядка P за допомогою розіграшу за кумулятивною ймовірністю, а π знаходиться справжнім методом степеневих ітерацій. Матриці пресетів є ілюстративними прикладами, а не виміряними реальними даними, тож якісна поведінка достовірна, навіть якщо конкретні числа стилізовані.
Не завжди. Єдиний стаціонарний розподіл, до якого збігається блукання, гарантований, коли ланцюг є незвідним та аперіодичним. Ланцюги з поглинаючими станами, незв'язними компонентами або суворою періодичністю можуть цього не мати, тому пресети на кшталт Розорення гравця поводяться якісно інакше, ніж ланцюг Погода.