Aplicar algoritmo MCMC Metropolis

Question

Estoy interesado en todas las posibles rutas de acceso (en la cuadrícula $\mathbb{N}^2 $) que va de $ (0,0) $$ (n, n) $. A cada paso hay dos posibilidades: ir a la derecha o subir.

El camino es una secuencia $ z=(z_0,z_1, ...,z_{2n}) $ al $ z_i=(x_i, y_i) $ tal forma que: $ z_0=(0,0) $, $ z_{2n}=(n, n) $ y con $ i=1, \dots, 2n $:

$ (x_i, y_i)=(x_{i-1}+1, y_{i-1}) $ o $ (x_i, y_i)=(x_{i-1}, y_{i-1}+1)$.

Hay algunos muy importantes limita: número máximo de pasos consecutivos a la derecha es 2 y el máximo número de pasos consecutivos es 3.

Permite definir x-segmento como máximo intervalo de $ [i;j] \in [0;2n]$ al $ y_i= \dots =y_j $. Permite a $ h(z) $ es una media de x-segmentos de longitudes en la forma z.

¿Cómo se puede aplicar en este caso MCMC algoritmo de Metropolis?

Cómo será el aspecto de distribución de probabilidad de interés $ \pi(x) $ y la cadena de Markov kernel P?

Voy a simular todos los posibles caminos con R, que cumplen los requisitos y, a continuación, calcular $ \text{E}h(Z) $.

Cualquier idea, cómo implementar eso?

P. S. sé, que tal vez hay otras formas de resolver esta pregunta, pero estoy interesado en cómo podría ser utilizado MCMC en este caso.

Por ejemplo, digamos que tengo una forma en la rutina, que cumplan con todas las condiciones (número máximo de pasos consecutivos a la derecha es 2 y el máximo número de pasos consecutivos es 3). ¿Qué cambios debo hacer, para producir un nuevo camino, que también va a satisfacer todas las condiciones? A continuación, repetir el algoritmo, quiero encontrar a todos los posibles caminos.

Answer 1

En mi opinión, la parte difícil es encontrar una forma de muestreo en el espacio de los paseos que usted está interesado en. Por suerte, el problema es un clásico en la física de polímeros (por ejemplo, la modelización 2d ideal polímero sobre un cuadrado de celosía entre puntos fijos), con una mayor restricción. Bueno, en realidad las restricciones son dos:

1. las longitudes de los segmentos en ambas direcciones.
2. La caminata sólo puede ir a la derecha o a la izquierda.

Como puede que ahora, MC algoritmos de aproximadamente caen en dos categorías: la dinámica y la estática. Con un algoritmo estático, generar paseos cada vez desde cero, mientras que con una dinámica de generar un nuevo camino a partir de algunas anteriores a pie.

Una forma dinámica de muestreo en el espacio de los paseos podría ser la definición de una energía de la forma

$$E = \begin{cases} \#_{violations} \text{ if the walk fits in the square and goes either right or up}\\ \infty \text{ otherwise} \end{casos} $$ con $\#_{violatios}$ siendo el número de veces que una restricción en el número de pasos en una dirección dada no es respetado. Usted puede, a continuación, proponer una modificación de su pie, y que el movimiento va a ser aceptado con una probabilidad de $$ P(E) = \min[1,e^{-\beta E}]\,, $$ como es típico para la Metrópoli de la prueba. Por lo tanto, sería la relajación de la primera restricción, con el fin de obtener una rápida dinámica, mientras que todavía cumplimiento de la segunda.

Usted puede tratar tanto de mudanzas locales (ver pag.36 de http://arxiv.org/pdf/hep-lat/9405016.pdf) y el mundial de movimientos como el de cortar y permutar (ibidem, pag. 38). Asegúrese de hacer cumplir la restricción de si el pie va siempre a la derecha o hacia arriba.

El primer paseo que puede ser generado al azar (pero asegúrese de que conecta las dos esquinas de la plaza), o puede ser simplemente una línea en zigzag que va hacia la parte superior derecha.

Una aplicación (en pseudocódigo) sería la siguiente:

Initialise the simulation
Create a walk that fits the square and goes only right or up
For (i=0, i< simulationSteps, i++){
  Apply some moves to the walk
  Propose the new configuration and reject it with probability P
  If ( the configuration respects the constraint on consecutive steps){
    measure h(z)
  }
}

Esto significa que usted estaría generando un montón de paseos, algunos de ellos respecto a la restricción y a otros no. Usted solo tendrá que medir las que hacen que siga su restricción. Además, de esta forma, no tendrás que medir a todos los paseos posibles, pero espero que usted va a obtener una muestra representativa, que es lo que haces en un Monte Carlo en lugar de en un completo método de enumeración. Por último, prestar atención a los tiempos de correlación, ya que los paseos se obtiene de esta manera será fuertemente correlacionados. Usted puede ser que desee para el estudio de la función de correlación de h(z) y calcular el integrado de autocorrelación tiempo $\tau_{int}$, como se explica en la referencia que he sugerido, y elegir para realizar sus medidas sólo una vez cada $\tau_{int}$ pasos.

EDIT:se fija la notación, la adición de más información, agregó pseudocódigo, etc.

EDIT2: si usted quiere tener un algoritmo que produce sólo el tipo de paseos que satisfacen la restricción en cada paso, usted puede simplemente introducir un bucle while que recorre el algoritmo hasta que un pie se encuentra.

Initialise the simulation
Create a walk that fits the square and goes only right or up
For (i=0, i< simulationSteps, i++){
  While( the configuration DOES NOT respect the constraint on consecutive steps){
    Apply some moves to the walk
    Propose the new configuration and reject it with probability P
  }
    measure h(z)
}