Монте Карло метода

Не поистовећивати са Монте Карло алгоритам.

Монте Карло методе (или Монте Карло експерименти) чини група рачунарских алгоритама који се ослањају на понављање случајних покушаја да би се добили нумерички резултати. Често се користе у решавању физичких и математичких проблемима и веома су корисни у случајевима када је немогуће користити друге математичке методе. Ове методе се најчешће користе у три класе случаја: оптимизацији, нумеричкој интеграцији и генерисању узорака код расподеле вероватноће.

У физичким проблемима, Монте Карло методе су веома корисне код симулације система са више степена слободе, као што су флуиди, јако везани раствори и ћелијске структуре (види ћелијски Потсов модел, интерактивне честичне системе, МекКин—Власове процесе, кинетичке моделе гасова). Остали примери укључују моделовање феномена са несигурним улазима попут висине ризика у бизнису или у математици, процене вичедимензионалних одрећених интеграла са сложеним граничним условима. У применама у свемирским и нафтним истраживањима, Монте—Карло базирана предвиђања неуспеха, прекорачења трошкова и неслагање са распоредом су много боља него људска интуиција или алтернативни „меки“ методи.  

У принципу, Монте Карло методе се могу користити за решавање многих проблема с пробабилистичком интерпретацијом. По закону великих бројева, интеграли описани очекиваном вредношћу неке рандомне променљиве се могу апроксимирати узимањем емпиријског просека (а.к.а. просека узорка) независних узорака променљиве. Када је расподела вероватноће променљиве веома сложена, математичари често користе генератор узорака Монте Карло Марковог ланца (MCMC). Главна идеја је стварање модела Марковог ланца са прописаним стационарним расподелама вероватноће. Та тај начин генерисани узорци у знатној мери ће одражавати жењену (циљну) дистрибуцију. По ергодичној теореми, стационарна раподела вероватноће је апроксимирана емпиријским мерама случајних стања MCMC семплера.   

Код осталих пролема заинтересовани смо са генерисање узорака из низова расподеле вероватноће који задовољавају нелинеарне еволуционе једначине. Ови токови расподеле вероватноће увек могу бити интерпретиране као расподеле случајних стања Марковог процеса чија промена расподеле вероватноће зависи од расподеле тренутних  случајних стања ( види МекКин-Власов процесе, нелинерне филтер једначине) . У осталим инстанцама  говоримо о току у расподели вероватноће са растућим нивоом сложености (модели простора са растућим временом, Болцман-Гибсове мере повезане са опадајућим температурним параметрима и многи други). Ови модели се могу такође посматрати као развој случајних стања нелинеарног ланца Маркова. Природни начин симулирања ових софистицираних процеса ланаца Маркова је узорковање великог броја копија процеса, заменом непознатих расподела  случајних стања у једначинама од стране емпиристичких мера. У супротности са традиционалним Монте Карло и ланцима Маркова методологијама ове технике честичног поља се ослањају на секвенцијалне интерагујуће узорке. Терминологија поља означава чињеницу да сваки од узорака (честице, индивидуе, шетачи, агенти, створења или фенотип) интерагује са емпиријским мерама процеса. Када величина система тежи бесконачности, ове случајне емпиријске мере конвергирају ка детерминистичкој расподели случајних стања ланаца Маркова, тако да се статистичка интеракција између честица губи.

Увод

Монте Карло метода примењена на апроксимацију вредности π. Након уцртавања 30000 произвољних тачака, процена π је у 0,07% од праве вредности. Ово се дешава са могућношћу процене од 20%

Монте Карло методе варирају, али теже да испрате одређени образац:

1. Дефинише се домен улаза 
2. Генерише се низ случајних улаза помоћу раподеле вероватноће 
3. Изврши се детерминистички прорачуни 
4. Изврши се сажимање резултата

На пример, узмимо у обзир круг уписан у квадрат. С обзиром на то да је однос ових површина π/4, вредност π се може апроксимирати употребом Монте Карло методе:

1. Нацртајмо квадрат на земљи, затим упишимо круг у њему 
2. Равномерно проспимо неке објекте једнаке величине (зрна песка или пиринча) преко квадрата
3. Преброји се број зрна у кругу и укупан број зрна однос два пребрајања је процена односа две површине тј. π/4. Помножи се резултат са 4, чиме се добија π.

У овој процедури домен улаза је квадрат који описујемо око круга. Генеришемо број улаза просипањем преко квадрата, затим извршимо прорачуне на сваки улаз (питамо се да ли је зрно пало у круг). Напокон, сажимамо резултате да би добили коначан резултат, апроксимацију π. Овде имамо две битне напомене: прво, ако зрна нису равномерно расподељена, онда је наша апроксимација непотпуна. Друго, мора да постоји велики број улаза. Апроксимација је генерално лоша само ако је пар зрна пало у цео квадрат. У просеку квалитет процене се повећава са већим бројем зрна у квадрату. Употреба Монте Карло методе захтева велику количину бројева, што је проузроковало формирање генератора псеудобројева чијом употребом је прорачунавање олакшано.

Историја

Пре него што је Монте Карло метода развијена, симулације су тестирале претходно дефинисане детерминистичке проблеме и статистичко узорковање је коришћено за процену неисигурности у симулацији. Монте Карло симулације су окренуле овај приступ, решавајући детерминистичке проблеме употребом вероватноће.

Рана верзија Монте Карло метода се могла видети у Буфоновом експерименту игле, у ком је π апроксимирано бацањем игала на под који је направљен од паралелних трака једнаког растојања. У 30-им годинама 20. века, Енрико Ферми је први експериментисао са Монте Карло методом проучавајућу неутронску дифузију, али није објавио тај рад.

Модерна верзија ланаца Маркова Монте Карло метода је измишљена крајем 1940-их од стране Станислава Улама, док је радио на пројектима нуклеарног наоружања у Националној лабораторији Лос Аламос. Након Уламовог продора, Џон фон Нојман је разумео његову важност па је програмирао ENIAC рачунар да врши Монте Карло прорачуне. Годие 1946. физичари и лабораторији Лос Аламос су проучавали заштиту од радијације и дистанцу коју неутрон пређе при проласку кроз различите материјале. И поред познавања већине података, попут просечне дистанце коју неутрон пређе у материји пре судара са атомским језгром или колико енергије неутрон ослобађа при судару, физичари Лос Аламоса нису могли да реше проблем користећи конвенционалне детерминистичке методе. Станислав Улам је имао идеју која се базирала на вероватноћи, он то овако описује:

Прве мисли и покушаји да развијем овај метод су настале из питања које ми је пало на памет 1946. док сам се опорављао од болести и играо солитер. Питање је било: које су шансе да се Кенфилд солитер добије са 52 карте? Након што сам провео доста времена покушавајући да израчунам помоћу обичног математичког рачуна, питао сам се да ли би практичнији начин од оног "апстрактног" био да извршим 1000 покушаја и избројим успешне покушаје. Ово је већ било могуће урадити са почетком нове ере брзих рачунара и моментално сам почео да разматрам питање неутронске дифузије и многа друга питања математичке физике, и генерално како да проблеме дефинисане помоћу сигурних диференцијалних једначина интерпретирам помоћу сукцесије случајних операција. Касније (1946) описао сам ову идеју Џону фон Нојман и почели смо да радимо на прорачунима.

Тајни рад Нојмана и Улама је захтевао тајно шифровано име. Њихов колега, Николас Метрополис, је предложио да то буде Монте Карло, по познатом Монте Карло казину у Монаку где је Уламов стриц позајмљивао новац од рођака за коцку. Употреба листе "случајних" бројева је била изузетно спора па је Нојман развио начин да израчуна псеудо бројеве, употребом методе средњег квадрата. Иако је ова метода критикована као сирова, Нојман је то оправдавао њеном брзином у тој позицији, и такође приметио да ова метода прави очигледне грешке за разлику од неких чије су грешке тешко приметне.

Монте Карло методе су биле основне методе у раду компјутерских симулација Менхетн пројекта, иако ограничени од стране рачунарских алата у то време. У 50-им годинама 20. века коришћени су у лабораторији Лос Аламос при развоју хидрогенске бомбе и постале су популарне у физици, физичкој хемији и операционим истраживањима. Корпорација Ранд и Америчко ратно ваздухопловство су биле главне организације одоговорне за финансирање и пропаганду Монте Карло метода током тог времена и почеле су да налазе примену у многим областима.

Теорија поља честичног типа Монте Карло методе је почела да се развија крајем 60-их година радом Хенрија П. МекКина Јуниора на Марковим интерпретацијама класа нелинеарних параболичних парцијалних диференцијалних једначина произашлих из механике флуида. Такође ћемо навести пионирски чланак Теодора Хариса и Хермана Кана, објављеног 1951., о коришћењу поља генетичког типа Монте Карло метода за процену преноса енергије честица. Поље генетичког типа Монте Карло методологија је такође коришћено у еволуционом рачунарству код алгоритама природне хеуристичке претраге (Метахеуристичке). Основе ових техника се могу наћи још у 50-им годинама у раду Алана Тјуринга на генетском типу машина за мутациону-селекцију и чланци Нилса Аала Баричелија са Института за напредне студије на Принстону, у Њу Џерзију.

Квантни Монте Карло, и посебно Дифузиони Монте Карло методи се такође могу интерпетирати као поље честичних Монте Карло метода у апроксимацији Фејнман-Кацових интеграла. Почеци ових метода се приписују Енрику Фермију и Роберту Ричмајеру који су развили 1948 честичну интерпретацију неутронске-ланчане реакције, али први хеуристички алгоритми и генетски честични алгоритми за процену стања енергије квантних система (у редукованој матрици) су дело Џека Х. Хетерингтона 1948. године. У молекуларној хемији, употреба генетских хеурситичких честичних методологија се може следити све до 1955. и рада МАршала Н. Розенблута и Аријане В. Розенблут.

Употреба секвенцијалног Монте Карла у напредној обради сигнала и Бајесовој интерференцији је све већа. Године 1993, Гордон и остали су објавили свој први рад са првом применом овог метода у Бајесовој статистичкој интерференцији. Аутори су назвали свој алгоритам „бутстреп филтер“ и показали да у поређењу са другим филтерима, њихов алгоритам не захтева никакву процену о стању-простору или буци система. Такође ћемо цитирати још један пионирски чланак у овој области аутора Геншира Китагаве о поменутим „Монте Карло филтерима“, и оне Пјера дел Морала и Химилкона Карваља, Пјера дел Морала, Андреа Монина и Џерарда Салута о честичним филтерима објављеним средином 90-их. Честични филтери су такође развијени у обради сигнала у периоду 1989-1992 од стране П. дел Морала, Џ. С. Нојера, Г. Ригала и Џ. Салута у ЛААС-ЦНРС у серији тајних пројеката СТЦАН, ИТ компаније ДИГИЛОГ, и ЛААС-ЦНРС (ЛАбораторија за анализу и архитектуру система) о проблемима процесије РАДАР/СОНАР и ГПС сигнала. Ове секвенцијалне Монте Карло методологије могу се интерпретирати као семплери прихватања-одбијања са интерактивним обновљивим системом.

Од 1950. до 1996. године, све публикације на тему секвенцијалне Монте Карло методологије, укључујући и прераде и модификације Монте Карло методе уведене у рачунарској физици и молекуларнокј хемији, су предтавиле природни и хеуристичке алгоритми који се примењују у различитим ситуацијама без иједног доказа о њиховој доследности, нити расправа о пристрасности процена генеалошких и предачких стабала на бази алгоритама. Математичке основе и прву ригорозну анализу ових честица алгоритама су дело Пјера дел Мораа из 1996. Честичне методологије са гранањем са различитим величинама популације су такође развијене крајем 1990. од стране Дена Крисана, Џесике Гејнс и Терија Лајонса и Ден Крисана, Пјера дел Морала и Терија Лајона. Даљи развој у овој области су извршени 2000. од стране П. дел Морала, А. Гуионета и Л. Мицла .

Дефиниција

Не постоји консензус о томе како треба да буду дефинисани Монте Карло методи. На пример, Рипли дефинише моделирање највише вероватноће као стохастичку симулацију, док је Монте Карло резервисан за Монте Карло интеграције и Монте Карло статистичке тестове. Савиловски разликује симулације, методе Монте-Карло, и Монте Карло симулације: симулација је измишљена представа стварности, метод Монте Карло је техника која се може користити за решавање математичког или статистичког проблем, а Монте Карло симулација користи поновио узорковање за утврђивање својства неке појаве (или понашања). Примери:

• Симулација: Генерисање једне псеудо-случајне јединствене променљиве из интервала [0,1] коришћеног за симулацију бацања новчића: Ако је вредност мања или једнака 0,50 одреди исход као главу, али ако је вредност већа од 0,50 одредити исход као писмо. Ово је симулација, али не и Монте Карло симулација
• Монте Карло метода: проспимо кутију кованица на сто, а затим израчунавање односа кованица са главом у односу на писма је Монте Карло метод за одређивања понашања поновљених бацања новчића, али није симулација.
• Монте Карло симулација: Цртање великог броја псеудо-случајних јединствених варијабли из интервала [0,1], и додељивање вредности мањих или једнаких 0,50 као главе и већи од 0,50 као писма, је Монте Карло симулација понашања у више наврата бацања новчића.

Калос и Витлок истичу да такве разлике нису увек лаке за одржавање. На пример, емисија зрачења код атома је природан стохастички процес. Може се симулирати директно или њено просечно понашање може бити описано стохастичим једначинама које се саме решавају коришћењем Монте Карло метода. "Заиста, исти рачунарски код може се истовремено посматрати као „природна симулација“ или као решењње једначина путем природног узорковања."

Монте Карло и случајни бројеви

Монте Карло симулације методе не захтевају увек истински случајне бројеве да би била корисне -док за неке примене, као што је тестирање узорака, непредвидивост је од виталног значаја. Многе од најкориснијих техника користе детерминистичке, псеудослучајне секвенце, што олакшава тестирање и поновне симулације. Једини квалитет обично потребан да се направи добре симулације је да се у псеудо-случајном редоследу појави "довољно случајни" у одређеном смислу. Шта то значи зависи од апликације, али обично треба да прође низ статистичких тестова. Тестирања да су бројеви равномерно распоређени или прате другу жељену раподелу када је довољан велики број елемената у низу се сматрају једним од најједноставнијих и најчешћих. Слабе корелације између узастопних узорака је често пожељно / неопходно

Савиловски наводи карактеристике квалитетне Монте Карло симулације:

• је (псеудо-случајни) генератор бројева има одређене карактеристике (нпр дуг "рок" пред понављања секвенце)
• је (псеудо-случајни) генератор бројева који производи вредности које пролазе тестове случајности
• има довољно узорака како би се осигурали тачни резултати
• користи се правилна техника узорковања
• алгоритам се користи за оно за шта је моделиран
• симулира феномен у питању.

Алгоритми узорковања псеудо-случајних бројева се користе за трансформацију равномерно распоређених псеудо-случајних бројева у бројеве који се дистрибуирају према датој расподели вероватноће. Секвенце мале несразмерности се често користе уместо случајног узорка јер имају бољу покривеност и обично имају бржи ред конвергенције од Монте Карло симулације помоћу случајних или псеудослучајних секвенци. Методе засноване на њиховој употреби се називају квази-Монте Карло методе.

Монте Карло методе против „шта ако“ сценарија

Постоје начини коришћења вероватноће које дефинитивно нису Монте Карло симулације - на пример, детерминистичко моделирање користи процене једне тачке. Свакој неизвесној променљивој у оквиру модела је додељена процена "најбоље претпоставке" . Сценарији (као што су најбољи, најгори, или највероватнији случај) за сваку улазну променљиву се бирају и резултати чувају. Насупрот томе, узорак Монте Карло симулација из расподеле вероватноће за сваку променљиву произведе стотине или хиљаде могућих исхода. Резултати су анализирани да би се увидело да се јављају вероватноће различитих исхода. На пример, поређење модела изградње табела трошкова користећи традиционални „шта ако“ сценаријо, а затим покретање поређења Монте Карло симулацијом, троугаона дистрибуција вероватноће показује да Монте Карло анализа има ужи опсег него "шта ако" анализа. Нпр. „шта ако“ анализа даје једнаку тежину свим сценаријима (види квантификативна несигурност у корпоративним финансијама), док је методом Монте Карло дају узорци у веома ниској вероватноћи региона. Узорци у таквим областима називају се „ретки догађаји“.

Примена

Монте Карло методе су посебно корисне за симулацију феномена са неизвесношћу улаза и системима са великим бројем спрегнутих степена слободе. Области примене укључују:

Физичке науке

Види још: Монте Карло методе у статистичкој физици

Монте Карло методе су веома важне у рачунарској физици, физичкој хемији и сродним примењеним областима, и имају различите примене у комплексним квантним хромодинамичким прорачунима у дизајнирању топлотних штитова и аеродинамичких облика као и у моделирању транспорта зрачења у дозиметријским прорачунима. У статистичкој физици Монте Карло молекуларно моделирање је алтернатива молекуларне рачунарске динамике, такође се користе за израчунавања у области статистичких теорија једноставних честица и полимерних система. Квантне Монте Карло методе решавају проблем многих тела за квантне системе. У експерименталној физици честица, Монте Карло методе се користе за израду детектора, разумевања њиховог понашања и поређења експерименталних података у теорији. У астрофизици, они се користе у различитим начинима моделирања еволуције галаксија и микроталасном преносу зрачења кроз тешке планетарне површине. Монте Карло методе се користе у ансамблу модела који чине основу савремене нумеричкевременске прогнозе.

Инжењерство

Монте Карло методе су у широкој употреби у инжењерству у анализи осетљивости и квантитативним анализама вероватноће у процесу пројектовања. Потреба произилази из интерактивног, ко-линеарног и нелинеарног понашања симулација типичних процеса. На пример,

• У микроелектроници, Монте Карло методе се примењују за анализу у корелацији у аналогним и дигиталним интегрисаним колима.
• У геостатици и геометалургији, Монте Карло методе подупиру ток процеса дизајна минералне обраде, и доприносе анализи квантитативног ризика.
• У анализи приноса енергије ветра, предвиђању излазне енергије ветропарка који током свог века даје различите нивое неизвесности (П90, П50, итд)
• симулирању утицаја загађења нафтом у поређењу са бензином.
• У динамици флуида, посебно у динамици гасова, где се Болцманова једначина решава за коначан Кнудсеновог броја протока течности користећи директну Монте Карло симулацију у комбинацији са високо ефикасним рачунарским алгоритмима.
• У аутономној роботици, Монте Карло локализација може одредити позицију робота. Често се примењује на стохастичким филтерима као што је Калман филтер или филтер честица које формира срце СЛАМ (Симултана локализација и мапирање) алгоритма.
• У области телекомуникација, када се планира бежична мрежа, дизајн мора бити доказано да раде за широк спектар сценарија који зависе углавном од броја корисника, њихових локација и услуга које они желе да користе. Монте Карло методе се обично користе за генерисање ових кориснике и њихове стања. Представа мрежа се затим оцењује и, ако резултати нису задовољавајући, дизајн мрежа пролази кроз процес оптимизације.
• У инжењерингу поузданости, може се користити Монте Карло симулација за генерисање међувремена између кварова и међувремена за поправку компоненти.
• У обради сигнала и Бајесовим закључцима, честични филтери и секвенцијалне Монте Карло технике су класа средњих метода поља честица за узимање узорака и израчунавање дистрибуција процеса сигнала имајући у виду нека бучна и парцијална запажања употребом интерактивних емпиријских мера.

Рачунарска биологија

Монте Карло методе се користе у разним областима рачунарске биологије, на пример код Бајесових закључка у филогени, или за проучавање биолошких система као што су геноми, протеини, или мембране. Ови системи се могу проучавати у грубим or ab initiio оквирима у зависности од жељене прецизности. Компјутерске симулације нам омогућавају да пратимо локалну средину одређеног молекула и видимо да ли се нека хемијска реакција дешава, на пример. У случајевима где није изводљиво да се спроведе физички експеримент, мисаони експерименти се могу спроводити (на пример: разбијање веза, увођење нечистоће на одређеним местима, мењање локалних / глобалних структура, односно увођење спољних поља).

Рачунарска графика

Праћење пута, повремено називано Монте Карло праћење стазе, чини 3Д приказ случајног праћењу узорака могућих светлсоних стаза. Поновљено узорковање сваког пиксела на крају ће довести до тога да просечни узорци конвергирају ка исправном решењу једначине рендеровања, што га чини једним од најзначајнијих физички тачних метода за приказивање 3Д графике у реалности.

Примењена статистика

У примењеној статистици, Монте Карло методе се генерално користе у две сврхе:

1. За поређење конкурентских статистика на малим узорцима под реалним условима података. Иако Тип 1 грешака и снага својства статистичких података се може израчунати за податке извучене из класичних теоријских расподела (нпр нормална крива, Кошијеве дистрибуције) за асимптотске услове (нпр. бесконачне величине узорка и бесконачно мали ефекат третмана), реални подаци често немају такве расподеле.
2. Да обезбеди имплементације хипотеза тестова који су ефикаснији од егзактних тестова, као што су пермутација тестова (које је често немогуће израчунати) док је прецизнији од критичних вредности за асимптотске расподеле.

Монте Карло методе су такође компромис између приближне случајности и тестова пермутација.Тестови приближне случајности се заснивају на одређеном подскупу свих пермутација (који подразумева потенцијално огроман уређивање од којих су пермутације сматра). Монте Карло приступ се заснива на одређеном броју насумично извучених пермутација (размену мањих губитака у прецизности ако се пермутација два пута извршава - или чешће-за ефикасност не морају да прате које су већ изабране пермутација).

Вештачка интелигенција код игрица

Главни чланак: Монте Карло претрага стабала

Монте Карло методе су развијене у техници под називом метод Монте-Карло претрага стабала који је користан за тражење најбољег потеза у игри. Могући потези су организовани у претрагу стабла и велики број случајних симулација се користи за процену дугорочног потенцијала сваког потеза. Симулатор црне кутије представља противникове потезе. Монте Карло претрага стабала (МЦТС) има четири корака:

1. Почевши од корена стабла, изаберите оптималне наследнике чворова док се не нађе лист чвор.
2. Проширите лист чвор и одаберите једно од његове деце.
3. Започните симулирану игру почевши од тог чвора
4. Користите резултате симулиране игре за ажурирање чвора и његових предака.

Нето ефекат, током многих симулација игре, је да вредност чвора који представља потез ће ићи горе или доле, при чему ће чвор представити добар или лош потез Монте Карло претрага стабла се успешно користи за играње игара као што су Го. Тантрикс, Оклопњача, Хавана, и Аримаа

Види још: Computer Go

Дизајн и визуелизација

Монте Карло методе су ефикасне у решавању спрегнутих интегралних диференцијалних једначина поља зрачења и преноса енергије, и на тај начин ове методе су коришћени у прорачунима Глобалног осветљења које производе фото-реалистичне слике виртуелних 3Д модела, са применама у видео играма, архитектури, дизајну, компјутерски генерисаним Филмовима, и филмским специјалним ефектима.

Финансије и бизнис

Види још: Монте Карло методе у финансијама, Квази Монте Карло методе у финансијама, Монте Карло методе у формирању цена, Стоџастичко моделовање (осигурање) и Стохастички модел улагања

Монте Карло методе у финансијама се често користе за процену улагања у пројекте на пословном или корпоративном нивоу, или при процени финансијских производа. Могу се користити за моделовање распореда пројеката, где симулације сажима процене у најгорем случају, најбољем случају, као и исхода пројеката. Монте Карло методе користе се и код одређивања цена, анализе подразумеваних ризика .

Примена у математици

У принципу, Монте Карло методе се користе у математици за решавање разних проблема кроз стварање одговарајућих случајних бројева (види Генерисање случајних бројева) и посматрање оних фракцију бројева који покорава неку имовину или имовине. Поступак је користан за добијање нумеричких решења за проблеме превише компликоване за аналитичко решавање. Најчешћи примена методе Монте Карло је Монте Карло интеграција.

Интеграција

Главни чланак: Интеграција Монте Карло

Монте Карло интеграција ради по принципу поређења произвоиљнх тачака са вредношћу функције

Грешке редуковане фактором $\scriptstyle 1/{\sqrt {N}}$

Алгоритми детерминистичке нумеричке интеграције раде добро у малом броју димензија, али наилазе на два проблема када функције имају много променљивих. Прво, број потребних процена функције рапидно се повећава са бројем димензија. На пример, ако 10 евалуација пруже адекватну тачност у једној димензији, за 100 димензија потребно је 10¹⁰⁰ евалуације-исувише прорачуна. Ово се зове проклетство димензионалности. Друго, граница мултидимензионалног региона може бити врло компликована, тако да не би било могуће да се проблем смањи на итеративни интеграл. 100 димензија никако није необично, јер у многим физичким проблемима, "димензија" је еквивалент степена слободе.

Монте Карло методе пружају излаз из овог експоненцијалног повећања рачунања времена. Докле год је функција са регулисаним начином понашања, може се проценити насумично одабиром процена у 100-димензионалном простору, и узимајући неку врсту просека вредности функције у тим местима. До централне граничне теореме, овај метод приказује $\scriptstyle 1/{\sqrt {N}}$ конвергенције-нпр учетворостручавањем броја узоркованих процена преполовљава се грешка, без обзира на број димензија.

Префињеност овог метода, позната као значај узорковања у статистици, подразумева узорковање процена случајно, али чешће где је интегранта велика. Да бисте то урадили управо један би морао да има ве познати интеграл, али може се приближно апроксимирати интегралу сличне функције или користити адаптивне рутине као што су 'стратификовано узорковање, рекурзивно слојевито узорковање, прилагодљиво кишобран узорковања или ВЕГАС алгоритам.

Сличан приступ, квази-Монте Карло метода, користи ниске неслагања секвенци. Ове секвенце боље "попуњавају" област и узоркују најважније тачке, па квази-Монте-Карло методи брже конвергирају.

Друга класа метода за узимање узорака у запремини је да се симулира случајни пролаз кроз њега (уметање). Такве методе укључују Метрополис-Хастингс алгоритам, Гибсово узорковање, Ванг и Ландау алгоритам и сарадње MCMC методологије, као што су секвенцијални Монте Карло семплери.

Симулација и оптимизација

Главни чланак: Стохастичка оптимизација

Још једна снажна и врло популарна примена за случајне бројеве у нумеричким симулацијама је код нумеричких оптимизација. Проблем је да се минимизирају (или повећају) функције неког вектора који често има велики број димензија. Многи проблеми могу бити формулисана на овај начин: на пример, рачунарски шаховски програм се може посматрати како покушава да пронађе скуп, рецимо, 10 потеза који даје најбоље функције евалуације на крају. Код проблема трговачких путника циљ је да се минимизира удаљеност. Постоји примена у инжењерском дизајну, као што је дизајн мултидисциплинарне оптимизације. Она је примењена са квази-једнодимензионалним моделима за решавање динамичких проблема честица ефикасним истраживањем велике конфигурације простора.

Проблем трговачког путника је оно што се зове конвенционални проблем оптимизације. Циљ је одредити растојања између сваког одредишта потребног за утврђивање оптималног пута најмањом укупном међусобном удаљеношћу. Међутим претпоставимо да уместо најмање укуоне удаљености тражимо најкраће време за обилазак. Ово превазилази конвенционалне оптимизације, јер је путовање кроз време инхерентно неизвесно (саобраћајне гужве, доба дана, итд). Као резултат тога, за одређивање оптималне путање користимо симулацију - оптимизацију прво да би разумели низ потенцијалних времена потребних за кретање од једне до друге тачке (представљених расподелом вероватноће у овом случају пре него одређеном удаљеношћу) и онда оптимизовањем наше одлуке идентификујемо најбољи пут уз узимање фактора неизвесност у обзир.

Инверзни проблеми

Формулација вероватноће инверзног проблема доводи до дефиниције расподеле вероватноће у модела простора. Ова расподела комбинује претходне информације са новим информацијама добијеним мерењем неког видљивог параметара (подаци). Како, у општем случају, теорија која повезује податке са параметрима модела је нелинеарна, па се крајња вероватноћа у моделу простора не може лако описати (може бити мултимодална, неки тренуци се не могу дефинисати, итд).

Када се анализира инверзни проблем, добијање максималне веродостојности модела обично није довољна, као што обично и желите да имате информације о снази резолуције података. У општем случају имамо велики број параметара модела и претрага маргиналних густина вероватноће од интереса може бити непрактична, или чак бескорисна. Али, могуће је псеудонасумично генеришемо велику колекцију модела према задњој расподели вероватноће и да анализирамо и прикажемо моделе на такав начин да информације о релативним својставима модела преносе на гледаоца. Ово се може постићи помоћу ефикасног Монте Карло метода, чак и у случајевима када је доступна експлицитна формула за а приори расподелу .

Најпознатији значај метода узорковања, Метрополис алгоритам, може се генерализовати, и то даје метод који омогућава анализу (евентуално високо нелинеарних) инверзних проблема са сложеним а приори информацијама и податацима произвољне дистрибуције буке.

Управљање залихама нафте

Монте Карло методе су веома популарне у управљању резервоарима угљоводоника у контексту нелинеарних инверзних проблема. Ово укључује стварање рачунарских модела нафтних и гасних резервоара са доследношћу посматраних података о производњи. Са циљем доношења одлука и проценом неизвесности, Монте Карло методе се користе за генерисање више геолошких реализација.

У култури

• Монте Карло Метод је албум јужнокалифорнијског рок бенда "Ништа обојено у плаво" из 1998. године.

Види још

• Помоћно поље Монте Карло метода
• Био Монте Карло метода
• Поређење анализе ризика Мicrosoft Excel-ових адова
• Директна симулација Монте Карло методе
• Динамичка Монте Карло метода
• Кинетички Монте Карло
• Поље честица Монте Карло
• Филтер честица
• Листа софтвера за Монте Карло биомоделовање
• Монте Карло метод за транспорт фотона
• Монте Карло метод за транспорт електрона
• Морисова метода
• Генетски алгоритам
• Квази-Монте Карло метод
• Собол секвенце

Литература

• Kroese, D. P.; Taimre, T.; Botev, Z. I. (2011). Handbook of Monte Carlo Methods. John Wiley & Sons. 
• Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering. (PDF). Lecture Notes in Mathematics. 1729. стр. 1—145. doi:10.1007/bfb0103798. 
• Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. стр. 575. „Series: Probability and Applications” 
• Anderson, Herbert L. (1986). „Metropolis, Monte Carlo and the MANIAC” (PDF). Los Alamos Science. 14: 96—108. 
• Baeurle, Stephan A. (2009). „Multiscale modeling of polymer materials using field-theoretic methodologies: A survey about recent developments”. Journal of Mathematical Chemistry. 46 (2): 363—426. doi:10.1007/s10910-008-9467-3. 
• Berg, Bernd A. (2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code). Hackensack, NJ: World Scientific. ISBN 978-981-238-935-0. 
• Binder, Kurt (1995). The Monte Carlo Method in Condensed Matter Physics. New York: Springer. ISBN 978-0-387-54369-7. 
• Caflisch, R. E. (1998). Monte Carlo and quasi-Monte Carlo methods. Acta Numerica. 7. Cambridge University Press. стр. 1—49. 
• Davenport, J. H. „Primality testing revisited”. Proceeding ISSAC '92 Papers from the international symposium on Symbolic and algebraic computation: 123 129. ISBN 978-0-89791-489-5. doi:10.1145/143242.143290. 
• Doucet, Arnaud; Freitas, Nando de; Gordon, Neil (2001). Sequential Monte Carlo methods in practice. New York: Springer. ISBN 978-0-387-95146-1. 
• Eckhardt, Roger (1987). „Stan Ulam, John von Neumann, and the Monte Carlo method” (PDF). Los Alamos Science, Special Issue (15): 131—137. Архивирано из оригинала (PDF) 09. 09. 2014. г. Приступљено 15. 11. 2015. 
• Fishman, G. S. (1995). Monte Carlo: Concepts, Algorithms, and Applications. New York: Springer. ISBN 978-0-387-94527-9. 
• C. Forastero; L. Zamora and D. Guirado and A. Lallena (2010). „A Monte Carlo tool to simulate breast cancer screening programmes”. Phys. In Med. And Biol. 55 (17): 5213—5229. Bibcode:2010PMB....55.5213F. doi:10.1088/0031-9155/55/17/021. 
• Golden, Leslie M. (1979). „The Effect of Surface Roughness on the Transmission of Microwave Radiation Through a Planetary Surface”. Icarus. 38 (3): 451—455. Bibcode:1979Icar...38..451G. doi:10.1016/0019-1035(79)90199-4. 
• Gould, Harvey; Tobochnik, Jan (1988). An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems. Reading: Addison-Wesley. ISBN 978-0-201-16504-3. 
• Grinstead, Charles; Snell, J. Laurie (1997). Introduction to Probability. American Mathematical Society. стр. 10–11. 
• Hammersley, J. M.; Handscomb, D. C. (1975). Monte Carlo Methods. London: Methuen. ISBN 978-0-416-52340-9. 
• Hartmann, A.K. (2009). Practical Guide to Computer Simulations. World Scientific. ISBN 978-981-283-415-7. Архивирано из оригинала 11. 02. 2009. г. Приступљено 15. 11. 2015. 
• Hubbard, Douglas (2007). How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons. стр. 46. 
• Hubbard, Douglas (2009). The Failure of Risk Management: Why It's Broken and How to Fix It. John Wiley & Sons. 
• Kahneman, D.; Tversky, A. (1982). Judgement under Uncertainty: Heuristics and Biases. Cambridge University Press. 
• Kalos, Malvin H.; Whitlock, Paula A. (2008). Monte Carlo Methods. Wiley-VCH. ISBN 978-3-527-40760-6. 
• Kroese, D. P.; Taimre, T.; Botev, Z.I. (2011). Handbook of Monte Carlo Methods. New York: John Wiley & Sons. стр. 772. ISBN 978-0-470-17793-8. 
• MacGillivray, H. T.; Dodd, R. J. (1982). [10.1007/BF00648545 „Monte-Carlo simulations of galaxy systems”]. Astrophysics and Space Science. Springer Netherlands. 86 (2). 
• MacKeown, P. Kevin (1997). Stochastic Simulation in Physics. New York: Springer. ISBN 978-981-3083-26-4. 
• Metropolis, N. (1987). „The beginning of the Monte Carlo method” (PDF). Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125—130. 
• Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth, Marshall N.; Teller, Augusta H.; Teller, Edward (1953). „Equation of State Calculations by Fast Computing Machines”. Journal of Chemical Physics. 21 (6): 1087. Bibcode:1953JChPh..21.1087M. doi:10.1063/1.1699114. 
• Metropolis, N.; Ulam, S. (1949). „The Monte Carlo Method”. Journal of the American Statistical Association. American Statistical Association. 44 (247): 335—341. JSTOR 2280232. PMID 18139350. doi:10.2307/2280232. 
• M. Milik & J. Skolnick (1993). „Insertion of peptide chains into lipid membranes: an off-lattice Monte Carlo dynamics model”. Proteins. 15 (1): 10—25. PMID 8451235. doi:10.1002/prot.340150104. 
• Mosegaard, Klaus; Tarantola, Albert (1995). „Monte Carlo sampling of solutions to inverse problems”. J. Geophys. Res. 100 (B7): 12431—12447. Bibcode:1995JGR...10012431M. doi:10.1029/94JB03097. 
• P. Ojeda; M. Garcia and A. Londono and N.Y. Chen (2009). „Monte Carlo Simulations of Proteins in Cages: Influence of Confinement on the Stability of Intermediate States”. Biophys. Jour. Biophysical Society. 96 (3): 1076—1082. Bibcode:2009BpJ....96.1076O. doi:10.1529/biophysj.107.125369. 
• Int Panis L; De Nocker L; De Vlieger I; Torfs, R. (2001). „Trends and uncertainty in air pollution impacts and external costs of Belgian passenger car traffic International”. Journal of Vehicle Design. 27 (1–4): 183—194. doi:10.1504/IJVD.2001.001963. 
• Int Panis L, Rabl A, De Nocker L, Torfs R (2002). P. Sturm, ур. „Diesel or Petrol ? An environmental comparison hampered by uncertainty”. Mitteilungen Institut für Verbrennungskraftmaschinen und Thermodynamik. Technische Universität Graz Austria. Heft 81 Vol 1: 48—54. 
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1996) [1986]. Numerical Recipes in Fortran 77: The Art of Scientific Computing. Fortran Numerical Recipes. 1 (Second изд.). Cambridge University Press. ISBN 978-0-521-43064-7. 
• Ripley, B. D. (1987). Stochastic Simulation. Wiley & Sons. 
• Robert, C. P.; Casella, G. (2004). Monte Carlo Statistical Methods (2nd изд.). New York: Springer. ISBN 978-0-387-21239-5. 
• Rubinstein, R. Y.; Kroese, D. P. (2007). Simulation and the Monte Carlo Method (2nd изд.). New York: John Wiley & Sons. ISBN 978-0-470-17793-8. 
• Savvides, Savvakis C. (1994). „Risk Analysis in Investment Appraisal”. Project Appraisal Journal. 9 (1). doi:10.2139/ssrn.265905. 
• Sawilowsky, Shlomo S.; Fahoome, Gail C. (2003). Statistics via Monte Carlo Simulation with Fortran. Rochester Hills, MI: JMASM. ISBN 978-0-9740236-0-1. 
• Sawilowsky, Shlomo S. (2003). „You think you've got trivials?”. Journal of Modern Applied Statistical Methods. 2 (1): 218—225. 
• Silver, David; Veness, Joel (2010). „Monte-Carlo Planning in Large POMDPs” (PDF). Ур.: Lafferty, J.; Williams, C. K. I.; Shawe-Taylor, J.; Zemel, R. S.; Culotta, A. Advances in Neural Information Processing Systems 23. Neural Information Processing Systems Foundation. Архивирано из оригинала (PDF) 25. 05. 2012. г. Приступљено 15. 11. 2015. 
• Szirmay-Kalos, László (2008). Monte Carlo Methods in Global Illumination - Photo-realistic Rendering with Randomization. VDM Verlag Dr. Mueller e.K. ISBN 978-3-8364-7919-6. 
• Tarantola, Albert (2005). Inverse Problem Theory. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-572-9. 
• Vose, David (2008). Risk Analysis, A Quantitative Guide (Third изд.). John Wiley & Sons.