¿Por qué el Monte-Carlo de trabajo de integración mejor que ingenuo integración numérica en alto dimensiones?

Question

¿Alguien puede explicar de forma sencilla el por qué de Monte-Carlo, funciona mejor que el ingenuo de Riemann integración en alto dimensiones? No entiendo cómo elegir al azar los puntos en los que se evalúa la función puede producir resultados más exactos de la distribución de estos puntos de manera uniforme en el dominio.

Más precisamente:

Deje $f:[0,1]^d \to \mathbb{R}$ ser un continuo delimitado función integrable, con $d\geq3$. Quiero calcular $A=\int_{[0,1]^d} f(x)dx$ $n$ puntos. Comparar 2 métodos simples.

El primer método es el enfoque de Riemann. Deje $x_1, \dots, x_n$ $n$ regularmente espaciados puntos en $[0,1]^d$$A_r=\frac{1}{n}\sum_{i=1}^n f(x_i)$. Tengo que $A_r \to A$$n\to\infty$. El error será del orden de $O(\frac{1}{n^{1/d}})$.

El segundo es el método de Monte-Carlo enfoque. Deje $u_1, \dots, u_n$ $n$ puntos elegidos al azar, sino uniformemente a lo largo de $[0,1]^d$. Deje $A_{mc}=\frac{1}{n}\sum_{i=1}^n f(u_i)$. El teorema del límite central me dice que $A_{mc} \to A$ $n\to \infty$ y $A_{mc}-A$ estará en el límite de una variable aleatoria gaussiana centrada en $0$ varianza $O(\frac{1}{n})$. Así que con una alta probabilidad de que el error será menor que $\frac{C}{\sqrt{n}}$ donde$C$, que no depende (?) en $d$.

Un problema obvio con el enfoque de Riemann es que si quiero aumentar el número de puntos, manteniendo una cuadrícula regular tengo que ir de$n=k^d$$n=(k+1)^d$, lo que añade un montón de puntos. Yo no tengo ese problema con Monte-Carlo.

Pero si el número de puntos que se fija en $n$, ¿ de Monte-Carlo realmente obtener mejores resultados que Riemann? Parece cierto en la mayoría de los casos. Pero no entiendo cómo elegir los puntos al azar puede ser mejor. ¿Alguien tiene una interfaz intuitiva explicación para esto?

Answer 1

Yo no creo que sea justo comparar Riemann Integración de Monte Carlo. En primer lugar, el uso de la habitual de las sumas de Riemann para la integración es una terrible manera de calcular las integrales, especialmente aquellos que oscilar violentamente o son simplemente malo en ciertas áreas. Basta con mirar a $d=1$. Riemann integración es$O(1/n)$, mientras que el Trapecio, regla de da $O(1/n^2)$, asumiendo que su función es tres veces diferenciable. Así que para empezar, en lugar de Riemann de integración uno tiene una gran cantidad de cuadratura numérica de los métodos disponibles. Hay docenas de tales métodos y algunos métodos adaptativos intentar concentrar la cuadratura de los puntos de muestreo en áreas donde la función se comporta mal. Algo así como la regla trapezoidal es una típica no adaptativos manera de obtener una mejor precisión por simplemente a evaluar en los puntos medios.

Sin embargo, como Hagen señaló que tienen que lidiar con la maldición de la dimensionalidad. La cuadratura de los métodos de comenzar a fallar muy mal en dimensiones superiores, porque usted necesita una gran cantidad de puntos. Entonces usted tiene que ser inteligente al respecto. Usted necesidad de centrarse en las áreas donde la función tiene grandes integral. Algo así como las VEGAS, Monte Carlo toma ventaja de esto por muestreo cerca de las áreas de los grandes valores de la función. Al hacerlo, usted está de cobertura de su quadriture puntos donde la función se comporta peor.

El simple Monte Carlo algoritmo de integración sólo muestras de puntos aleatorios. Si su función no es demasiado loco, esto tiende a hacer un poco mejor que un tamaño fijo de cuadrícula, especialmente en las funciones que varían (¡pero no demasiado!). Como un experimento de pensamiento, imagínate tratando de integrar algo muy bruscamente alcanzó su punto máximo y cero eleswhere. A continuación, Monte Carlo va a hacer un trabajo terrible, porque sólo hay un par de puntos donde la función es distinto de cero, mientras que la de Riemann la integración puede ser un poco mejor, especialmente si la anchura del pico es un poco más grande que el tamaño de la cuadrícula. En el otro extremo del espectro, considere la posibilidad de una función cuya derivada va de pequeño a grande en pequeñas ráfagas. Luego de Riemann de la integración va a ser bastante terrible, pero de Monte Carlo se tienden a un promedio de mejor manera.

Answer 2

Bueno, supongo que has respondido a la pregunta a ti mismo, menos la explicación intuitiva. Si aceptamos que el "Reimann integración" error será como S($ {} \frac{1}{n^{1/d}} $) y el MC de error como $ {} \frac{C}{\sqrt{n}} $, entonces es obvio que la MC, en general, dar de baja los errores de $ \mathbb d > 2$. The only thing that I suppose might still prevent us from being sure is that C parameter which does not depend (much?) on $ \mathbb d $. That might conceivably mean that MC still gives a larger error say for $ \mathbb d = 3 $ or $ \mathbb 4$, but as C really doesn't depend much on $ \mathbb d$, then it's obvious that as $ \mathbb d$ va más allá, MC va a ganar las manos hacia abajo.

Como Alex se mencionó anteriormente, usted hizo vender el Reimann enfoque un poco corto por romper cada dimensión de la igualdad de subintervalos $\Delta$S y la evaluación en los extremos (que no se puede O($ {} \frac{1}{n^{1/d}} $) de error). Para ser más justos para la "colocación de puntos en una cuadrícula regular" (que es supongo lo que son, en esencia, lo que contrasta con la colocación al azar), se debe usar una malla regular de puntos, pero "mejor" en su hipercubo. Por "mejor" me refiero a tener el primer punto en cada una de las dimensiones del eje en $ \mathbb 0.5\Delta$S, el segundo en $ \mathbb 1.5\Delta$S, etc, en lugar de $\Delta$S, $ \mathbb 2\Delta$S, etc. Esto dará lugar a un error de O($ {} \frac{1}{n^{2/d}} $) en lugar de, como se utiliza eficazmente los puntos medios. Este es el mejor que usted puede hacer tratando de calcular una integral por solo "muestreo" puntos colocados en una cuadrícula regular, pero de Monte Carlo se seguía latente que fácilmente después de $ \mathbb d = 4$.

Así que esto es donde todavía parece contra-intuitivo, ¿cómo puede MC vencer a la cuadrícula regular con el mismo número total de puntos cuando sólo lugares puntos al azar?! OK, así que aquí está la parte interesante y realmente la respuesta a tu pregunta: la colocación de puntos en una cuadrícula regular no es lo mejor que puede hacer la integración de sabios, ya que deja grandes huecos que pueden ser evitados por los más inteligentes de la colocación. Pensar en un $ \mathbb3D$ cuadrícula regular. Cuando se mira desde cualquier lado, es decir, cuando se mira en un $ \mathbb2D$ proyección de los puntos, los puntos a partir de la tercera dimensión caer en el mismo lugar (se superponen) y por lo tanto dejará de agujeros grandes que no ayudan a la integración. Lo mismo sucede en las dimensiones superiores, por lo que para una mejor integral estimación inferior-dimensiones de la cara(proyección) debe ser lo más homogénea y uniforme lleno de puntos como sea posible, sin tener puntos de la superposición y la creación de agujeros. Esto es lo que Quasi-Monte Carlo en las secuencias de tratar de hacer. Se coloca puntos (determinista) en lugares en los que (debe) evitar salir de ellos con superposición de dimensiones inferiores proyecciones y por esta razón se puede vencer a la cuadrícula regular incluso en $ \mathbb2D$$ \mathbb3D$.

Creo que luego de Monte Carlo como tener la misma ventaja que QMC (es decir, dejando menos agujeros evidentes en el bajo-dimensional caras, precisamente porque se carece de esa estructura regular que es responsable de los agujeros), pero con la gran desventaja de no colocar los puntos muy uniforme y homogénea (como una cuadrícula regular y QMC). En algún momento (en torno a $ \mathbb d>4$) la ventaja victorias sobre la situación de desventaja y MC comienza a latir de la cuadrícula regular.

EDIT: acabo de añadir un típico numérico experimento de prueba de los métodos aquí

Answer 3

Como usted dice, una de las principales razones para elegir un MC método es, precisamente, que no utilice el mismo número de puntos. Dicho esto, asumimos que debemos usar $n$ de las muestras. Tu pregunta es "¿ la elección de $n$ puntos al azar a hacer mejor o peor que ponerlos sobre una rejilla?"

La respuesta es: depende. En dos cosas clave.

• ¿Qué tipo de función se que la integración? Esto es crucial en la determinación de su $C$ que básicamente mide la variación de la función.
• Lo "aleatorio" se utilizan? De nuevo, te dicen "uniformemente", que es un muy apretado restricciones en cuanto a la técnica utilizada más a menudo con algún tipo de importancia de muestreo, pero vamos a ir con uniforme.

Ahora el punto es, en esencia, que el error de un método es realmente depende de la función, y pueden variar drásticamente. Por ejemplo, uno podría construir una función (lineal?) para los que aún cuadrícula siempre da una respuesta exacta, pero para que MC métodos de error distinto de cero. Y así sucesivamente. Del mismo modo, usted probablemente podría ingeniero peores situaciones para las cuales incluso las rejillas de hacer mal en casi todas las escalas, debido a fluctuaciones violentas en un pequeño rincón que siempre son sensibles, pero que no contribuyen en general. A continuación, MC podría nunca ver y hacer mejor las cosas. Columpios y rotondas.

Answer 4

Creo que no es el caso de que los puntos al azar un mejor desempeño que la selección de los puntos de forma manual como se hace en la Cuasi-métodos de Monte Carlo y la escasa método de cuadrícula: http://www.mathematik.hu-berlin.de/~romisch/papers/Rutg13.pdf

También en métodos de Monte Carlo se utiliza números aleatorios para generar una adaptación de método de integración global.