Многоуровневый метод Монте-Карло

Методы многоуровневого Монте-Карло (MLMC) в численном анализе представляют собой алгоритмы расчета ожиданий , возникающих в стохастическом моделировании . Так же, как и методы Монте-Карло , они основаны на повторной случайной выборке , но эти выборки отбираются с разной степенью точности. Методы MLMC могут значительно снизить вычислительные затраты по сравнению со стандартными методами Монте-Карло, поскольку большинство образцов отбираются с низкой точностью и соответствующей низкой стоимостью, и только очень немногие образцы отбираются с высокой точностью и соответствующей высокой стоимостью.

Цель

Целью многоуровневого метода Монте-Карло является аппроксимация ожидаемого значения случайной величины , которая является результатом стохастического моделирования . Предположим, что эту случайную величину невозможно точно смоделировать, но существует последовательность аппроксимаций с возрастающей точностью, но и возрастающей стоимостью, которая сходится к как . В основе многоуровневого метода лежит тождество телескопической суммы ^[1] ${\displaystyle \operatorname {E} [G]}$ ${\displaystyle G}$ ${\displaystyle G_{0},G_{1},\ldots ,G_{L}}$ ${\displaystyle G}$ ${\displaystyle L\rightarrow \infty }$

${\displaystyle \operatorname {E} [G_{L}]=\operatorname {E} [G_{0}]+\sum _{\ell =1}^{L}\operatorname {E} [G_{\ell }-G_{\ell -1}],}$

это тривиально выполняется из-за линейности оператора ожидания. Каждое из ожиданий затем аппроксимируется методом Монте-Карло, в результате чего получается многоуровневый метод Монте-Карло. Обратите внимание, что для получения выборки разницы на уровне требуется моделирование как и . ${\displaystyle \operatorname {E} [G_{\ell }-G_{\ell -1}]}$ ${\displaystyle G_{\ell }-G_{\ell -1}}$ ${\displaystyle \ell }$ ${\displaystyle G_{\ell }}$ ${\displaystyle G_{\ell -1}}$

Метод MLMC работает, если дисперсии равны , что будет в случае, если оба и аппроксимируют одну и ту же случайную величину . По Центральной предельной теореме это означает, что нужно все меньше и меньше выборок, чтобы точно аппроксимировать математическое ожидание разницы как . Следовательно, большинство образцов будет взято на уровне , где образцы дешевы, и лишь очень небольшое количество образцов потребуется на самом высоком уровне . В этом смысле MLMC можно рассматривать как стратегию рекурсивного управления . ${\displaystyle \operatorname {V} [G_{\ell }-G_{\ell -1}]\rightarrow 0}$ ${\displaystyle \ell \rightarrow \infty }$ ${\displaystyle G_{\ell }}$ ${\displaystyle G_{\ell -1}}$ ${\displaystyle G}$ ${\displaystyle G_{\ell }-G_{\ell -1}}$ ${\displaystyle \ell \rightarrow \infty }$ ${\displaystyle 0}$ ${\displaystyle L}$

Приложения

Аппроксимация выборочного пути СДУ на разных уровнях.

Первое применение MLMC приписывается Майку Джайлсу ^[2] в контексте стохастических дифференциальных уравнений (СДУ) для ценообразования опционов , однако более ранние следы можно найти в работе Генриха в контексте параметрического интегрирования. ^[3] Здесь случайная величина известна как функция выигрыша, а последовательность аппроксимаций использует аппроксимацию пути выборки с шагом по времени . ${\displaystyle G=f(X(T))}$ ${\displaystyle G_{\ell }}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle X(t)}$ ${\displaystyle h_{\ell }=2^{-\ell }T}$

Применение MLMC к проблемам количественной оценки неопределенности (UQ) является активной областью исследований. ^{[4] [5]} Важным прототипным примером этих проблем являются уравнения в частных производных (ЧДУ) со случайными коэффициентами . В этом контексте случайная величина известна как интересующая величина, а последовательность аппроксимаций соответствует дискретизации УЧП с различными размерами ячеек. ${\displaystyle G}$

Алгоритм моделирования MLMC

Простой адаптивный к уровню алгоритм моделирования MLMC приведен ниже в псевдокоде.

 ${\displaystyle L\gets 0}$повторение Возьмите прогревающие выборки на каждом уровне Вычислите дисперсию выборки на всех уровнях Определите оптимальное количество выборок на всех уровнях Возьмите дополнительные выборки на каждом уровне в соответствии с если то ${\displaystyle L}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle N_{\ell }}$ ${\displaystyle \ell =0,\ldots ,L}$ ${\displaystyle \ell }$ ${\displaystyle N_{\ell }}$   ${\displaystyle L\geq 2}$  Тест на сходимость конец  , если не сходится, то  конец, пока не сходится ${\displaystyle L\gets L+1}$ 

Расширения MLMC

Недавние расширения многоуровневого метода Монте-Карло включают многоиндексный метод Монте-Карло ^[6] , где рассматривается более одного направления уточнения, а также комбинацию MLMC с методом квази-Монте-Карло . ^{[7] [8]}

Смотрите также

• Метод Монте-Карло
• Методы Монте-Карло в финансах
• Методы квазимонте-карло в финансах
• Количественная оценка неопределенности
• Уравнения в частных производных со случайными коэффициентами

Рекомендации

1. Джайлз, МБ (2015). «Многоуровневые методы Монте-Карло». Акта Нумерика . 24 : 259–328. arXiv : 1304.5472 . дои : 10.1017/s096249291500001x. S2CID  13805654.
2. Джайлз, МБ (2008). «Многоуровневое моделирование пути Монте-Карло». Исследование операций . 56 (3): 607–617. CiteSeerX 10.1.1.121.713 . дои : 10.1287/opre.1070.0496. S2CID  3000492. 
3. Генрих, С. (2001). «Многоуровневые методы Монте-Карло». Крупномасштабные научные вычисления . Конспекты лекций по информатике. Том. 2179. Спрингер. стр. 58–67. дои : 10.1007/3-540-45346-6_5. ISBN 978-3-540-43043-8.
4. Клифф, А.; Джайлз, МБ; Шейхл, Р.; Текцентрруп, А. (2011). «Многоуровневые методы Монте-Карло и приложения к эллиптическим уравнениям частного уравнения со случайными коэффициентами» (PDF) . Вычисления и визуализация в науке . 14 (1): 3–15. дои : 10.1007/s00791-011-0160-x. S2CID  1687254.
5. Писарони, М.; Нобиле, ФБ; Лейланд, П. (2017). «Продолжение многоуровневого метода Монте-Карло для количественного определения неопределенности в аэродинамике сжимаемой невязкой жидкости» (PDF) . Компьютерные методы в прикладной механике и технике . 326 (С): 20–50. дои : 10.1016/j.cma.2017.07.030. S2CID  10379943. Архивировано из оригинала (PDF) 14 февраля 2018 г.
6. Хаджи-Али, Алабама; Нобиле, Ф.; Темпоне, Р. (2016). «Мультииндексный Монте-Карло: когда разреженность встречается с выборкой». Нумерическая математика . 132 (4): 767–806. arXiv : 1405.3757 . дои : 10.1007/s00211-015-0734-5. S2CID  253742676.
7. Джайлз, МБ; Уотерхаус, Б. (2009). «Многоуровневое моделирование пути квази-Монте-Карло» (PDF) . Расширенное финансовое моделирование, серия «Радон» по вычислительной и прикладной математике . Де Грюйтер: 165–181.
8. Робб, П.; Нуйенс, Д.; Вандевалле, С. (2017). «Многоиндексный алгоритм квазимонте-карло для задач логнормальной диффузии». Журнал SIAM по научным вычислениям . 39 (5): А1811–С392. arXiv : 1608.03157 . Бибкод : 2017SJSC...39S.851R. дои : 10.1137/16M1082561. S2CID  42818387.