Método de Montecarlo

Os métodos de Montecarlo, ou experimentos de Montecarlo, son unha ampla clase de algoritmos computacionais que se basean nunha mostraxe aleatoria repetida para obter resultados numéricos. O concepto subxacente é utilizar a aleatoriedade para resolver problemas que poden ser deterministas en principio. O nome provén do Casino de Montecarlo debido a aleatoriedade dos da mostra.

Os métodos de Montecarlo adoitan implementarse mediante simulacións por ordenador, e poden proporcionar solucións aproximadas a problemas que doutro xeito son insolúbeis ou demasiado complexos para analizalos matematicamente.

Visión xeral

Os métodos de Montecarlo varían, pero tenden a seguir un patrón particular:

Definir un dominio de entradas posíbeis
Xera entradas aleatoriamente a partir dunha distribución de probabilidade sobre o dominio
Realiza un cálculo determinista das saídas
Agregar os resultados

Por exemplo, considere un cuadrante (sector circular) inscrito nun cadrado unitario. Dado que a razón das súas áreas é $π$ /4 ( $\pi r^{2}=\pi \cdot 1^{2}$ área do círculo, fronte a $(1+1)^{2}=4$ , área do cadrado dos catro cuadrantes), o valor de $π$ pódese aproximar usando un método de Montecarlo:^[1]

Debuxe un cadrado e inscriba un cuadrante dun círculo dentro del.
Obteña uniformemente un número determinado de puntos sobre o cadrado.
Conte o número de puntos dentro do cuadrante, é dicir, que teñen unha distancia da orixe inferior a 1
A relación entre a conta interior e a conta total da mostraxe é unha estimación da relación das dúas áreas, $π$ /4. Multiplique o resultado por 4 para estimar $π$ .

Hai dúas consideracións importantes:

Se os puntos non están distribuídos uniformemente, entón a aproximación será pobre.
A aproximación é xeralmente pobre se só uns poucos puntos se colocan aleatoriamente en todo o cadrado. De media, a aproximación mellora a medida que se van colocando máis puntos.

Para usar o método de Montecarlo requírese gran cantidade de números aleatorios, sendo moi positivo a utilización de xeradores de números pseudoaleatorios.

Definicións

Non hai consenso sobre como debe definirse o método de Montecarlo. Por exemplo, Ripley^[2] define a maioría dos modelos probabilísticos como simulación estocástica, reservando como propio de Montecarlo só a integración de Montecarlo e as probas estatísticas de Montecarlo. Sawilowsky ^[3] distingue entre unha simulación, un método de Montecarlo e unha simulación de Montecarlo: unha simulación é unha representación ficticia da realidade, un método de Montecarlo é unha técnica que se pode usar para resolver un problema matemático ou estatístico e unha simulación de Montecarlo utiliza mostraxes repetidas para obter as propiedades estatísticas dalgún fenómeno (ou comportamento).

Uso en matemáticas

En xeral, os métodos de Montecarlo úsanse en matemáticas para resolver varios problemas xerando números aleatorios axeitados (ver tamén Xeración de números aleatorios) e observando a fracción dos números que obedece a algunha propiedade ou propiedades. O método é útil para obter solucións numéricas a problemas demasiado complicados para resolver analiticamente. A aplicación máis común do método de Monte Carlo é a integración de Monte Carlo.

Integración

Artigo principal: Integración de Montecarlo.

Os algoritmos de integración numérica deterministas funcionan ben nun pequeno número de dimensións, mais atopan dous problemas cando as funcións teñen moitas variábeis. En primeiro lugar, o número de avaliacións de funcións necesarias aumenta rapidamente co número de dimensións. Por exemplo, se 10 avaliacións proporcionan a precisión adecuada nunha dimensión, entón son necesarios 10¹⁰⁰ puntos para 100 dimensións, demasiados para calculalos. Isto chámase a maldición da dimensionalidade. En segundo lugar, o límite dunha rexión multidimensional pode ser moi complicado, polo que pode non ser viábel reducir o problema a unha integral iterada^[4] . 100 dimensións non é nada infrecuente, xa que en moitos problemas físicos, unha "dimensión" equivale a un grao de liberdade.

Un perfeccionamento deste método, coñecido como mostraxe de importancia en estatística, implica a mostraxe dos puntos de forma aleatoria, pero con máis frecuencia onde o integrando é grande. Precisamente para iso habería que coñecer xa a integral, pero pódese aproximar a integral mediante unha integral dunha función similar ou utilizar rutinas adaptativas como a mostraxe estratificada, a mostraxe estratificada recursiva^[5]^[6] ou o algoritmo das VEGAS.

Na integración numérica, métodos como a regra trapezoidal usan un enfoque determinista. A integración de Monte Carlo, por outra banda, emprega un enfoque non determinista: cada realización proporciona un resultado diferente. En Montecarlo, o resultado final é unha aproximación do valor correcto coas respectivas barras de erro, e é probable que o valor correcto estea dentro desas barras de erro.

Visión xeral

O problema que aborda a integración de Montecarlo é o cálculo dunha integral definida multidimensional

I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}

onde Ω, un subconxunto de $\mathbb {R} ^{m}$ , ten volume

V=\int _{\Omega }d{\overline {\mathbf {x} }}

O enfoque inxenuo de Montecarlo consiste en ter puntos de mostraxe uniformemente en Ω:^[7]

dadas "N" mostras uniformes, ${\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in \Omega ,$ $I$ pódese aproximar por

I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})=V\langle f\rangle .

Isto é porque a lei dos grandes números garante que

\lim _{N\to \infty }Q_{N}=I.

Dada a estimación de I a partir de Q_N, os límites de erro de Q_N pódense estimar mediante a varianza da mostraxe mediante a estimación imparcial da varianza.

\mathrm {Var} (f)=\mathrm {E} (\sigma _{N}^{2})\equiv {\frac {1}{N-1}}\sum _{i=1}^{N}\mathrm {E} \left[\left(f({\overline {\mathbf {x} }}_{i})-\langle f\rangle \right)^{2}\right].

que leva a $\mathrm {Var} (Q_{N})={\frac {V^{2}}{N^{2}}}\sum _{i=1}^{N}\mathrm {Var} (f)=V^{2}{\frac {\mathrm {Var} (f)}{N}}=V^{2}{\frac {\mathrm {E} (\sigma _{N}^{2})}{N}}.$

posto que a secuencia

\left\{\mathrm {E} (\sigma _{1}^{2}),\mathrm {E} (\sigma _{2}^{2}),\mathrm {E} (\sigma _{3}^{2}),\ldots \right\}

está limitada debido a que é idéntica a Var(f), sempre que se asuma finita, esta varianza diminúe asintóticamente a cero como 1/N. A estimación do erro de Q_N é así

\delta Q_{N}\approx {\sqrt {\mathrm {Var} (Q_{N})}}=V{\frac {\sqrt {\mathrm {Var} (f)}}{\sqrt {N}}},

que diminúe como ${\tfrac {1}{\sqrt {N}}}$ . Este é o erro padrón da media multiplicado por $V$ .

Este resultado non depende do número de dimensións da integral, que é a vantaxe prometida da integración de Montecarlo fronte á maioría dos métodos deterministas que dependen exponencialmente da dimensión.^[8] É importante notar que, a diferenza dos métodos deterministas, a estimación do erro non é un límite de erro estrito; a mostraxe aleatoria pode non descubrir todas as características importantes do integrando que poden resultar nunha subestimación do erro.

Cunha distribución de mostras axeitada é posíbel explotar o feito de que case todos os integrandos de dimensións superiores están moi localizados e só un pequeno subespazo contribúe notabelmente á integral.^[9]

Unha gran parte da literatura de Montecarlo dedícase a desenvolver estratexias para mellorar as estimacións de erros. En particular, a mostraxe estratificada (dividir a rexión en subdominios) e a mostraxe de importancia (mostraxe a partir de distribucións non uniformes) son dous exemplos destas técnicas.

Simulación e optimización

Outra aplicación poderosa e moi popular para os números aleatorios na simulación numérica é a optimización numérica. O problema é minimizar (ou maximizar) as funcións dalgún vector que a miúdo ten moitas dimensións. Moitos problemas poden ser formulados deste xeito: por exemplo, un programa de xadrez por ordenador podería ser visto como tentar atopar o conxunto de, por exemplo, 10 movementos que produce a mellor función de avaliación ao final. No problema do vendedor ambulante o obxectivo é minimizar a distancia percorrida. Tamén hai aplicacións para o deseño de enxeñería, como a optimización multidisciplinar. Aplicouse con modelos case unidimensionaiss para resolver problemas de dinámica de partículas explorando de forma eficiente un gran espazo de configuración. A referencia de (Spall, J. C. (2003))^[10] é unha revisión exhaustiva de moitos problemas relacionados coa simulación e a optimización.

Problemas inversos

A formulación probabilística de problemas inversos conduce á definición dunha distribución de probabilidade no espazo modelo. Esta distribución de probabilidade combina información previa coa nova información obtida medindo algúns parámetros observábeis (datos). Como, no caso xeral, a teoría que vincula datos cos parámetros do modelo é non linear, a probabilidade posterior no espazo do modelo pode non ser fácil de describir (pode ser multimodal, algúns momentos poden non estar definidos, etc.).

Notas

↑ Kalos & Whitlock 2008.
↑ Ripley 1987
↑ Sawilowsky 2003
↑ Press et al. 1996
↑ MEZEI, M (31 de decembro de 1986). "Adaptive umbrella sampling: Self-consistent determination of the non-Boltzmann bias". Journal of Computational Physics 68 (1): 237–248. Bibcode:1987JCoPh..68..237M. doi:10.1016/0021-9991(87)90054-4.
↑ Bartels, Christian; Karplus, Martin (31 de decembro de 1997). "Probability Distributions for Complex Systems: Adaptive Umbrella Sampling of the Potential Energy". The Journal of Physical Chemistry B 102 (5): 865–880. doi:10.1021/jp972280j.
↑ Newman & Barkema 1999
↑ Press et al. 2007
↑ MacKay 2003, pp. 284–292
↑ Spall, J. C. (2003), Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley, Hoboken, NJ. http://www.jhuapl.edu/ISSO

Véxase tamén

Bibliografía

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. pp. 1–49.
Davenport, J. H. (1992). "Primality testing revisited". Papers from the international symposium on Symbolic and algebraic computation - ISSAC '92. pp. 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.

Fishman, G. S. (1995). Monte Carlo: Concepts, Algorithms, and Applications. New York: Springer. ISBN 978-0-387-94527-9.
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. pp. 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. Arquivado dende o orixinal o February 11, 2009.
Hubbard, Douglas (2007). How to Measure Anything: Finding the Value of Intangibles in Business. John Wiley & Sons. p. 46. ISBN 9780470110126.
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. p. 772. ISBN 978-0-470-17793-8.
MacKeown, P. Kevin (1997). Stochastic Simulation in Physics. New York: Springer. ISBN 978-981-3083-26-4.
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 (2nd ed.). Cambridge University Press. ISBN 978-0-521-43064-7.
Ripley, B. D. (1987). Stochastic Simulation. Wiley & Sons.
Robert, C.; Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). New York: Springer. ISBN 978-0-387-21239-5.
Rubinstein, R. Y.; Kroese, D. P. (2007). Simulation and the Monte Carlo Method (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-470-17793-8.
Sawilowsky, Shlomo S.; Fahoome, Gail C. (2003). Statistics via Monte Carlo Simulation with Fortran. Rochester Hills, MI: JMASM. ISBN 978-0-9740236-0-1.
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 (3rd ed.). John Wiley & Sons. ISBN 9780470512845.
Mazhdrakov, Metodi; Benov, Dobriyan; Valkanov, Nikolai (2018). The Monte Carlo Method. Engineering Applications. ACMO Academic Press. ISBN 978-619-90684-3-4.

Outros artigos

Ligazóns externas

What is Monte Carlo Simulation?.

[FOOTNOTEKalosWhitlock2008-1] Kalos & Whitlock 2008.

[Ripley-2] Ripley 1987

[Sawilowsky-3] Sawilowsky 2003

[Press-4] Press et al. 1996

[5] MEZEI, M (31 de decembro de 1986). "Adaptive umbrella sampling: Self-consistent determination of the non-Boltzmann bias". Journal of Computational Physics 68 (1): 237–248. Bibcode:1987JCoPh..68..237M. doi:10.1016/0021-9991(87)90054-4.

[6] Bartels, Christian; Karplus, Martin (31 de decembro de 1997). "Probability Distributions for Complex Systems: Adaptive Umbrella Sampling of the Potential Energy". The Journal of Physical Chemistry B 102 (5): 865–880. doi:10.1021/jp972280j.

[newman1999ch1-7] Newman & Barkema 1999

[8] Press et al. 2007

[9] MacKay 2003, pp. 284–292

[10] Spall, J. C. (2003), Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley, Hoboken, NJ. http://www.jhuapl.edu/ISSO

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]