Monte Carlo в статистичній механіці: алгоритм Метрополіса

1. Проблема вибірки

Статистична механіка стверджує, що система в тепловій рівновазі за температури T відвідує конфігурацію (мікростан) i з імовірністю, заданою розподілом Больцмана:

Для будь-чого, крім іграшкової системи, Z — астрономічно велика сума: решітка з усього 20×20 спінів Ізінга вже має 2⁴⁰⁰ ≈ 10¹²⁰ мікростанів — більше, ніж атомів у видимому Всесвіті. Обчислення термодинамічних середніх шляхом буквального підсумовування за кожним мікростаном тому неможливе. Звичайний Monte Carlo — вибірка конфігурацій рівномірно навмання з подальшим зважуванням фактором Больцмана — також безнадійний: за низької температури переважна більшість випадкових вибірок потрапляє на високоенергетичні стани з практично нульовою вагою, марнуючи майже всі обчислювальні зусилля.

2. Алгоритм Метрополіса

Алгоритм Метрополіса будує марковський ланцюг — послідовність конфігурацій, де кожна залежить лише від попередньої — чия довгострокова частота відвідування збігається до розподілу Больцмана. Кожен крок:

Правило прийняття завжди приймає рухи, що знижують енергію, і лише зрідка приймає рухи, що підвищують енергію, з імовірністю, що спадає експоненційно з ΔE — саме той баланс, що потрібен, щоб витрачати більшість обчислювальних зусиль поблизу термодинамічно важливих, низькоенергетичних конфігурацій, водночас час від часу досліджуючи високоенергетичні стани (що дозволяє системі уникати локальних мінімумів і коректно вибирати теплові флуктуації).

3. Детальна рівновага і чому це працює

Коректність алгоритму спирається на детальну рівновагу: у рівновазі потік імовірності зі стану i в стан j має точно дорівнювати зворотному потоку з j в i:

Розкладаючи імовірність переходу на імовірність пропозиції g(i→j) (обрану симетричною, g(i→j) = g(j→i), для простої пропозиції на кшталт перевертання випадкового спіна) та імовірність прийняття A(i→j), детальна рівновага вимагає:

Вибір Метрополіса A(i→j) = min[1, exp(−ΔE/k_BT)] є одним із валідних розв'язків цього співвідношення (серед кількох можливих правил прийняття — правило Глаубера/теплової бані A = 1/(1+exp(ΔE/k_BT)) є ще одним). На практиці вибір Метрополіса переважає, оскільки максимізує коефіцієнт прийняття за умови задоволення детальної рівноваги, змушуючи марковський ланцюг досліджувати простір конфігурацій якомога ефективніше.

4. Практичні міркування

• Врівноваження (розігрів): ланцюг стартує з довільної конфігурації і потребує кількох кроків, щоб "забути" початковий стан і почати вибирати справжній рівноважний розподіл. Ці ранні кроки відкидають перед обчисленням середніх.
• Час автокореляції: послідовні конфігурації в ланцюзі корельовані (кожна відрізняється від попередньої лише одним невеликим рухом). Вибірки мають бути розділені приблизно часом автокореляції τ, перш ніж їх можна вважати статистично незалежними для оцінки похибки.
• Критичне уповільнення: поблизу фазового переходу (напр., точки Кюрі моделі Ізінга) τ розходиться, вимагаючи набагато більше кроків для коректної вибірки. Кластерні алгоритми (Вольфа, Свендсена-Ванга) розроблено саме для подолання цього шляхом перевертання цілих корельованих кластерів спінів за один рух.
• Налаштування коефіцієнта прийняття: для неперервних змінних (напр., зсув частинки) розмір кроку пропозиції налаштовують так, щоб приймалося приблизно 30-50% рухів — надто малий крок марнує час на дрібні рухи; надто великий крок майже завжди відхиляється.

5. Приклад: модель Ізінга

2D-модель Ізінга — сітка спінів sᵢ = ±1 з енергією E = −J·Σ⟨ij⟩ sᵢsⱼ за парами найближчих сусідів — канонічний тестовий випадок Метрополіса. Перевертання одного спіна sₖ змінює енергію на суто локальну величину:

Оскільки ΔE залежить лише від чотирьох (або шести, або восьми, залежно від геометрії решітки) сусідів переверненого спіна, обчислення критерію прийняття коштує O(1) незалежно від розміру системи — саме ця локальність робить Метрополіс Monte Carlo для граткових моделей на кшталт Ізінга надзвичайно швидким на крок, навіть якщо для досягнення рівноваги поблизу критичної температури можуть знадобитися мільйони кроків.

6. Поза межами фізики

Обчислювальна хімія та молекулярна симуляція

Методи Monte Carlo доповнюють молекулярну динаміку (див. наш супутній матеріал про потенціал Леннарда-Джонса) щоразу, коли цікава величина — термодинамічне середнє, а не часозалежна властивість. Рухи Метрополіса — зсув молекули, обертання чи спроба вставити/видалити її (великий канонічний Monte Carlo) — робочий інструмент для симуляції фазових рівноваг, адсорбції та вільних енергій сольватації.

Байєсівська статистика та машинне навчання

Узагальнення Метрополіса-Гастінгса (що дозволяє асиметричні пропозиції) лежить в основі методів марковського ланцюгового Monte Carlo (MCMC), що використовуються по всій байєсівській статистиці для вибірки апостеріорних розподілів, які не мають замкненої форми — від оцінки космологічних параметрів до байєсівського виведення в нейромережах.

Комбінаторна оптимізація

Симульоване відпалювання — поступове зниження штучного параметра "температури" в циклі Метрополіса, застосованого до функції вартості, а не фізичної енергії — це універсальна евристика оптимізації для задач на кшталт комівояжера, компонування схем та передбачення структури білка, де правило прийняття Метрополіса дозволяє рухи "вгору" на ранніх етапах, щоб уникнути поганих локальних оптимумів.