Метод квазі-Монте-Карло

Метод квазі-Монте-Карло (англ. Quasi-Monte Carlo Method) — метод чисельного інтегрування та розв'язування деяких інших задач з використанням послідовностей з низьким рівнем невідповідності (так-звані квазі-випадкові послідовності або суб-випадкові послідовності). Це на противагу звичайному методу Монте-Карло, який заснований на послідовності псевдовипадкових чисел.

[Псевдовипадкова послідовність]

[Соболева послідовність - послідовність із малою розбіжністю]

256 точок з джерела псевдовипадкових чисел, послідовність Хальтона та Соболева послідовність (Червоні=1,..,10, Сині=11,..,100, Зелені=101,..,256). Точки Соболевої послідовності є більш рівномірно розподіленими.

Методи Монте-Карло і квазі-Монте-Карло викладені аналогічним чином. Проблема полягає  в тому, щоб апроксимувати інтеграл від функції f як середнє значення функції, обчисленої в наборі точок х₁, …, х_п:

${\displaystyle \int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}$

Оскільки ми інтегруємо по х-вимірному одиничному кубі, кожен х_i є вектором s елементів. Різниця між методами квазі-Монте-Карло і Монте-Карло — це спосіб вибору х_i.  Квазі-Монте-Карло використовує послідовності з низьким рівнем невідповідності, такі як послідовності Халтон, Соболеві послідовності, або послідовності Фора (з англ. Faure), в той час як метод Монте-Карло використовує псевдовипадкові послідовності. Перевага використання послідовностей з низьким рівнем невідповідності — швидкість збіжності. Метод квазі-Монте-Карло має оцінку збіжності  О(1/n), тоді як у випадку методу Монте-Карло вона становить О(N^−0.5).^[1]

Метод квазі-Монте-Карло останнім часом став популярним в області математичних фінансів і фінансових обчислень. В цих областях багатовимірні числові інтеграли, де значення інтегралу повинне бути оцінене в межах порогового значення ε, трапляються часто. Методи Монте-Карло і квазі-Монте-Карло корисні в таких випадках.

Оцінка похибки апроксимації методу квазі-Монте-Карло

Апроксимаційна похибка методу квазі-Монте-Карло обмежена значенням, пропорційним невідповідності комплекту х₁, …, х_n. Зокрема, з нерівності Koksma-Hlawka маємо, що похибка

${\displaystyle \epsilon =\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|}$

є обмеженою

${\displaystyle |\epsilon |\leq V(f)D_{N}}$,

де V(F) є варіацією Харді-Краузе для функції f (див. Morokoff і Кафлиш (1995) для детального визначення). Dn — це так звана головна  розбіжність набору (х₁,…,x_n) і визначається як

${\displaystyle D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\mbox{number of points in }}Q}{N}}-{\mbox{volume}}(Q)\right|}$,

де Q — прямокутна [0,1]^s фігура зі сторонами, паралельними осям координат. Нерівність ${\displaystyle |\epsilon |\leq V(f)D_{N}}$ може бути використана, щоб показати, що похибка апроксимації методом квазі-Монте-Карло метод рівна ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$, у той час як метод Монте-Карло має імовірнісну похибку ${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$. Хоча ми можемо тільки констатувати верхню межу похибки апроксимації, збіжність розрахунку методу квазі-Монте-Карло на практиці, як правило, набагато швидша за його теоретичну межу. Отже, в загальному випадку, точність методу квазі-Монте-Карло збільшується швидше, ніж збіжність методу Монте-Карло. Однак, ця перевага забезпечується тільки якщо N досить велике і якщо варіація скінченна.

Методи Монте-Карло та Квазі-Монте-Карло для багатовимірних інтегрувань

Для одновимірного інтегрування, квадратурні методи, такі як методи трапецій, Сімпсона, або формула Ньютона–Котеса, відомі як ефективні, якщо функція є гладкою. Ці підходи можуть бути також використані для багатовимірної інтеграції, повторюючи одновимірні інтегрування за кількома вимірами. Однак кількість обчислень функції зростає експоненціально з числом вимірів s. Отже, щоб подолати це прокляття розмірності слід використовувати для багатовимірних інтегралів дещо інший метод. Стандартний метод Монте-Карло часто використовується, коли квадратурні методи складно або дорого реалізувати.^[2] Методи Монте-Карло і квазі-Монте-Карло точні і відносно швидкі, коли розмірність сягає 300 і вище.^[3]

Мороков і Кафлиша вивчали продуктивність методів Монте-Карло і квазі-Монте-Карло у інтегруванні. У статті, Халтон, Соболь, і Фор послідовності для квазі-Монте-Карло порівнюють із стандартним методом Монте-Карло з використанням псевдовипадкових послідовностей. Вони виявили, що метод з  Халтон послідовністю найбільш ефективний для розмірностей до приблизно 6; метод з Соболевими послідовністями працює краще для більш високих розмірностей; і метод з Фор послідовностями, хоч і є гіршим за вказані дві інші послідновності, досі працює краще, ніж псевдовипадкові послідовності.

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

Недоліку методу квазі-Монте-Карло

Лем'є виділив недоліки методу квазі-Монте-Карло:^[4]

• Для того щоб оцінка ${\displaystyle O\left({\frac {(\log N)^{s}}{N}}\right)}$ була меншою за ${\displaystyle O\left({\frac {1}{\sqrt {N}}}\right)}$,${\displaystyle s}$ повинен бути достатньо малим і ${\displaystyle N}$ повинен бути великим (наприклад, ${\displaystyle N>2^{s}}$).
• Для багатьох функцій, що виникають на практиці, ${\displaystyle V(f)=\infty }$.
• Ми знаємо тільки верхню межу помилки (тобто ε ≤ V(f) D_N), і важко обчислити ${\displaystyle D_{N}^{*}}$ і ${\displaystyle V(f)}$.

Для того, щоб подолати деякі з цих недоліків, ми можемо використати рандомізований метод квазі-Монте-Карло .

Рандомізування методу квазі-Монте-Карло

Оскільки послідовності з низьким рівнем розбіжності не випадкові, а детерміновані, квазі-Монте-Карло метод може розглядатися як детермінований алгоритм або дерандомізований алгоритм. В даному випадку, у нас є тільки межа (наприклад, ε ≤ (Ф) Г_Н) похибки, і похибку важко оцінити. Для того, щоб уможливити аналіз та оцінку дисперсії, ми можемо рандомізувати метод (див. рандомізації для загального випадку). В результаті отримаємо рандомізований метод квазі-Монте-Карло, який також можна розглядати як зменшення варіації для стандартного методу Монте-Карло.^[5] Серед декількох методів, найпростіша процедура перетворень — це через випадкові зміщення. Нехай {х₁,…,х_п} точка встановлена на послідовності з низькою розбіжністю. Оберемо випадковий s-вимірний  вектор U і змішаємо його з {х₁,…,х_п}. Тобто, для кожного x_J, створюємо

${\displaystyle y_{j}=x_{j}+U{\pmod {1}}}$

і використовуємо послідовність ${\displaystyle (y_{j})}$ замість ${\displaystyle (x_{j})}$. Якщо ми маємо R повторів за методом Монте-Карло, оберемо випадковий s-вимірний вектор U для кожної реплікації. Рандомізація дозволяє дати оцінку дисперсії, при цьому використовуючи квазі-випадкові послідовності. Порівняно з чисто методом квазі-Монте-Карло, кількість зразків квазі-випадкової послідовності буде ділитись на R, рівноцінну за обчислювальних витрат, що зменшує теоретичну швидкість збіжності. У порівнянні зі стандартним методом Монте-Карло, дисперсії та обчислення швидкості є дещо кращі, ніж експериментальні результати у Туффіна (2008)^[6]

Див. також

• Метод Монте-Карло