Bundling Monte Carlo

bundling_monte_carlo.pdf

bundling_monte_carlo.tex

\documentclass{article}

\usepackage{amsmath}
\usepackage{graphicx}

\title{Monte Carlo and Bundling Moves}

\author{David W.H. Swenson}


\def\Pacc{\ensuremath{P_\text{acc}}}


\begin{document}
\maketitle

\section{Detailed balance in Monte Carlo}

First, let's talk about detailed balance.  I would say that detailed balance
is technically the combination of microscopic reversibility with ergodicity.
We frequently use the words ``detailed balance'' to refer to just the
microscopic reversibility part. However, without ergodicity, you are not
sampling the entire ensemble. For example, a replica exchange move (without
any shooting choices) will satisfy microscopic reversibility, but obviously
isn't ergodic in the space of paths.

Because of this, I think it is important to recognize that we're only doing
ONE real move per step, no matter how many submoves occur in the process. It
is the overarching procedure, from the root mover, that must satisfy
detailed balance.

Now let's dive into the specifics of microscopic reversibility. That is, of
course, the condition that
\begin{equation}
    \rho(o) \pi(o\to n) = \rho(n) \pi(n\to o)
\end{equation}
where $\rho$ is the probability of a given state and $\pi$ is the transition
probability.

We can, of course, further decompose $\pi$ into the probability of
generating trial $n$ from $o$, called $\alpha(o\to n)$, and the probability
of accepting that trial move, called $\Pacc(o\to n)$. (I often use the
notation $P_\text{gen}$ instead of $\alpha$, but most of the literature uses
$\alpha$.)

This makes the previous equation into:
\begin{equation}
    \rho(o) \alpha(o\to n) \Pacc(o\to n) = \rho(n) \alpha(n\to o)
    \Pacc(n\to o)
\end{equation}
or equivalently:
\begin{equation}
    \frac{\Pacc(o\to n)}{\Pacc(n\to o)} =
    \frac{\rho(n) \alpha(n\to o)}{\rho(o) \alpha(o\to n)}
    \label{eq:ratios}
\end{equation}

Trivially, the Metropolis acceptance rule
\begin{equation}
    \Pacc(o\to n) = \min\left( 1, 
    \frac{\rho(n) \alpha(n\to o)}{\rho(o) \alpha(o\to n)}
    \right)
\end{equation}
satisfies this. There exist other acceptance rules, but we'll limit our
discussion here to Metropolis.

Importantly, this means that for any move to satisfy detailed balance, the
acceptance probability must be calculable and finite. This typically means
that we need at least the values of $\rho(n)\slash \rho(o)$ and
$\alpha(n\to o)\slash \alpha(o\to n)$ to be calculable and finite (and so
much the better if we can calculate each term).

\section{Necessity of reverse moves}

That bit about being calculable and \emph{finite} is the previous section is
very important. The most common pitfall in designing Monte Carlo moves is to
create a move where there is some case where the reverse move is not
possible. For example, imagine a flexible path length shooting move that
always took its shooting point at the midpoint of the trajectory. Because
the midpoint of one trajectory might not be the midpoint of the next
trajectory, this move can not be its own reverse. Technically, you could use
a normal shooting move as the reverse of this one, but then you'd have a
$1/L$ acceptance probability (where $L$ is the number of frames that it is
legal to shoot from).

In many cases, the fact that a specific submove does not satisfy microscopic
reversibility can be ameliorated by putting a ``reverse'' version of the
move somewhere else in the path tree. However, it is important to get the
relative probabilities of selecting these moves correct.

One example of this is the ensemble hopping in single replica TIS. Of
course, a hop from ensemble A to ensemble B can not be its own reverse move.
But a hop from ensemble B to ensemble A would be its reverse, and so we
ensure that such a hop exists. 

\section{Multi-stage propositions}

If our total move consists of multiple probabilistic decisions (such of
first deciding what kind of move to do, then deciding which ensemble to do
it on, then deciding some details of how to do the move), then $\alpha(o\to
n)$ can be split into subparts, one for each decision. Usually we make most
of these decisions isotropic (i.e., $\alpha_\text{part}(o\to n) =
\alpha_\text{part}(n\to o)$), which means that they play no overall role in
the Metropolis acceptance rule. However, it is important to remember that
those steps exist.

For example, let's consider the example in Fig.~\ref{fig:srtis_scheme}. As
mentioned in the previous section, the hop from A$\to$B requires a separate
move to be its reverse; the hop for B$\to$A. Both are available in that move
scheme, but with different probabilities of being selected.

Let's assume that our replica begins in ensemble A. We can easily enumerate
all possible moves: either we try a shooting move in A, or we try a hopping
move from A to B. 

\begin{figure}[tb]
    \centering
    \includegraphics[width=0.6\textwidth]{srtis_scheme}
    \caption{Move scheme for a simple single replica TIS example. In this
    example, the relative probability of shooting vs. hopping is different
    between ensemble A and ensemble B.}
    \label{fig:srtis_scheme}
\end{figure}

First let's consider the shooting move. For the sake of simplicity, we'll
just describe it as a standard one-way shooting move. Generating the trial
consists of the following steps:

\begin{enumerate}
    \item Identify that we're in ensemble A. This is determistic.
    \item Choose to do a shooting move. The probability of this is
        $P_\text{shoot}=0.5$ given that we are in A.
    \item Choose to shoot forward with probability $P_\text{fwd}=0.5$.
    \item Choose a specific frame $x_\text{sh}$ from the trajectory to be
        the shooting point, with probability $1/(L_o-2)$ where $L_o$ is the
        length of the trajectory (neither first nor last frame are allowed
        shooting points).
    \item Generate the new trajectory segment with probability
        $P_\text{traj}(\text{sh}\to x_{L_n})$.
\end{enumerate}

This means that the total probability of generating this trajectory is:
\begin{equation}
    \alpha(o\to n) = P_\text{shoot} P_\text{fwd} \frac{1}{L_o-2}
    P_\text{traj}(\text{sh}\to x_{L_n})
\end{equation}

The shooting move in A is its own reverse move, so the first two steps have
the exact same probability. Then we need to select the \emph{same} shooting
point from the \emph{new} trajectory. This means that in the third step, the
probability is $1/(L_n-2)$. Altogether, this means that the ratio of the
probabilities which goes into the Metropolis acceptance rule is:
\begin{equation}
    \frac{\alpha(n\to o)}{\alpha(o\to n)} = \frac{L_o-2}{L_n-2} 
    \frac{P_\text{traj}(\text{sh}\to x_{L_o})}
    {P_\text{traj}(\text{sh}\to x_{L_n})} = \frac{L_o-2}{L_n-2}
\end{equation}
where the equality of probability of generating the different trajectories
is one of the results of transition path sampling.

Now we consider the other move from the A ensemble: the replica hopping.
Identification of which ensemble we're in is, of course, still
deterministic. And the probability of selecting ensemble hopping is
$P_\text{hop,A}=0.5$. From there, the trial is generated deterministically.
So we have $\alpha(o\to n) = P_\text{hop,A}$.

Now consider the reverse move. If the hop to B is accepted, then obviously
the reverse move must start in B and hop to A. So, given that the replica
starts in B, the probability of selecting the hop to $A$ is
$P_\text{hop,B}=0.3$. Again, everything \emph{inside} the hopping move is
deterministic, so $\alpha(n\to o) = P_\text{hop,B}$.

Put these together and we get:
\begin{equation}
    \frac{\alpha(n\to o)}{\alpha(o\to n)} =
    \frac{P_\text{hop,B}}{P_\text{hop,A}} = \frac{0.3}{0.5} = 0.6
\end{equation}
Note in this case, the ratio is determined by the probability of selecting
the move, whereas in the case that the move was its own reverse, the ratio
was determined by details within the move.

\section{Bundling Moves}

Now we turn to the question of what I call ``bundling'' moves. This is when,
instead of combining moves to make a multi-stage proposition in the normal
sense, you take sub-moves which each consist of a full Monte Carlo
propose-accept cycle. Assuming that a reverse move exists, this move can be
accepted with probability based on the ratio of the probability of selecting
the move to selecting its reverse.

Note that the existence of the reverse is important. Just because each move
is its own reverse doesn't mean the sequence will be. Consider a move with
is \verb+shootA-repexAB+: the submoves are their own reverse, but the
combination clearly isn't. However, as mentioned in the section of reverse
moves, you could always make the total move satisfy detailed balance by
adding the possibility of doing the actual reverse move, which is
\verb+repexAB-shootA+.

Here's the detailed mathematics behind bundling. Let's consider a 3-step
sequence of \verb+shootA-repexAB-shootA+. Clearly, this move is its own
reverse, so let's just think of it alone. For now, we'll restrict ourselves
to cases where the reverse mover is just the original mover with submoves in
reverse order (there may be cases which satisfy microscopic reversibility
where that isn't the case, but this is both the most common situation and
makes the proof easier).

Since we have a sequence of steps, we'll consider what those intermediate
states might be. Let's define our trial path as $o\to i_1 \to i_2 \to n$,
where $i_1$ and $i_2$ are the outcomes after the first shooting move and the
replica exchage, respectively. This means that the reverse trial path is $n
\to i_2 \to i_1 \to o$. If each individual submover is reversible, the whole
path is reversible. For cases where not all movers are their own reverse,
the reverse move must have the reverse submove at the appropriate position.
As long as these things are true, we can analyze this by looking at each
pair of trial/reverse trial paths, and look at each submover separately.

We'll define the total trial generation probability as:
\begin{equation}
    \alpha(o\to n) = \prod_{(\text{sub}, a, b)} 
    \alpha_\text{tot}^\text{sub}(a\to b) 
\end{equation}
where $\alpha_\text{tot}^\text{sub}(a\to b)$ is the total probability of
generating transition from $a$ to $b$ in submove $\text{sub}$.

Keep in mind that not every stage will be accepted. This means that, in
general, there are two possibilities for the probability at each stage, and
it will depend on the specific path which you use at which point. However,
we can split them into accepted moves and rejected moves. For accepted
moves, the generation probability is:
\begin{equation}
    \alpha_\text{tot}^\text{sub}(a\to b)  = 
    \alpha^\text{sub}(a\to b)\  \Pacc^\text{sub}(a\to b)
\end{equation}
For rejected moves, it is:
\begin{equation}
    \alpha_\text{tot}^\text{sub}(a\to a)  = 
    \alpha^\text{sub}(a\to b)\ (1-\Pacc^\text{sub}(a\to b))
\end{equation}

Of course, what really matters is the ratio of the forward and backward
acceptance probabilities, as seen in Eq.~\eqref{eq:ratios}. If a step in the
trial generation is rejected, then it would be an $a\to a$ step (e.g.,
perhaps we have $i_1 = o$ in our example). In that case, the reverse step
would also be $a\to a$. Since the initial state is the same, the ratio
$\alpha_\text{tot}^\text{sub}(a\to a) / \alpha_\text{tot}^\text{sub}(a\to
a) = 1$. 

For the case of accepted moves, we directly insert Eq.~\eqref{eq:ratios},
using the fact that the ratio of the acceptance probabilities is given  by
microscopic reversibility (independent of the specific acceptance
criterion). So:

\begin{equation}
    \frac{\alpha_\text{tot}^\text{sub}(a\to b)}
    {\alpha_\text{tot}^\text{sub}(b\to a)} = 
    \frac{\alpha^\text{sub}(a\to b)} 
    {\alpha^\text{sub}(b\to a)}
    \frac{\rho(b) \alpha^\text{sub}(b\to a)}{\rho(a) \alpha^\text{sub}(a\to b)}
    = \frac{\rho(b)}{\rho(a)} 
\end{equation}
Now we combine put this into the total ratio of the two products (which, it
is easy to see, is in this case also the product of the two ratios):

\begin{equation}
    \frac{\alpha(o\to n)}{\alpha(n\to o)} = 
    \prod_{(\text{sub}, a, b)}
    \frac{\rho(b)}{\rho(a)}  = \frac{\rho(n)}{\rho(o)}
\end{equation}
where we loop over all moves because $a=b$ for rejected moves, and
$\rho(a)\slash\rho(a) = 1$.

Plugging this into the Metropolis acceptance rule gives us
$\min(1, 1)=1$, so a trial move generated by combining several accepted
subtrials will always be accepted, assuming it is its own reverse move. If
it is not its own reverse move, it will need to be weighted by the
probability of choosing the reverse move.

The mathematics of this lends itself to the interpretation that \emph{all}
bundled moves are accepted, and that the moves with a ``rejected'' submove
really just propose a trial which is unchanged. This is a bit counter to
what how our intuition would like to describe this --- that the whole bundle
is rejected if no submove is accepted.


\end{document}

srtis_scheme.pdf