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