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 and final states , respectively.[1] Terminology taken from graph theory. In probability theory, state is called absorbing if , which coincides with our definition of a sink. Every cycle of KMC simulation involves the generation of a single KMC trajectory connecting a node and a node . A source node is chosen from set with probability .

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

(6.12) |

KMC trajectories terminate when they arrive at an minimum, and the expected probability transfer to the region at the th KMC step is . If there is at least one escape route from to with a non-zero branching probability, then eventually all the occupation probabilities in must tend to zero and

(6.13) |

We now rewrite as a sum over all -step paths that start from and end at without leaving . Each path contributes to according to the appropriate product of branching probabilities, so that

where denotes the set of -step paths that start from and end at without leaving , and the last line defines the pathway sum .

It is clear from the last line of Equation 4.14 that for fixed the quantities define a probability distribution. However, the pathway sums are not probabilities, and may be greater than unity. In particular, 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 terms for which vanishes.

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

(6.15) |

where is the set of all appropriate paths from to of any length that can visit and revisit any node in . If we focus upon paths starting from minima in region

(6.16) |

where is the set of nodes in that are adjacent to minima in the complete graph , since vanishes for all other nodes. We can rewrite this sum as

(6.17) |

which defines the non-zero pathway probabilities for all paths that start from any node in set and finish at any node in set . The paths can revisit any minima in the set, but include just one minimum at the terminus. Note that and can be used interchangeably if there is only one state in set .

The average of some property, , defined for each KMC trajectory, , can be calculated from the as

(6.18) |

Of course, KMC simulations avoid this complete enumeration by generating trajectories with probabilities proportional to , so that a simple running average can be used to calculate . 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:

where the prime on the summation indicates that the paths are not allowed to revisit the region. We have also used the fact that .

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 are defined to be sinks and all the nodes in are the sources, i.e. every node in set is both a source and a sink. The required sum then includes all the pathways that finish at sinks of type , but not those that finish at sinks of type . The case when sets of sources and sinks (partially) overlap is discussed in detail in Section 4.6.