Applying MCMC Metropolis algorithm

Question

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up.

The path is a sequence $ z=(z_0,z_1, ...,z_{2n}) $ when $ z_i=(x_i, y_i) $ such that: $ z_0=(0,0) $, $ z_{2n}=(n, n) $ and with $ i=1, \dots, 2n $:

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

There are some very important constrains: maximum number of consecutive steps to the right is 2 and the maximum number of consecutive steps up is 3.

Lets define x-segment as maximum interval $ [i;j] \in [0;2n]$ when $ y_i= \dots =y_j $. Lets $ h(z) $ is a mean of x-segments lenghts on the way z.

How can one apply in this case MCMC Metropolis algorithm?

How will look probability distribution of interest $ \pi(x) $ and Markov chain kernel P?

I'm going to simulate all possible paths with R, that satisfy conditions and then compute $ \text{E}h(Z) $.

Any ideas, how to implement that?

P.S. I know, that maybe there are other ways to solve this questions, but I'm interesting in how could be used MCMC in this case.

For example let's say, that I have a way on the grind, that satisfies all conditions (maximum number of consecutive steps to the right is 2 and the maximum number of consecutive steps up is 3). What changes should I make, to produce a new way, that also will satisfy all conditions? Then by repeating that algorithm, I want to find all possible paths.

Answer 1

In my opinion, the tricky bit is to figure out a way of sampling the space of walks that you are interested in. Luckily, the problem is a classic one in polymer physics (e.g. modelling a 2d ideal polymer on a square lattice between fixed points), with an added constraint. Well, actually the constraints are two:

1. the lengths of the segments in both directions.
2. The walk can only go right or left.

As you might now, MC algorithms roughly fall in two categories: dynamic and static. With a static algorithm, you generate walks every time from scratch, while with a dynamic one you generate a new walk starting from some previous walk.

A way of dynamically sampling the space of walks could be defining an energy of the form

$$E = \begin{cases} \#_{violations} \text{ if the walk fits in the square and goes either right or up}\\ \infty \text{ otherwise} \end{cases} $$ with $\#_{violatios}$ being the number of times a constraint on the number of steps in a given direction is not respected. You can then propose a move to modify your walk, and the move will be accepted with probability $$ P(E) = \min[1,e^{-\beta E}]\,, $$ as is typical for the Metropolis test. Therefore, you would be relaxing the first constraint in order to get a faster dynamic, while still enforcing the second.

You might try both local moves (see pag.36 of http://arxiv.org/pdf/hep-lat/9405016.pdf) and global moves like the cut-and-permute (ibidem, pag. 38). Make sure to enforce the constraint on whether the walk goes always right or up.

The first walk can either be randomly generated (but make sure it connects the two corners of the square), or can just be a zig-zag line going towards the top right.

An implementation (in pseudocode) would be the following:

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)
  }
}

This means that you would be generating lots of walks, some of them will respect your constraint and others won't. You will only measure the ones who do follow your constraint. Also, this way you won't measure all the possible walks, but hopefully you'll get a representative sample, which is what you do in a Monte Carlo rather than in a complete enumeration method. Finally, pay attention to correlation times, since the walks obtained in this way will be heavily correlated. You might want to study the correlation function of h(z) and compute the integrated autocorrelation time $\tau_{int}$, as explained in the reference that I suggested, and choose to perform your measures only once every $\tau_{int}$ steps.

EDIT: fixed notation, added more info, added pseudocode, etc.

EDIT2: if you want to have an algorithm that produces only the kind of walks that satisfy your constraint at each step, you can simply introduce a while loop that iterates the algorithm until such a walk is found.

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)
}