¿Son todos los algoritmos de Monte Carlo para aproximar $\pi$ ¿equivalente?

Question

Hay varias maneras de aproximarse $\pi$ utilizando un algoritmo de tipo Monte-Carlo. Por ejemplo, se pueden dibujar puntos aleatorios en el cuadrado de la unidad, y aproximar $\pi$ a través de la proporción de puntos que caen en el disco unitario. Otra forma sería utilizar un algoritmo basado en el problema de las agujas de Buffon: a partir de la proporción de agujas que caen sobre las líneas paralelas, se puede aproximar $\pi$ . Es de suponer que se pueden idear muchos otros algoritmos aleatorios para estimar $\pi$ .

Mi pregunta es: en términos de velocidad de convergencia, ¿son todos estos algoritmos equivalentes? ¿O hay algunos que darán decimales correctos de $\pi$ más rápido? ¿Cuál es el método de Monte Carlo para estimar $\pi$ que tiene la convergencia más rápida?

Answer 1

Tratando de mantener esto simple, respondiendo a tu muy buena pregunta original.(+1) Usando la aproximación de Riemann por rectángulos para obtener el área bajo la curva $y = \sqrt{1-x^2},$ para $0 < x < 1,$ y multiplicando por 4, puedes acercarte bastante a $\pi$ con sólo una docena de rectángulos. Más cerca si se usan trapezoides. Este no es un método de Monte Carlo pero el primer método de abajo es algo análogo (usando puntos aleatorios puntos al azar $x,$ en lugar de una cuadrícula determinista de puntos centrales como bases de rectángulos).

set.seed(430)  # retain for exactly the same simulation
m = 10^6;  x = runif(m);  h = sqrt(1-x^2)
mean(h)*4
[1] 3.142033           # estimate of pi
2*4*sd(h)/sqrt(m)
[1] 0.001784625        # rough 95% margin of simulation error

Así que un millón de $x$ -valores da $3.1420 \pm 0.0018.$

Un método de aceptación-rechazo similar al que has sugerido es algo menos eficiente.

set.seed(430)
m = 10^6;  x = runif(m);  y=runif(m)
acc = y <+ sqrt(1-x^2)
mean(acc)*4
[1] 3.143212           # aprx pi
2*4*sd(acc)/sqrt(m)
[1] 0.003282115        # marg of sim err

Aquí tenemos $3.1433 \pm 0.0033,$ que indica una convergencia algo más lenta.

Notas: (a) Mi propósito aquí no es dar los mejores métodos de simulación para aproximar $\pi,$ sino responder a su pregunta mostrando dos métodos comúnmente utilizados con diferentes tasas de convergencia. (b) No cuestiono la importancia del algoritmo Metropolis-Histings en simulación, pero según mi experiencia es más útil en dimensiones superiores a una o dos. (c) No soy del estado de Missouri, pero tengo una hermana que vive allí. una hermana que vive allí; si hay una manera de conseguir $\pi$ a 47 decimales de la moneda, eso es nuevo para mí y me gustaría ver una referencia autorizada para ello. quisiera ver una referencia autorizada para ello. (d) He ilustrado otros métodos de Monte Carlo en otra página algunos de ellos pueden adaptarse a su pregunta.

Answer 2

Todos los algoritmos aleatorios que se aproximan $\pi$ al intentar algo que tenga éxito con probabilidad $f(\pi)$ muchas veces, obteniendo una estimación de $f(\pi)$ y utilizando eso para estimar $\pi$ serán aproximadamente equivalentes. (Tanto si lo que intentamos es "soltar una aguja que intercepte una línea" o "elegir un punto que caiga dentro de un círculo" o cualquier otra cosa).

La razón es que su tasa de convergencia no tendrá nada que ver con el método. Si la probabilidad que intentamos estimar es $p$ , entonces después de $n$ el número de aciertos seguirá una distribución binomial, y el número típico de aciertos será $np \pm C \sqrt{np(1-p)}$ . Esto da una estimación de $p$ a dentro de $O(\frac1{\sqrt n})$ error, lo que significa millones de ensayos antes de poder estimar $p$ con tres decimales.

Sólo digo "aproximadamente" equivalente porque la probabilidad que estamos estimando puede depender de $\pi$ de muchas maneras. Si la probabilidad de éxito es $\frac12 + \frac{\pi}{1000}$ entonces se necesitarán muchos ensayos antes de que nuestra estimación de esta probabilidad sea significativamente mejor que "se trata de $\frac12$ ". Por otro lado, si la probabilidad de éxito es $10000\pi - 31415$ , entonces se estima que la probabilidad es aproximadamente $0.9$ es suficiente para dar uso $\pi$ a cinco dígitos después del decimal: $\pi \approx 3.14159$ .