next up previous contents
Next: Mean Escape Times Up: Introduction Previous: Discrete Path Sampling   Contents


KMC and DPS Averages

We now show that the evaluation of the DPS sum in Equation 4.11 and the calculation of KMC averages are two closely related problems.

For KMC simulations we define sources and sinks that coincide with the set of initial states $ B$ and final states $ A$, respectively.[1] Terminology taken from graph theory. In probability theory, state $ i$ is called absorbing if $ P_{i,i}=1$, which coincides with our definition of a sink. Every cycle of KMC simulation involves the generation of a single KMC trajectory connecting a node $ b \in B$ and a node $ a \in A$. A source node $ b$ is chosen from set $ B$ with probability $ P_b^{\rm eq}/P_B^{\rm eq}$.

We can formulate the calculation of the mean first passage time from $ B$ to $ A$ in graph theoretical terms as follows. Let the digraph consisting of nodes for all local minima and edges for each transition state be $ \mathcal{G}$. The digraph consisting of all nodes except those belonging to region $ A$ is denoted by $ G$. We assume that there are no isolated nodes in $ \mathcal{G}$, so that all the nodes in $ A$ can be reached from every node in $ G$. Suppose we start a KMC simulation from a particular node $ \beta\in G$. Let $ P_\alpha(n)$ be the expected occupation probability of node $ \alpha $ after $ n$ KMC steps, with initial conditions $ P_\beta(0)=1$ and $ P_{\alpha\not=\beta}(0)=0$. We further define an escape probability for each $ \alpha\in G$ as the sum of branching probabilities to nodes in $ A$, i.e.

$\displaystyle \mathcal{E}_{\alpha}^{G} = \sum_{a\in A} P_{a,\alpha}.$ (6.12)

KMC trajectories terminate when they arrive at an $ A$ minimum, and the expected probability transfer to the $ A$ region at the $ n$th KMC step is $ \sum_{\alpha\in G}\mathcal{E}_{\alpha}^{G}P_\alpha(n)$. If there is at least one escape route from $ G$ to $ A$ with a non-zero branching probability, then eventually all the occupation probabilities in $ G$ must tend to zero and

$\displaystyle \Sigma_{\beta}^{G} = \sum_{n=0}^\infty \sum_{\alpha\in G}\mathcal{E}_{\alpha}^{G}P_\alpha(n) = 1.$ (6.13)

We now rewrite $ P_\alpha(n)$ as a sum over all $ n$-step paths that start from $ \beta $ and end at $ \alpha $ without leaving $ G$. Each path contributes to $ P_\alpha(n)$ according to the appropriate product of $ n$ branching probabilities, so that

\begin{displaymath}\begin{array}{lll} \Sigma_{\beta}^{G} &=& \displaystyle \sum_... ...E}_{\alpha}^{G} \mathcal{S}_{\alpha,\beta}^{G} = 1, \end{array}\end{displaymath} (6.14)

where $ \Xi(n)$ denotes the set of $ n$-step paths that start from $ \beta $ and end at $ \alpha $ without leaving $ G$, and the last line defines the pathway sum $ \mathcal{S}_{\alpha,\beta}^{G}$.

It is clear from the last line of Equation 4.14 that for fixed $ \beta $ the quantities $ \mathcal{E}_{\alpha}^{G} \mathcal{S}_{\alpha,\beta}^{G}$ define a probability distribution. However, the pathway sums $ \mathcal{S}_{\alpha,\beta}^{G}$ are not probabilities, and may be greater than unity. In particular, $ \mathcal{S}_{\beta,\beta}^{G}\ge1$ because the path of zero length is included, which contributes one to the sum. Furthermore, the normalisation condition on the last line of Equation 4.14 places no restriction on $ \mathcal{S}_{\alpha,\beta}^{G}$ terms for which $ \mathcal{E}_{\alpha}^{G}$ vanishes.

We can also define a probability distribution for individual pathways. Let $ \mW _\xi$ be the product of branching probabilities associated with a path $ \xi$ so that

$\displaystyle \mathcal{S}_{\alpha,\beta}^{G} = \sum_{n=0}^\infty \sum_{\xi\in\Xi(n)} \mW _\xi \equiv \sum_{\xi\in\alpha\leftarrow\beta} \mW _{\xi},$ (6.15)

where $ \alpha\leftarrow\beta$ is the set of all appropriate paths from $ \beta $ to $ \alpha $ of any length that can visit and revisit any node in $ G$. If we focus upon paths starting from minima in region $ B$

$\displaystyle \sum_{b\in B} \frac{P_b^{\rm eq}}{P_B^{\rm eq}} \sum_{\alpha\in G... ...n G_A} \mathcal{E}_{\alpha}^{G} \sum_{\xi\in\alpha\leftarrow b} \mW _{\xi} = 1,$ (6.16)

where $ G_A$ is the set of nodes in $ G$ that are adjacent to $ A$ minima in the complete graph $ \mathcal{G}$, since $ \mathcal{E}_{\alpha}^{G}$ vanishes for all other nodes. We can rewrite this sum as

$\displaystyle \sum_{\xi\in G_A\leftarrow B} \frac{P_b^{\rm eq}}{P_B^{\rm eq}} \... ...eq}}{P_B^{\rm eq}} \mW _{\xi} = \sum_{\xi\in A\leftarrow B} \mathcal{P}_\xi =1,$ (6.17)

which defines the non-zero pathway probabilities $ \mP _\xi$ for all paths that start from any node in set $ B$ and finish at any node in set $ A$. The paths $ \xi\in A\leftarrow B$ can revisit any minima in the $ G$ set, but include just one $ A$ minimum at the terminus. Note that $ \mW _\xi$ and $ \mP _{\xi}$ can be used interchangeably if there is only one state in set $ B$.

The average of some property, $ Q_{\xi}$, defined for each KMC trajectory, $ \xi$, can be calculated from the $ \mathcal{P}_\xi$ as

$\displaystyle \left<Q_{\xi}\right>=\sum_{\xi\in A\leftarrow B} \mathcal{P}_{\xi}Q_{\xi}.$ (6.18)

Of course, KMC simulations avoid this complete enumeration by generating trajectories with probabilities proportional to $ \mathcal{P}_{\xi}$, so that a simple running average can be used to calculate $ \left<Q_{\xi}\right>$. In the following sections we will develop alternative approaches based upon evaluating the complete sum, which become increasingly efficient at low temperature. We emphasise that these methods are only applicable to problems with a finite number of states, which are assumed to be known in advance.

The evaluation of the DPS sum defined in Equation 4.11 can also be rewritten in terms of pathway probabilities:

\begin{displaymath}\begin{array}{lll} k_{A,B}^{\rm DPS} &=& \displaystyle \sum_{... ...in A\leftarrow B}' \mathcal{P}_\xi \tau_\beta^{-1}, \end{array}\end{displaymath} (6.19)

where the prime on the summation indicates that the paths are not allowed to revisit the $ B$ region. We have also used the fact that $ k_{i_n,b}=P_{i_n,b}/\tau_b$.

A digraph representation of the restricted set of pathways defined in Equation 4.19 can be created if we allow sets of sources and sinks to overlap. In that case all the nodes $ A\cup B$ are defined to be sinks and all the nodes in $ B$ are the sources, i.e. every node in set $ B$ is both a source and a sink. The required sum then includes all the pathways that finish at sinks of type $ A$, but not those that finish at sinks of type $ B$. The case when sets of sources and sinks (partially) overlap is discussed in detail in Section 4.6.

next up previous contents
Next: Mean Escape Times Up: Introduction Previous: Discrete Path Sampling   Contents
Semen A Trygubenko 2006-04-10