Desviación de la estimación Monte Carlo Markov Chain pi

Question

Tengo este gráfico aquí:

http://imgur.com/1XmjcvA

https://github.com/martin-varbanov96/fmi-fall-2016/blob/master/monte_python/hw_1/b1.py

Representa el algoritmo de muestreo de cadena de Markov para estimar PI con 500 ensayos.

Mi pregunta es: -¿Por qué valores muy pequeños de delta y valores muy grandes de delta dan un resultado menos preciso comparado con los valores medianos?

Answer 1

Este método es un algoritmo Metropolis-Hastings para el muestreo de la distribución uniforme en el cuadrado de lado 2. Esto asigna una densidad de $1/4$ a cada punto dentro del cuadrado y $0$ a cada punto fuera del cuadrado. Para construir un algoritmo MH que tome muestras de esta distribución, primero se necesita una cadena que pueda llegar a cualquier punto del cuadrado. La cadena subyacente (que extrae puntos uniformemente de un cuadrado de lado $2 \delta$ centrada en el punto actual) es una cadena de este tipo. A continuación, se elige la probabilidad de aceptación correspondiente, de modo que la cadena resultante sea reversible con respecto a la distribución de equilibrio deseada. En este caso, esta reversibilidad se consigue simplemente aceptando siempre a un candidato dentro del cuadrado y rechazando a un candidato fuera del cuadrado.

Ahora bien, la tasa de convergencia de un algoritmo MCMC, incluido Metropolis-Hastings, depende en gran medida de que el tiempo de descorrelación de la cadena sea suficientemente corto. Esto requiere que la cadena de propuestas sea a la vez "ambiciosa", para que haya alguna posibilidad de que la cadena de propuestas recorra una distancia significativa en poco tiempo, y "conservadora", para que se acepte una fracción razonable de las transiciones propuestas. Cuanto mayor sea $\delta$ es, más ambiciosa (y, por tanto, menos conservadora) es la cadena de propuestas. Así, la tasa de convergencia es mejor para valores intermedios de $\delta$ .

Hacerlo riguroso no es tan sencillo, porque este problema está en el espacio continuo. Es necesario estimar el mayor valor propio no trivial del núcleo de probabilidad de transición, que en este caso es el operador integral $(Pf)(x)=\frac{4\delta^2-A(x)}{4\delta^2} f(x)+\frac{1}{4\delta^2} \int_{\| x-y \|_\infty \leq \delta,\| y \|_\infty \leq 1} f(y) dy$ donde $A(x)=\int_{\| x-y \|_\infty \leq \delta,\| y \|_\infty \leq 1} 1 dy$ .

En este caso de estimación $\pi$ puedes hacerte una idea limitada de lo que ocurre imaginando que empiezas tu cadena en el centro del cuadrado y mides cuánto tardarás en salir del círculo. Con pasos suficientemente pequeños, la mayoría de los pasos serán aceptados, por lo que tardarás como $O \left ( \frac{1}{\delta^2} \right )$ tiempo para salir del círculo (el cuadrado se debe a que los pasos tienden a anularse entre sí, ya que la velocidad media es cero en la mayor parte del cuadrado). Con pasos grandes, el primer paso tenderá a sacarnos del círculo, pero sólo se aceptará un paso con probabilidad $1/\delta^2$ por lo que tomará $O(\delta^2)$ pasos para salir del círculo. Si asumimos las "constantes" en estos $O()$ son comparables, entonces éstas se equilibrarán cuando $\delta=1$ para que el mejor $\delta$ debe estar en las inmediaciones de $1$ . Por supuesto, esta suposición puede ser totalmente errónea, pero en realidad suele ser razonable, como se desprende de sus datos.