Методи Монте-Карло марковських ланцюгів

Коли методи МКМЛ застосовуються для наближення багатовимірних інтегралів, то всюди випадково рухається ансамбль ходаків. У кожній точці, де ступає ходак, до інтегралу зараховується значення підінтегрального в цій точці. Потім ходак може зробити якусь кількість пробних кроків цією зоною, шукаючи місця з прийнятно високим внеском до інтегралу, щоби рухатися туди далі.

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

Приклади методів Монте-Карло випадкового блукання включають наступні:

• Алгоритм Метрополіса — Гастінгса: Цей метод породжує випадкове блукання із застосуванням густини пропозиції та методу відкидання деяких із запропонованих рухів.
• Вибірка за Ґіббсом: Цей метод вимагає, щоби було точно вказано вибірки з усіх умовних розподілів цільового розподілу. Він є популярним зокрема тому, що не вимагає жодного «регулювання».
• Вибірка за рівнями: Цей метод залежить від того принципу, що можна робити вибірку з розподілу шляхом рівномірної вибірки з області під графіком функції його густини. Він чергує рівномірну вибірку у вертикальному напрямку з рівномірною вибіркою з горизонтального «рівня», визначеного поточною вертикальною позицією.
• Багатоспробовий метод Метрополіса: Цей метод є варіацією алгоритму Метрополіса — Гастінгса, що дозволяє багаторазові спроби у кожній точці. Дозволяючи робити більші кроки на кожній ітерації, він допомагає розв'язувати прокляття розмірності.
• Реверсивно-стрибковий: Цей метод є варіацією алгоритму Метрополіса — Гастінгса, що дозволяє пропозиції, які змінюють розмірність простору.[4] Методи МКМЛ, що змінюють розмірність, тривалий час застосовуватися у статистичній фізиці, де для деяких задач використовується розподіл, що є великим канонічним ансамблем (наприклад, коли кількість молекул у коробці є змінною). Але реверсивно-стрибковий варіант є корисним при виконанні МКМЛ або вибірки за Ґіббсом над непараметричними баєсовими моделями, такими як пов'язані з процесом Діріхле чи процесом китайського ресторану, де кількість змішуваних складових/кластерів/тощо автоматично виводиться з даних.

Взаємодійні методології МКМЛ є класом методів частинок осередненого поля для отримання випадкових виборок із послідовності розподілів ймовірності зі зростаючим рівнем складності вибірки.[5] Ці ймовірнісні моделі включають моделі простору шляху зі збільшуваним часовим горизонтом, апостеріорними розподілами відносно послідовності часткових спостережень, збільшуваними наборами рівнів обмежень для умовних розподілів, зменшуваними графіками температури, пов'язаними з деякими розподілами Больцмана — Ґіббса, та багато інших. У принципі, будь-який відбірник МКМЛ може бути перетворено на взаємодійний відбірник МКМЛ. Ці взаємодійні відбірники МКМЛ може бути інтерпретовано як спосіб паралельного виконання відбірників МКМЛ. Наприклад, взаємодійні імітаційні алгоритми ренатурації базуються на незалежних кроках Метрополіса — Гастінгса, що послідовно взаємодіють з механізмом типу вибору/повторного взяття вибірки. На відміну від традиційних методів МКМЛ, параметр точності цього класу взаємодійних відбірників МКМЛ стосується лише кількості відбірників МКМЛ, що взаємодіють. Ці передові частинкові методології належать до класу частинкових моделей Фейнмана-Каца,[6][7] що у спільнотах баєсового висновування та обробки сигналів називаються також послідовними методами Монте-Карло, або частинковими фільтрами.[8] Взаємодійні методи МКМЛ також може бути інтерпретовано як генетичні частинкові алгоритми мутації-відбору з мутаціями МКМЛ.

Методи квазі-Монте-Карло марковських ланцюгів (КМКМЛ, англ. Markov Chain quasi-Monte Carlo, MCQMC).[9][10] Перевага використання малорозбіжних постідовностей замість випадкових чисел для простої незалежної вибірки Монте-Карло є добре відомою.[11] Ця процедура, відома як Метод квазі-Монте-Карло (КМК, англ. Quasi-Monte Carlo method, QMC),[12] згідно нерівності Коксма-Главка дає інтеграційну помилку, що спадає значно швидше, ніж отримувана за допомогою вибірки НОР. Емпірично це дозволяє зменшувати як помилку оцінки, так і тривалість збіжності, на порядок величини.^{[джерело?]}

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

Приклади методів МКМЛ не випадкового блукання включають наступне:

• Гібридний алгоритм Монте-Карло (ГМК, англ. Hybrid Monte Carlo, HMC): Намагається уникнути поведінки випадкового блукання за допомогою введення додаткового вектора імпульсу та реалізації гамільтонової динаміки, так, що функція потенціальної енергії є цільовою густиною. Імпульсні елементи вибірки відкидаються після вибірки. Кінцевим результатом гібридного алгоритму Монте-Карло є те, що пропозиції рухаються простором вибірки більшими кроками; вони відтак є менш корельованими, та швидше згортаються до цільового розподілу.
• Деякі варіації вибірки за рівнями також уникають випадкового блукання.[13]
• МКМЛ Ланжевена, та інші методи, що покладаються на градієнт (та, можливо, другу похідну) логарифму апостеріорного, уникають випадкового блукання, роблячи пропозиції, що правдоподібніше знаходяться в напрямку вищої густини ймовірності.[14]