Next: Complete Graphs Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Mean Escape Times   Contents

# Chain Graphs

A general account of the problem of the first passage time in chemical physics was given by Weiss as early as 1965 [212]. In Reference Weiss67 he summarised various techniques for solving such problems to date, and gave a general formula for moments of the first passage time in terms of the Green's function of the Fokker-Plank operator. Explicit expressions for the mean first passage times in terms of the basic transition probabilities for the case of a one-dimensional random walk were obtained by Ledermann and Reuter in 1954 [213], Karlin and MacGregor in 1957 [214], Weiss in 1965 [212], Gardiner in 1985 [215], Van den Broeck in 1988 [216], Le Doussal in 1989 [217], Murthy and Kehr and Matan and Havlin in 1989-1990 [219,211,218], Raykin in 1992 [210], Bar-Haim and Klafter in 1998 [203], Pury and Cáceres in 2003 [220], and Slutsky, Kardar and Mirny in 2004 [221,222]. The one-dimensional random walk is therefore a very well researched topic, both in the field of probability and its physical and chemical applications. The results presented in this section differ in the manner of presentation.

A random walk in a discrete state space , where all the states can be arranged on a linear chain in such a way that for all , is called a one-dimensional or simple random walk (SRW). The SRW model attracts a lot of attention because of its rich behaviour and mathematical tractability. A well known example of its complexity is the anomalous diffusion law discovered by Sinai [223]. He showed that there is a dramatic slowing down of an ordinary power law diffusion (RMS displacement is proportional to instead of ) if a random walker at each site experiences a random bias field . Stanley and Havlin generalised the Sinai model by introducing long-range correlations between the bias fields on each site and showed that the SRW can span a range of diffusive properties [224].

Although one-dimensional transport is rarely found on the macroscopic scale at a microscopic level there are several examples, such as kinesin motion along microtubules [226,225], or DNA translocation through a nanopore [228,227], so the SRW is interesting not only from a theoretical standpoint. There is a number of models that build upon the SRW that have exciting applications, examples being the SRW walk with branching and annihilation [229], and the SRW in the presence of random trappings [230]. Techniques developed for the SRW were applied to study more complex cases, such as, for example, multistage transport in liquids [231], random walks on fractals [232,233], even-visiting random walks [234], self-avoiding random walks [235], random walks on percolation clusters [237,236], and random walks on simple regular lattices [238,239] and superlattices [240].

A presentation that discusses SRW first-passage probabilities in detail sufficient for our applications is that of Raykin [210]. He considered pathway ensembles explicitly and obtained the generating functions for the occupation probabilities of any lattice site for infinite, half-infinite and finite one-dimensional lattices with the random walker starting from an arbitrary lattice site. As we discuss below, these results have a direct application to the evaluation of the DPS rate constants augmented with recrossings. We have derived equivalent expressions for the first-passage probabilities independently, considering the finite rather than the infinite case, which we discuss in terms of chain digraphs below.

We define a chain as a digraph with nodes and edges, where and .Adjacent nodes in the numbering scheme are connected via two oppositely directed edges, and these are the only connections. A transition probability is associated with every edge , as described in Section 4.1.1. An -node chain is depicted in Figure 4.2 as a subgraph of another graph.

The total probability of escape from the chain via node if started from node is of interest because it has previously been used to associate contributions to the total rate constant from unique paths in DPS studies [9,8]. We can restrict the sampling to paths without recrossings between intermediate minima if we perform the corresponding recrossing sums explicitly [8].

We denote a pathway in by the ordered sequence of node indices. The length of a pathway is the number of edges traversed. For example, the pathway has length , starts at node and finishes at node . The indices of the intermediate nodes are given in the order in which they are visited. The product of branching probabilities associated with all edges in a path was defined above as . For example, the product for the above pathway is , which we can abbreviate as . For a chain graph , which is a subgraph of , we also define the set of indices of nodes in that are adjacent to nodes in but not members of as . These nodes will be considered as sinks if we are interested in escape from .

Analytical results for are easily derived:

 (6.24)

These sums converge if the cardinality of the set is greater than zero. To prove this result consider a factor, , of the form

 (6.25)

and assume that the branching probabilities are all non-zero, and that there is at least one additional escape route from , or . We know that because and . Hence . However, , and equality is only possible if , which contradicts the assumption of an additional escape route. Hence and . The pathway sums , , and can be obtained from Equation 4.24 by permuting the indices. The last two sums in Equation 4.24 are particularly instructive: the 'th term in the sum for and the 'th term in the sum for are the contributions from pathways of length and , respectively.

The pathway sums can be derived for a general chain graph in terms of recursion relations, as shown in Appendix C. The validity of our results for was verified numerically using the matrix multiplication method described in Reference Wales02. For a chain of length we construct an transition probability matrix with elements

 (6.26)

The matrix form of the system of Chapman-Kolmogorov equations [187] for homogeneous discrete-time Markov chains [123,187] allows us to obtain the -step transition probability matrix recursively as

 (6.27)

can then be computed as

 (6.28)

where the number of matrix multiplications, , is adjusted dynamically depending on the convergence properties of the above sum. We note that sink nodes are excluded when constructing and can be less than unity.

For chains a sparse-optimised matrix multiplication method for scales as ,and may suffer from convergence and numerical precision problems for larger values of and branching probabilities that are close to zero or unity [8]. The summation method presented in this section can be implemented to scale as with constant memory requirements (Algorithm B.1). It therefore constitutes a faster, more robust and more precise alternative to the matrix multiplication method when applied to chain graph topologies (Figure 4.3).

Mean escape times for are readily obtained from the results in Equation 4.24 by applying the method outlined in Section 4.1.5:

 (6.29)

and can be obtained from by permuting the subscripts 1 and 3.

The mean escape time from the graph if started from node can be calculated recursively using the results of Appendix D and Section 4.1.5 or by resorting to a first-step analysis [241].

Next: Complete Graphs Up: ENSEMBLES OF REARRANGEMENT PATHWAYS Previous: Mean Escape Times   Contents
Semen A Trygubenko 2006-04-10