Multilevel Moves

One notices that the average displacement in a single slice move is of order $\sqrt{\tau \lambda}$, which means that the diffusion through phase space goes to zero for small time steps. This is clearly an unwanted effect in particular because one would like to have an algorithm that is almost independent of the time step. This can be done by introducing multi-slice moves. Instead of moving one bead one cuts out and regrows a whole section of the path containing $2^k -1$ slices. The number $k$ is called the level of the move. Different methods have been suggested to regrow the path such as Lévy flights (Lévy, 1939) or the bisection method. The latter method will be described here using free particle sampling. The distribution in Eq. 2.63 for any level $k$ reads,

$$T_k({\bf r}) = (2^{k} \lambda \tau \pi )^{-D/2} \exp \left... ...bf r}-{\bf r}_{\rm m})^2}{2^{k} \lambda \tau} \right \} \quad.$$ (73)

First, one samples the bead ${\bf r}_i$ at slice $i+2^{k-1}$ from a Gaussian distribution $T_k$ centered at the midpoint of ${\bf r}_i$ and ${\bf r}_{i+2^k}$. As a second step with $k \to k-1$, one samples the slices corresponding to the next lower level $i+2^{k-1}$ and $i+3*2^{k-1}$ using the new $T_{k}$ and then keeps filling in the new coordinates until level $k=1$ is reached and a complete set of trial coordinates has been created. Finally, one performs one Metropolis step on the entire move.

The efficiency of this method can be improved by a multilevel Metropolis method. It rejects certain unlikely paths at an earlier level instead of waiting until the end and then using a single metropolis step. One starts at the highest level $k$, samples beads according to $T_k$, and accepts with

$$A(s_k \to s'_k) = \mbox{min} \left\{ \,1 \, , \, \frac{ T_k... ...k(s'_k) } { T_k(s_k \to s'_k) \, \pi_k(s_k) } \right\} \quad.$$ (74)

Note that the sampling distribution $T_k$ as well as the probability function $\pi_k$ are derived from the density matrix corresponding to the time step $2^k \tau$. If the move is rejected one starts again from the beginning. Otherwise, one continues at the next lower level $k \to k-1$ and samples all the midpoints according to the new $T_{k}$ and uses a modified acceptance probability,

$$A(s_k \to s'_k) = \mbox{min} \left\{ \,1 \, , \, \frac{ T_k... ...k \to s'_k) \, \pi_k(s_k) \, \pi_{k+1}(s'_k) } \right\} \quad.$$ (75)

The bisection is continued until the final level has been accepted. Only in this case, the particle coordinates are updated. This method has the advantage that unlikely moves are rejected early. The algorithm as a whole satisfies detailed balance because it is fulfilled on each level,

$$\frac{\pi_k(s_k)}{\pi_{k+1}(s_{k+1})} \; T_k(s_k \to s'_k) \... ...k+1}(s'_{k+1})} \; T_k(s'_k \to s_k) \; A_k(s'_k \to s_k) \;.$$ (76)

The total transition probability for the move being accepted at all levels is given by the following product,

$${\mathcal{P}}(s\to s') = \prod_{k=1}^{k_{\rm max}} \; T_k(s_k \to s'_k) \; A_k(s_k \to s'_k) \quad.$$ (77)

It is worth noting that one can use an approximate form of $\pi_k$ for all levels except for the lowest. These kinds of approximation modify only the acceptance ratios but not the MC averages. Therefore, it can be advantageous to use a simplified action, which can be computed faster. We often used the approximation $u_k \approx 2^{k-1} u_1$, which means that we can re-use the diagonal part of the pair action from the previous levels. Furthermore, the long-range as well as the off-diagonal contributions to the action are only calculated at the lowest level.