Марковські ланцюги: збіжність, змішування та власні значення

Розподіл, який оновлює себе

Марковська ланцюг – це набір станів і матриця переходу P, де елемент P_ij є ймовірністю переходу з стану i до стану j за один крок. За будь-якого початкового розподілу π₀ над станами – рядок ймовірностей – розподіл через один крок визначається як π₁ = π₀ * P, а повторне застосування цього вперед є цілим моделюванням.

π_{t+1} = π_t · P                one step of the chain
π★ P = π★                      stationary distribution: a left eigenvector of P with eigenvalue 1

Чому існує унікальне стаціонарне розподіле

Для ланцюга, що є незвідним (кожна стан може врешті-решт досягти будь-якого іншого стану) та періодичним (він не потрапляє в циклічні переміщення через стани з фіквованою частотою), теорема Перрона–Фробена гарантує існування унікального стаціонарного розподілу π*, до якого сходиться будь-який початковий розподіл, незалежно від того, звідки він почався. Ця комбінація незвідності та періодичності має назву – ергодична ланцюг, і це саме те, що задовольняють або навмисно порушують пресети «погода» та «гравець у рулетку».

Как быстро происходит схождение

Досягнення стаціонарної розподіленої не є миттєвим, і швидкість визначається власними значеннями P за виключенням одного, який завжди дорівнює точно 1. Відсортуйте власні значення за величиною; друге найбільше, λ₂, контролює, як швидко спадає тимчасова частина розподілу, зменшуючись приблизно як |λ₂|ᵗ після t кроків. Проміжок між 1 та |λ₂| називається спектральним проміжком, і більший проміжок означає швидше змішування — ланцюг «забуває» свій початковий стан раніше. Ланцюг із власним значенням близьким до 1 окрім лідера буде виглядати майже замороженим надовго перед тим, як різко встановитися, що точно відповідає вигляду майже розкладеної матриці переходу (дві слабко з’єднані кластери станів на екрані).

x_{t+1} = Pᵀ x_t / ||Pᵀ x_t||       power iteration — converges to π★ at rate |λ₂/λ₁|

Зворотність – це зручний спосіб, а не вимога

Деякі ланцюги задовольняють детальному балансу: π★_i P_ij = π★_j P_ji, що означає, що потік ймовірностей від i до j точно збалансований потоком назад від j до i. Такі ланцюги називаються зворотними, і їх розподіл стабільної рівноваги часто можна записати у замкнутому вигляді без жодних обчислень власних векторів – це ключ до методів Markov chain Monte Carlo. Більшість реальних ланцюгів, включаючи модель веб-переглядача PageRank, не є зворотними; вони все ще мають добре визначену розподіл стабільної рівноваги, просто для нього немає швидкого формули.

Два пресети, дві структурні відмінності

Пресет PageRank моделює веб-серфера, який випадково переходить за посиланнями, з невеликою ймовірністю затухання (dampening), яка дозволяє випадковим чином переходити на будь-яку сторінку – цей термін ‘телепортації’ є важливим, оскільки він гарантує, що мережевий граф (який сам по собі може мати безвихідні кінцеві точки або відключені кластери) стає незвідним та періодичним, і таким чином існує унікальний стаціонарний розподіл. Навпаки, Gambler’s ruin навмисно не є ергодичним: він має два поглинаючі стани (банкрут або досягнуто цілі), кожен з ймовірністю самозв'язку 1, що призводить до того, що масове ймовірність стікається в них, а не циркулює вічно – цікавим питанням тут є не стаціонарний розподіл, а ймовірність потрапити в один із цих поглинаючих станів проти іншого.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Markov Chain і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.