Todos os métodos de simulação são alguma forma de Monte Carlo?

35

Existe um método de simulação que não seja Monte Carlo? Todos os métodos de simulação envolvem a substituição de números aleatórios na função para encontrar um intervalo de valores para a função. Então, todos os métodos de simulação são essencialmente os métodos de Monte Carlo?

Vencedor
fonte
2
Eu acho que "Stan" era apenas o primeiro nome de Ulam, não o sobrenome de mais ninguém.
Nick Cox
Stan é a abreviação de Stanislas , de fato. Por isso, Andrew Gelman escolheu o STAN para sua nova linguagem de simulação.
Xian
Dado um pequeno problema combinatório, talvez limítrofe-trivial, uma pesquisa exaustiva ainda seria "Monte Carlo"?
Nick T
3
O que me lembro da minha palestra sobre algoritmos aleatórios é que os métodos de Monte Carlo têm resultados estocásticos com tempos de execução conhecidos, em contraste com os métodos de Las Vegas que têm tempos de execução estocásticos, mas resultados corretos. Nenhuma referência a isso, exceto um script manuscrito de cinco anos de idade na minha gaveta. Edit: As páginas da Wikipedia sobre Monte Carlo e Las Vegas parecem concordar com isso.
bayerj
Uma pesquisa exaustiva provavelmente seria um cálculo de força bruta. Os métodos de Monte Carlo são extraídos de um espaço de amostra. Essa amostra geralmente é um pequeno subconjunto do universo de resultados, o que torna a análise estatística tratável.
Alex Reynolds

Respostas:

41

Existem simulações que não são Monte Carlo. Basicamente, todos os métodos de Monte Carlo usam a lei (fraca) de grandes números: a média converge para sua expectativa.

Depois, existem métodos Quasi Monte Carlo. Estes são simulados com um compromisso de números aleatórios e grades igualmente espaçadas para gerar convergência mais rápida.

Simulações que não são Monte Carlo são, por exemplo, usadas em dinâmica de fluidos computacional. É fácil modelar a dinâmica de fluidos em uma "microescala" de porções únicas do fluido. Essas porções têm velocidade, pressão e tamanho iniciais e são afetadas por forças das porções vizinhas ou por corpos sólidos. As simulações calculam todo o comportamento do fluido calculando todas as porções e sua interação. Fazer isso com eficiência faz disso uma ciência. Nenhum número aleatório é necessário lá.

Na meteorologia ou na pesquisa climática, as coisas são feitas da mesma forma. Mas agora, os valores iniciais não são exatamente conhecidos: você só possui os dados meteorológicos em alguns pontos em que foram medidos. Muitos dados precisam ser adivinhados.

Como esses problemas complicados geralmente não são contínuos nos dados de entrada, você executa as simulações com diferentes suposições. O resultado final será escolhido entre os resultados mais frequentes. É assim que algumas previsões meteorológicas são simuladas em princípio.

Horst Grünbusch
fonte
5
Uma pequena correção: as simulações de Monte Carlo podem usar cálculos não aleatórios. É válido chamar uma simulação de "monte-carlo" se variar as condições iniciais e depois aplicar cálculos não aleatórios a partir daí. Muitas situações de CFD exigem monte-carlo porque as condições de contorno são definidas estatisticamente.
Cort Ammon
14

O método de Monte Carlo foi a primeira abordagem a usar simulação em computador para problemas estatísticos. Foi desenvolvido pela equipe de John von Neumann, Stanisław Ulam e Nicholas Metropolis dos laboratórios de Los Alamos que estavam trabalhando no projeto de Manhattan durante a Segunda Guerra Mundial. Foi descrito pela primeira vez em 1949 pela Metropolis & Ulam , e foi a primeira vez que o nome apareceu impresso. Isso foi possível porque os cientistas que descobriram também conseguiram usar um dos primeiros computadores em que estavam trabalhando. Em seu trabalho, eles usaram métodos de Monte Carlo para simulação de problemas físicos, e a idéia era que você poderia simular um problema complicado com a amostragem de vários exemplos desse processo. Existem vários artigos interessantes sobre a história de Monte Carlo, por exemplo:Metropolis ele mesmo ou alguns mais recentes, por exemplo, por Robert & Casella .

Portanto, "Monte Carlo" era o nome do primeiro método descrito com o objetivo de simulação por computador para resolver problemas estatísticos. Então, o nome se tornou um nome geral para toda uma família de métodos de simulação e é comumente usado dessa maneira.

Existem métodos de simulação considerados não Monte Carlo , no entanto, enquanto Monte Carlo foi o primeiro uso de simulação por computador, é comum que "simulação por computador" e "Monte Carlo" sejam usados ​​de forma intercambiável.

Há uma definição diferente do que é "simulação", isto é,

Dicionário Merriam-Webster :

3 a: a representação imitativa do funcionamento de um sistema ou processo por meio do funcionamento de outro b: exame de um problema geralmente não sujeito a experimentação direta por meio de um dispositivo de simulação

Dicionário Cambridge :

fazer ou criar algo que se comporte ou pareça algo real, mas que não seja real

Wikipedia :

imitação da operação de um processo ou sistema do mundo real ao longo do tempo

O que a simulação precisa para funcionar é a capacidade de imitar algum sistema ou processo. Isso não precisa de nenhuma aleatoriedade envolvida (como em Monte Carlo); no entanto, se todas as possibilidades forem tentadas, o procedimento será uma busca exaustiva ou um problema geralmente de otimização . Se o elemento aleatório estiver envolvido e um computador for usado para executar uma simulação de algum modelo, essa simulação será semelhante ao espírito do método inicial de Monte Carlo (por exemplo, Metropolis & Ulam, 1949). O elemento aleatório como parte crucial da simulação é mencionado, por exemplo, por Ross (2006, Simulation. Elsevier). No entanto, a resposta à pergunta depende muito da definição de simulação que você assume. Por exemplo, se você assumir que algoritmos determinísticos que usam otimização ou pesquisa exaustiva são de fato simulações, precisamos considerar uma grande variedade de algoritmos como simulações e isso torna a definição de simulação per se muito embaçada.

Literalmente, todo procedimento estatístico emprega algum modelo ou aproximação da realidade, que é "experimentada" e avaliada. Isso é consistente com as definições de simulação de dicionário. No entanto, não consideramos todas as estatísticas baseadas em simulação. A questão e a discussão parecem emergir da falta da definição precisa de "simulação". Monte Carlo parece ser um exemplo arquetípico (e primeiro) de simulação; no entanto, se considerarmos uma definição muito geral de simulação, muitos métodos não-Monte Carlo se enquadram nessa definição. Portanto, existem simulações que não são de Monte Carlo, mas todos os métodos claramente baseados em simulação se assemelham ao espírito de Monte Carlo, se relacionam com ele de alguma forma ou foram inspirados por ele. Essa é a razão pela qual "Monte Carlo" é frequentemente usado como sinônimo de "simulação".

Tim
fonte
3
Eu acho que "Stan" era apenas o primeiro nome de Ulam, não o sobrenome de mais ninguém.
Nick Cox
11
Stan é a abreviação de Stanislas , de fato. Por isso, Andrew Gelman escolheu o STAN para sua nova linguagem de simulação.
Xian
Dado um pequeno problema combinatório, talvez limítrofe-trivial, uma pesquisa exaustiva ainda seria "Monte Carlo"?
Nick T
6
Não entendi: como isso responde à pergunta?
o0 '.
11
@ Xi'an é Stanisław escrito com "Ł" (lido como "woo" em inglês).
Tim
13

Todos os métodos de simulação envolvem a substituição de números aleatórios na função para encontrar um intervalo de valores para a função.

Eu nunca ouvi falar dessa definição de simulação. Por exemplo, os artigos da Wikipedia sobre simulação e simulação em computador mencionam termos como aleatório e estocástico apenas brevemente.

Um exemplo simples de uma simulação que não envolve aleatoriedade e, portanto, claramente não é uma simulação de Monte Carlo, seria o seguinte:

Quero simular o comportamento de um pêndulo simples e fazer algumas suposições simplificadoras (cordão sem massa, massa pontual, sem atrito, sem forças externas como a força de Coriolis). Então obtenho um pêndulo matemático e posso escrever equações diferenciais que descrevem seu movimento. Posso então usar algum solucionador para equações diferenciais como um método de Runge-Kutta para simular sua trajetória para determinadas condições iniciais. (Também posso teoricamente argumentar que não preciso considerar outras condições iniciais.)

Dessa maneira, obtenho uma simulação bastante boa de um pêndulo real sem nunca usar um número aleatório. Portanto, essa não é uma simulação de Monte – Carlo.

Em outro exemplo, considere o mapa logístico , que é um modelo de população simples, sem qualquer aleatoriedade.

Wrzlprmft
fonte
7

Não. A simulação de uma partícula sob uma força pode ser feita usando Runge-Kutta ou outro algoritmo determinístico, que não é Monte Carlo.

Monte Carlo é usado para calcular integrais (você pode chamá-lo de simulação, mas no final calcula apenas uma aproximação numérica de um estimador). Novamente, você pode usar um método determinístico para fazer isso (por exemplo, regra trapezoidal).

Em termos gerais, é possível separar algoritmos para calcular integrais em determinístico e não determinístico. Monte Carlo é um método não determinístico. Quasi-Monte Carlo é outro. A regra trapezoidal é um algoritmo determinístico.

Jorge Leitao
fonte
4

Deixe-me dar uma facada em uma explicação simplificada. Um modelo "what-if" é uma simulação (determinística). Digamos que você tenha um sistema complexo, como uma planta de processamento de widgets. Você deseja estimar alguns parâmetros de desempenho, por exemplo, custo. Você constrói um modelo matemático da planta e, em seguida, seleciona várias suposições para fatores específicos no modelo, como a rapidez com que os widgets se movem por diferentes operações, ou quais porcentagens fluem em várias direções ou quantos widgets você processará. O modelo é uma simulação da planta e cada conjunto de premissas fornece uma estimativa desse parâmetro de desempenho.

Agora introduza incerteza. Você não sabe qual será a demanda por widgets no próximo mês, mas precisa estimar o custo. Portanto, em vez de dizer que a demanda terá 1.000 widgets, você estima uma distribuição de probabilidade para a demanda. Em seguida, você faz uma amostragem aleatória dos valores de demanda dessa distribuição e os utiliza para sua suposição. Enquanto você está nisso, também pode usar distribuições de probabilidade para outras suposições. Você usa o modelo repetidamente, inserindo suposições amostradas das várias distribuições de probabilidade. O resultado será uma distribuição de estimativas de custo. Esse é o aspecto de Monte Carlo.

Monte Carlo é um "recurso" ou "mecanismo" que é colocado em camadas sobre um modelo de simulação. Em vez de simular com um único conjunto de premissas para uma única estimativa, ele realiza uma coleção de simulações usando premissas selecionadas aleatoriamente.

fixer1234
fonte
2

Na teoria dos jogos, especialmente, abordagens que usam aleatoriedade nas simulações são chamadas técnicas de monte carlo. É normalmente usado como parte do Monte Carlo Tree Search (MCTS) em programas modernos.

(A pergunta original não fez uma distinção entre " algoritmo de monte carlo " e " método de monte carlo ", o que pode explicar discordâncias sobre algumas das respostas aqui.)

Por exemplo, no jogo de go (e todos os outros jogos que eu conheço que usam o MCTS), as simulações são chamadas de playouts. Os playouts aleatórios usam o conjunto de regras mais simples. Playouts leves são sinônimo de playouts aleatórios ou filtram alguns movimentos ruins facilmente detectados. Playouts pesados ​​usam mais heurísticas para filtrar muito mais movimentos. (Pela maneira como o playout sempre termina no final do jogo, cada playout leva aproximadamente a mesma quantidade de tempo.) Mas todos são referidos como simulações de "monte carlo".

Darren Cook
fonte