Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2965612

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Fourier transform based on reducible representations of space groups
- 3. Numerical results
- References

Authors

Related links

J Algebr Stat. Author manuscript; available in PMC 2010 October 28.

Published in final edited form as:

J Algebr Stat. 2010; 1(1): 27–46.

PMCID: PMC2965612

NIHMSID: NIHMS224203

ude.etatsai@1orilksa (A. Skliros), ude.uhj@7krapw (W. Park)

This paper presents an efficient group-theoretic approach for computing the statistics of non-reversal random walks (NRRW) on lattices. These framed walks evolve on proper crystallographic space groups. In a previous paper we introduced a convolution method for computing the statistics of NRRWs in which the convolution product is defined relative to the space-group operation. Here we use the corresponding concept of the fast Fourier transform for functions on crystallographic space groups together with a non-Abelian version of the convolution theorem. We develop the theory behind this technique and present numerical results for two-dimensional and three-dimensional lattices (square, cubic and diamond). In order to verify our results, the statistics of the end-to-end distance and the probability of ring closure are calculated and compared with results obtained in the literature for the random walks for which closed-form expressions exist.

The topic of random walks on lattices and on finite groups has been of interest to mathematicians for at least half a century [15, 24, 36], and remains of interest in recent times [9, 10]. Often the main mathematical goals in studying random walks center around limiting behaviors of ensembles of walks as their length becomes large [28, 41, 43]. Similar topics have been studied intensely in the context of random walks on Lie groups, and associated convolutions (see e.g., [6, 16, 19]). Statements about the behaviors of random walks on broad classes of groups are often sought. However, our goal is somewhat different. In this paper, we develop a *computational methodology* to compute *exact* probability distributions of random walks of finite (but possibly large) length on particular finite groups. From these distributions we can extract any statistical quantity of interest. In spirit, our motivation is similar to that behind the development of group FFT’s Diaconis and Rockmore [8], though the groups of interest in our study have noncommutative subgroups that remain small as the group grows, and so the usual Abelian FFT can be used. In particular, our emphasis is on random walks on proper crystallographic space groups, which are discrete subgroups of the groups of rigid-body motions. This particular family of groups is important because they provide a natural setting to study *non-reversal* random walks in lattices in Euclidean space. Such walks serve as an intermediate between those that are purely random and those that are completely self-avoiding (such as those studied in [25, 30]). Walks on lattices have been studied extensively for a variety of reasons [42].

Many scientific fields use random and self-avoiding walks on lattices. Polymer theory is an important example of this. The statistical behavior of long polymer chains on lattices is often studied using the Monte Carlo sampling method introduced in [34]. This method has been used extensively in the literature [39]. The existence of polymer science traces back to the 1930s [27]. Through the decades of the 1950s and 60s many more new models were introduced, as reviewed in Flory’s book [13]. Studying the statistics of polymers is a matter of interest [1, 18] because of the knowledge about mechanical properties that results [26]. Some examples of these properties include the elasticity of rubbery materials [26] and the toughness and ductility of semi crystalline polymers. Another very important quantity is the entropy of the polymer solution. All of these properties depend on the statistics that we study [13, 26], which in turn are due to their molecular structure. Hence it is very important to study the structure and statistics of ensembles of long polymer molecules.

A polymer configuration can be represented as a lattice random walk if we consider the lattice bead the central carbon atom of the monomer and the lattice edge the covalent bond between the monomers. Let **r**_{i} denote the position of the *i ^{th}* bead, and let

$$\mathbf{r}=\sum _{i=1}^{n}{\mathbf{r}}_{i}-{\mathbf{r}}_{i-1}.$$

(1)

The corresponding end-to-end distance is *r* = ||**r**|| where $\Vert \mathbf{r}\Vert =\sqrt{\mathbf{r}\cdot \mathbf{r}}$. As a matter of notation, double vertical lines denote the two-norm of a vector, whereas single vertical lines denote the number of elements in a set, e.g., |{*a, b, c*}| = 3. Both notations are used in this paper and should not be confused.

Other important physical quantities are related to the distribution of values of *r*, denoted as *p*(*r*). A plethora of simulation methods, for instance those in [31], have been developed in order to obtain information about how *p*(*r*) evolves for polymer chains. Our study focuses on the random walk (RW) on lattices under the simple constraint that step *i* + 1 cannot return to the location of the walk at step *i*. This is called a “non-reversal random walk” (NRRW). It is convenient to think of NRRWs as *framed* walks. That is, a reference frame is attached to each step in the walk, with the local *x*-axis pointing along the new direction of motion, which in the case of a polymer is the bond vector.

Let *g _{n}* denote the reference frame attached to the

$${f}_{n+1}\left(g\right)=({f}_{n}\ast {f}_{1})\left(g\right)=\sum _{h\in G}{f}_{n}\left(h\right){f}_{1}({h}^{-1}\circ g).$$

(2)

Here the sum is taken over the proper crystallographic motion group, *G*, that describes the particular lattice walk. But since in practice the support of *f*_{1}(*g*) is very small, the sum does not need to be taken over this whole group, but only over the support of *f*_{1} for each value of *g* in the support of *f*_{n+1}.† Referring to [40] for more details, (2) can be written more explicitly as

$${f}_{n+1}(\mathbf{t},R)=({f}_{n}\ast {f}_{1})(\mathbf{t},R)=\sum _{A\in \mathbb{P}}\sum _{\mathbf{a}\in \mathbb{L}}{f}_{n}(\mathbf{a},A){f}_{1}\left({A}^{T}\right(\mathbf{t}-\mathbf{a}),{A}^{T}R).$$

(3)

where $\mathbb{P}$ is the proper crystallographic point group (described as a set of rotation matrices) and $\mathbb{L}$ is the lattice translation group (described as a set of vectors), combinations of which comprise all of the possible motions in *G*. Iterating these convolutions by using the result of each as the input for the next and letting *n* → *n* + 1 generates the sequence of distributions {*f _{n}*(

The main reason for using the group Fourier transform in this work is that the convolution theorem allows for the efficient computation of (2) (or equivalently, (3)). This provides an alternative technique for computing convolutions, and analyzing the limiting behavior of long walks by raising Fourier matrices to high powers rather than iterating convolution many times using (3) directly. For the theoretical foundations behind Fourier analysis on proper crystallographic space groups, see works such as [2, 3, 4, 5, 11, 17, 20, 22, 29, 37, 38].

Since the walks of interest will always be finite, we can define a maximal length of interest, *N*, and then rather than doing calculations with the full lattice $\mathbb{L}$, we can do calculations with the quotient lattice $\mathbb{L}\u2215N\mathbb{L}$. The group that acts on this lattice will be referred to here as the *lattice motion group*. This is the quotient group $G\u2215N\mathbb{L}$. Functionally, the only difference between *G* and $G\u2215N\mathbb{L}$ is that the latter is finite and translations larger than *N* steps in any spatial direction “wrap around,” whereas *G* is infinite because translations continue on to infinity in all spatial directions. As long as the length of a walk satisfies *n* < *N*/2, then there is no difference in computing the distribution *f _{n}*(

A unitary representation of a finite group, such as $G\u2215N\mathbb{L}$, is a mapping that takes elements of the group, *g*, and returns unitary matrices, π(*g, k*), with the properties

$$\Pi ({g}_{1}\circ {g}_{2},k)=\Pi ({g}_{1},k)\Pi ({g}_{2},k)\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\Pi (e,k)=\mathbb{I}$$

(4)

where *e* is the identity element of the group, *k* is an element of the dual space of the group, and $\mathbb{I}$ is the identity matrix with the same dimension as π(*g, k*). Sometimes it will be convenient to write π*k*(*g*) for π(*g, k*) and sometimes we will leave off the argument and write π_{k}. The first equality in (4) is analogous to *e*^{ik(θ1+θ2)} = *e*^{ikθ1}*e*^{ikθ2} which, together with unitarity and completeness, forms the foundations of all of the useful properties in Fourier analysis.

The matrix-valued functions π*k*(*g*) in (4) are called *unitary representations*. Usually Fourier analysis on groups is defined based on *irreducible* unitary representations. These are matrices with the smallest possible dimensions. However, we use *reducible* representations that are easy to define. The dimension of these representations will be $\mid \mathbb{P}\mid \times \mid \mathbb{P}\mid $. Since $\mid \mathbb{P}\mid $ will not typically be a huge number (e.g., 4 for the square lattice, 12 for the diamond lattice, 24 for the cubic lattice), it is hardly worth the added effort to reduce them. However, since the classical theory only addresses irreducible representations, we need to verify that our Fourier transform for $G\u2215N\mathbb{L}$ (which is defined in the following section) is in fact invertible.

Let {*R _{j}*} for $j=1,\dots ,\mid \mathbb{P}\mid $ denote the set of all rotations in the point group $\mathbb{P}$. Reducible representations of $G\u2215N\mathbb{L}$ are matrices with entries of the form [7]

$${\Pi}_{m,n}(g,\mathbf{k})={e}^{i\left({R}_{m}\mathbf{k}\right)\cdot \left(\mathbf{a}\right)}\delta \left({R}_{n}^{T}{A}^{T}{R}_{m}\right).$$

(5)

The *δ* function implies that ${R}_{n}^{T}{A}^{T}{R}_{m}={\mathbb{I}}_{\mathbb{P}}$ (the identity matrix with the same dimensions as rotations in the proper point group $\mathbb{P}$), forcing the equality $A={R}_{m}{R}_{n}^{T}$.

Let *g*_{1} = (*A*_{1}, *a*_{1}) and *g*_{2} = (*A*_{2}, *a*_{2}). The reducible representation defined in (5) evaluated at *g*_{1} *g*_{2} is given by:

$${\Pi}_{m,n}({g}_{1}\circ {g}_{2},\mathbf{k})={e}^{i\left({R}_{m}\mathbf{k}\right)\cdot ({A}_{1}{\mathbf{a}}_{2}+{\mathbf{a}}_{1})}\delta \left({R}_{n}^{T}{A}_{2}^{T}{A}_{1}^{T}{R}_{m}\right).$$

(6)

Then let *A* = π(*g*_{1}, **k**), *B* = π(*g*_{2}, **k**), and *C* = π(*g*_{1}, **k**)π(*g*_{2}, **k**). The entries of matrix *C* can be written as

$${C}_{m,n}=\sum _{j}{A}_{m,j}{B}_{j,n}=\sum _{j}{e}^{i\left({R}_{m}\mathbf{k}\right)\cdot \left({\mathbf{a}}_{1}\right)}\delta \left({R}_{j}^{T}{A}_{1}^{T}{R}_{m}\right){e}^{i\left({R}_{j}\mathbf{k}\right)\cdot \left({\mathbf{a}}_{2}\right)}\delta \left({R}_{n}^{T}{A}_{2}^{T}{R}_{j}\right).$$

(7)

Given the fact that ${R}_{j}={A}_{1}^{T}{R}_{m}$, (7) can be rewritten as:

$${C}_{m,n}={e}^{i\left({R}_{m}\mathbf{k}\right)\cdot \left({\mathbf{a}}_{1}\right)}{e}^{i\left({A}_{1}^{T}{R}_{m}\mathbf{k}\right)\cdot \left({\mathbf{a}}_{2}\right)}\delta \left({R}_{n}^{T}{A}_{2}^{T}{A}_{1}^{T}{R}_{m}\right),$$

(8)

or equivalently

$${C}_{m,n}={e}^{i\left({R}_{m}\mathbf{k}\right)\cdot ({A}_{1}{\mathbf{a}}_{2}+{\mathbf{a}}_{1})}\delta \left({R}_{n}^{T}{A}_{2}^{T}{A}_{1}^{T}{R}_{m}\right),$$

(9)

which indeed equals to the elements of (6).

The matrix elements of the Fourier transform of a function on a lattice motion group can be defined as:

$$\widehat{f}{\left(\mathbf{k}\right)}_{m,n}=\sum _{g\in G\u2215N\mathbb{L}}f\left(g\right)\Pi ({g}^{-1},\mathbf{k})=\sum _{A\in \mathbb{P}}\sum _{\mathbf{a}\in \mathbb{L}\u2215N\mathbb{L}}f(\mathbf{a},A){e}^{i\left({R}_{m}\mathbf{k}\right)\cdot (-{A}^{T}\mathbf{a})}\delta \left({R}_{n}^{T}A{R}_{m}\right).$$

(10)

Using the properties of the delta function, (10) can be rewritten as

$$\widehat{f}{\left(\mathbf{k}\right)}_{m,n}=\sum _{\mathbf{a}\in \mathbb{L}\u2215N\mathbb{L}}f(\mathbf{a},{R}_{n}{R}_{m}^{T}){e}^{-i\left({\mathbf{k}}^{T}{R}_{m}^{T}{R}_{m}{R}_{n}^{T}\mathbf{a}\right)}$$

(11)

where **k** is drawn from the reciprocal lattice (see the appendix). By setting $\mathbf{u}={R}_{n}^{T}\mathbf{a}$, (11) becomes

$$\widehat{f}{\left(\mathbf{k}\right)}_{m,n}=\sum _{\mathbf{u}\in \mathbb{L}\u2215N\mathbb{L}}f({R}_{n}\mathbf{u},{R}_{n}{R}_{m}^{T}){e}^{-i(\mathbf{k}\cdot \mathbf{u})}.$$

(12)

Equation (12) can be identified as a *d*-dimensional space DFT-transform, where *d* is the dimension of the lattice. That is, $\mid \mathbb{L}\u2215N\mathbb{L}\mid ={N}^{d}$. The sum over $\mathbb{L}\u2215N\mathbb{L}$ is a nested sum of *d* one-dimensional sums from *j* = 0 to *N* – 1. The matrix $\widehat{f}\left(\mathbf{k}\right)$ is a $\mid \mathbb{P}\mid \times \mid \mathbb{P}\mid $ matrix where $\mid \mathbb{P}\mid $ is the number of rotations in the proper point group $\mathbb{P}$. We can reduce the computational cost by using the classical fast Fourier transform (FFT) to compute (12). The FFT is standard in many numerical/computational software packages.

In (12), the sum ${\sum}_{\mathbf{u}\in \mathbb{L}\u2215N\mathbb{L}}f({R}_{n}\mathbf{u},{R}_{n}{R}_{m}^{T}){e}^{-i(\mathbf{k}\cdot \mathbf{u})}$ is calculated over **u**. The FFT is calculated with respect to **u** and the non-zero terms of the summation occur on the support of $f({R}_{n}\mathbf{u},{R}_{n}{R}_{m}^{T})$. Since the term *R _{n}*

Our whole reason for wanting to compute Fourier transforms on space groups is that the property (4) immediately implies that

$$\widehat{{f}_{1}\ast {f}_{2}}\left(\mathbf{k}\right)=\widehat{{f}_{2}}\left(\mathbf{k}\right)\widehat{{f}_{1}}\left(\mathbf{k}\right).$$

(13)

This can be proven abstractly without going into the detailed structure of the representations in (5), as long as (4) holds. We know (4) to be true from the analysis provided in the equations (7)-(9).

By definition we have

$$\left(\widehat{{f}_{1}\ast {f}_{2}}\right)\left({\Pi}_{\mathbf{k}}\right)=\sum _{g\in {G}^{\prime}}\left(\sum _{h\in {G}^{\prime}}{f}_{1}\left(h\right){f}_{2}({h}^{-1}\circ g)\right){\Pi}_{\mathbf{k}}\left({g}^{-1}\right)$$

where ${G}^{\prime}=G\u2215N\mathbb{L}$. By setting *p* = *h*^{−1} *g* and substituting *g* = *h**p*, we have the following expression

$$\sum _{p\in {G}^{\prime}}\sum _{h\in {G}^{\prime}}{f}_{1}\left(h\right){f}_{2}\left(p\right){\Pi}_{\mathbf{k}}({p}^{-1}\circ {h}^{-1}).$$

By taking into account the homomorphism property of π** _{k}** and the commutativity of scalar-matrix multiplication and summation, this can be split into

$$\left(\sum _{p\in {G}^{\prime}}{f}_{2}\left(p\right){\Pi}_{\mathbf{k}}\left({p}^{-1}\right)\right)\left(\sum _{h\in {G}^{\prime}}{f}_{1}\left(h\right){\Pi}_{\mathbf{k}}\left({h}^{-1}\right)\right)=\widehat{{f}_{2}}\left({\Pi}_{\mathbf{k}}\right)\widehat{{f}_{1}}\left({\Pi}_{\mathbf{k}}\right).$$

This works regardless of whether or not the representations are irreducible.

Of course, such a convolution theorem has value only when we can recover a function from its Fourier transform. This is verified in the following subsection.

The function *f*(**a**, *A*) can be recovered from the set of Fourier transform matrices $\left\{\widehat{f}\right(\mathbf{k}\left)\right\}$ by the following formula:

$$f(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{\mathbf{k}}\widehat{f}{\left(\mathbf{k}\right)}_{m,n}{e}^{i\mathbf{k}\cdot {R}_{n}^{T}\mathbf{a}}\delta \left({R}_{n}^{T}A{R}_{m}\right).$$

(14)

It may not be obvious a priori that a function *f*(**a**, *A*) on a lattice motion group can be recovered from the Fourier transform in (10), since the representations are reducible. We can prove that (14) does recover *f*(**a**, *A*) by first writing:

$$g(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{\mathbf{k}}\sum _{\mathbf{u}\in \mathbb{L}\u2215N\mathbb{L}}f({R}_{n}\mathbf{u},{R}_{n}{R}_{m}^{T}){e}^{-i(\mathbf{k}\cdot \mathbf{u})}{e}^{i\mathbf{k}\cdot {R}_{n}^{T}\mathbf{a}}\delta \left({R}_{n}^{T}A{R}_{m}\right).$$

(15)

We will see if *g*(**a**, *A*) = *f*(**a**, *A*). By setting $\nu ={R}_{n}\mathbf{u}\Rightarrow \mathbf{u}={R}_{n}^{T}\nu $, (15) becomes

$$g(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{\mathbf{k}}\sum _{\nu \in \mathbb{L}\u2215N\mathbb{L}}f(\nu ,{R}_{n}{R}_{m}^{T}){e}^{-i{R}_{n}\mathbf{k}\cdot (\nu -a)}\delta \left({R}_{n}^{T}A{R}_{m}\right).$$

(16)

By setting **k**’ = *R _{n}*

$$g(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{{\mathbf{k}}^{\prime}}\sum _{\nu \in \mathbb{L}\u2215N\mathbb{L}}f(\nu ,{R}_{n}{R}_{m}^{T}){e}^{-i{\mathbf{k}}^{\prime}\cdot (\nu -a)}\delta \left({R}_{n}^{T}A{R}_{m}\right),$$

(17)

which obviously takes the form

$$g(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}f(\mathbf{a},{R}_{n}{R}_{m}^{T})\delta \left({R}_{n}^{T}A{R}_{m}\right)=f(\mathbf{a},A).$$

(18)

It is convenient to calculate the inverse Fourier transform for a lattice motion group using the classical Abelian inverse FFT transform in *d*-dimensional lattices for the translational part, and computing the rotational part by brute-force. That is, since (14) can be rewritten as

$$f(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{\mathbf{k}}\widehat{f}{\left(\mathbf{k}\right)}_{m,n}{e}^{i{R}_{n}\mathbf{k}\cdot \mathbf{a}}\delta \left({R}_{n}^{T}A{R}_{m}\right)$$

(19)

and since we can set ${\mathbf{k}}_{1}={R}_{n}\mathbf{k}\Rightarrow \mathbf{k}={R}_{n}^{T}{\mathbf{k}}_{1}$, (19) becomes

$$f(\mathbf{a},A)=\frac{1}{\mid \mathbb{P}\mid}\sum _{m,n=0}^{\mid \mathbb{P}\mid -1}\frac{1}{{N}^{d}}\sum _{{\mathbf{k}}_{1}}\widehat{f}{\left({R}_{n}{\mathbf{k}}_{1}\right)}_{m,n}{e}^{i{\mathbf{k}}_{1}\cdot \mathbf{a}}\delta \left({R}_{n}^{T}A{R}_{m}\right).$$

(20)

The term $\frac{1}{{N}^{d}}{\sum}_{{\mathbf{k}}_{1}}\widehat{f}{\left({R}_{n}{\mathbf{k}}_{1}\right)}_{m,n}{e}^{i{\mathbf{k}}_{1}\cdot \mathbf{a}}$ can be easily calculated by using software packages containing the inverse Fourier transform. Again we note, as in the case of the Fourier transform, that since the sum is over **k**_{1}, and $\widehat{f}$ is a function of **k**, the pseudocode would be of the form $\mathit{IFFTD}{\left(\widehat{f}\right({R}_{n}\mathbf{k}\left)\right)}_{m,n}$. Since we have the term $\delta \left({R}_{n}^{T}A{R}_{m}\right)\Rightarrow {R}_{m}={A}^{T}{R}_{n}$, we can simply calculate *f*(**a**, *A*) using $\frac{1}{\mid \mathbb{P}\mid}{\sum}_{n}\mathit{IFFTD}\left(\widehat{f}{\left({R}_{n}\mathbf{k}\right)}_{\text{index}({A}^{T},{R}_{n}),n}\right)$, where “*index*” calls the group table for the proper point group of rotational b symmetries of the lattice, $\mathbb{P}$.

The new feature of the methods presented in this paper and that of [40] is that the methods can efficiently generate exact statistics (to within machine precision) corresponding to *all* of the exponential number of conformations. This becomes more and more convenient when the number of segments increases. While previous methods relied on sampling, the new method presented here finds statistics for all the possible conformations in a very short time. A natural question to ask is if, and how much, the Fourier transform speeds up the computation of convolutions on proper space groups. The Fourier transform based on irreducible unitary representations will naturally be the fastest, but it also requires the most pre-processing in terms of determining all of the IURs.

Consider the case of a homogeneous polymer in which the single-step distribution function describing allowable conformational motions going from residue *i* to *i* + 1 is *f*_{1}(*g*). The end-to-end distribution in positions and orientations for a polymer of length *L* residues will then be the *n*-fold convolution *f _{L}*(

For each fixed value of $m,n\in \mathbb{P}$, the convolution over the periodized translational lattice can be computed via lattice translational FFT in $\mathcal{O}\left({N}^{d}\phantom{\rule{thinmathspace}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{thinmathspace}{0ex}}{N}^{d}\right)$ operations where $\mid \mathbb{L}\u2215N\mathbb{L}\mid ={N}^{d}$. This means that the cost for computing over all values of *m* and *n* will be ${\mid \mathbb{P}\mid}^{2}$ times this value, or $\mathcal{O}({\mid \mathbb{P}\mid}^{2}\cdot {N}^{d}\phantom{\rule{thinmathspace}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{thinmathspace}{0ex}}{N}^{d})$. This means that it is asymptotically more costly to perform one convolution by FFT than a single one-step convolution. However, if the goal is to find only *f*_{Lmax}(*g*) without all of the intermediate functions *f _{i}* for

In this section we demonstrate our method by calculating the probability distribution functions for non-reversal random walks of up to 400 segments on the square lattice and up to 20 segments on the cubic and diamond lattices.

First, we develop the array which defines the supports of the probability distribution functions on the square, cubic and diamond lattices. Taking into account the final number of segments that we want to reach (400, 20 and 20), we define arrays of dimensions (801, 801, 4) for the square, (41, 41, 41, 24) for the cubic and (41, 41, 41, 12) for the diamond lattice. The first two indices (for the square) and the first three (for the cubic and diamond) denote the Cartesian coordinates on the lattice whereas the last array coordinate denotes the index of the element of the point group describing discrete rotations. In order to avoid aliasing, the arrays for the Cartesian coordinates must be at least (2*N* + 1, 2*N* + 1) for the square lattice and (2*N* + 1, 2*N* + 1, 2*N* + 1) for the cubic and diamond lattices where *N* is the number of segments.

We use the periodized lattice. This can be obtained using the *mod*_{2N + 1} operation. For example, in the square lattice, the coordinate of (−1, 0) for the periodized lattice would be (*mod*(−1, 801), *mod*(0, 801)) = (800, 0). After we obtain the support arrays of the functions in the periodized lattice, we compute the fast Fourier transform thereof using the reducible representations we described above. The array for the Fourier transform in the square lattice will be in dimensions of (401, 401, 4, 4), and in the cubic lattice will be (41, 41, 41, 24, 24) and in the diamond lattice (41, 41, 41, 12, 12). One issue with the Fourier transform is the Gibbs peaks that occur for large numbers of segments (greater than 30). Classically these peaks occur when computing the Fourier transform of discontinuous functions. The probability distribution functions of random walks can exhibit sharp changes in values from one point in the lattice motion group to another. We deal with the problem by normalizing all the values by the biggest value. We round off all the values less than 10^{−15} to zero. After finding the Fourier transform, ${\widehat{f}}_{1}$, we compute the Fourier transform for the longer segments. We compute ${\widehat{f}}_{n}\left({\Pi}_{\mathbf{k}}\right)={\left({\widehat{f}}_{1}\right({\Pi}_{\mathbf{k}}\left)\right)}^{n}$ for all possible **k**, *n* is the number of segments. Finally, inverse Fourier transform gives *f _{n}*(

In Figure 1, we present the distribution of the end point of 20-segment NRRW on the square lattice. The probability density is depicted by the size and the darkness of the circles. All the 3^{20} possible end points are obtained and from there we can extract various statistics including the probability distribution of the end-to-end distance. Although we limited the number of segments as 20 in this example, we can increase this to a large value as long as the computer memory allows. In the following test, we use the 400-segment NRRWs.

Several important statistics, that are calculated in the literature [13, 14, 12, 23, 26, 33], and give information about the shape (width, skewness) of the distribution functions for *R*^{2}, are $\frac{\langle {R}^{4}\rangle}{{\langle {R}^{2}\rangle}^{2}}$, $\frac{\langle {R}^{6}\rangle}{{\langle {R}^{2}\rangle}^{3}}$ and $\frac{\langle {R}^{8}\rangle}{{\langle {R}^{2}\rangle}^{4}}$, where *R* is the end-to-end distance of the random walk. We compute these quantities using the end points obtained by our method, and we compare them with the results by the method described in [32]. When we compute the quantities, the NRRWs with from 1 to 400 segments are considered. For convenience, we will refer to $\frac{\langle {R}^{4}\rangle}{{\langle {R}^{2}\rangle}^{2}}$ as RATIO4, $\frac{\langle {R}^{6}\rangle}{{\langle {R}^{2}\rangle}^{3}}$ as RATIO6 and $\frac{\langle {R}^{8}\rangle}{{\langle {R}^{2}\rangle}^{4}}$ as RATIO8. In Figures 2(a), 3(a), and 4(a), we respectively compare RATIO4, RATIO6 and RATIO8 obtained using our method (crosses) and by the method described in [32] (a solid line). In addition, Figures 2(b), 3(b), and 4(b) respectively show the difference at every number of segments. This difference is defined as (*b* – *a*)/*a*, where *a* and *b* are the statistics (RATIO4, RATIO6 or RATIO8) obtained by the Mattice method [32] and our method, respectively.

RATIO4 = *R*^{4}/*R*^{2}^{2} in the square lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO6 = *R*^{6}/*R*^{2}^{3} in the square lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO8 = *R*^{8}/*R*^{2}^{4} in the square lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

Another statistical quantity of great importance is that of the ring closure. The approximate probability of the ring closure can be calculated analytically by the method of Jacobson and Stockmayer [21]. The term “ring closure” simply means the probability for a random walk to terminate in the origin. For the square lattice, in order for a walk to terminate in the origin, it has to have even number of segments and the number of segments has to be greater or equal than four. For the case of the square lattice, which is a two-dimensional lattice, the Jacobson-Stockmayer result reduces to the formula $\frac{1}{\pi n}$ [21]. We count the number of walks that are obtained by our Fourier method and terminate in the origin. Then we divide that number by the total number of random walks to have the probability of the ring closure. This probability is compared with the Jacobson-Stockmayer result, $\frac{1}{\pi n}$.

Figure 5(a) shows the probabilities of ring closure on the square lattice. The two results are obtained by the Jacobson-Stockmayer formula (a solid line) and our method (crosses). Figure 5(b) shows the difference between the two results in Figure 5(a). The difference is defined as (*b*–*a*)/*a*, where *a* and *b* are the probability of ring closure obtained by the Jacobson-Stockmayer method [21] and our method, respectively. The Jacobson-Stockmayer formula provides the probability of ring closure that is more accurate with larger *n*. The fact that the difference in Figure 5(b) is getting closer to zero means that the probability of ring closure obtained by our method is reliable.

Probability of ring closure on the square lattice (a) Comparison of the results obtained by Jacobson-Stockmayer method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

It is important to note that the main purpose of this comparison between the various statistics is to verify that our method accurately generates the NRRWs. Using the NRRWs obtained by our method, any kinds of statistics of the random walks can be computed, while the methods such as the Mattice method and the Jacobson-Stockmayer method can compute only the specific statistics.

As in the square lattice, we can apply our method to the NRRWs on the cubic lattice. Figure 6 shows the distribution of the end points of 10-segment NRRWs on the cubic lattice. Figures 7(a), 8(a), and 9(a) show the statistics of the end-to-end distance obtained using our method (crosses) and by the method described in [32] (a solid line) for up to 20 segments. In addition, Figures 7(b), 8(b), and 9(b) show the corresponding difference at every number of segments. This difference is defined in the same way as in the square lattice.

RATIO4 = *R*^{4}/*R*^{2}^{2} in the cubic lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO6 = *R*^{6}/*R*^{2}^{3} in the cubic lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO8 = *R*^{8}/*R*^{2}^{4} in the cubic lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

The probability of the ring closure that was calculated analytically by Jacobson and Stockmayer [21] is ${\left(\frac{3}{2\pi n}\right)}^{3\u22152}$ for the cubic lattice. In order for a walk on the cubic lattice to terminate in the origin, it has to have even number of segments and the number of segments has to be greater than or equal to four. Figure 10(a) shows the probabilities of the ring closure on the cubic lattice. The two results are obtained by the Jacobson-Stockmayer method (a solid line) and our method (crosses). Figure 10(b) shows the difference between the two results in Figure 10(a). We define this difference in the same way as in the square lattice.

As in the above two lattices, we can apply our method to the NRRWs on the diamond lattice. One distinctive feature of the diamond lattice is that this lattice is 2-definable [35]. Therefore, we start with ${\widehat{f}}_{2}$ as a smallest step and compute the NRRWs of the even number of segments. Figure 11 shows the distribution of the end points of 10-segment NRRWs on the diamond lattice. Figures 12(a), 13(a), and 14(a) show the statistics of the end-to-end distance obtained using our method (crosses) and by the method described in [32] (a solid line) for up to 20 segments. In addition, Figures 12(b), 13(b), and 14(b) show the corresponding difference at every number of segments. This difference is defined in the same way as in the above two lattices.

RATIO4 = *R*^{4}/*R*^{2}^{2} in the diamond lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO6 = *R*^{6}/*R*^{2}^{3} in the diamond lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

RATIO8 = *R*^{8}/*R*^{2}^{4} in the diamond lattice. (a) Comparison of the results obtained by Mattice method (a solid line) and our method (crosses). (b) Difference between the two results in (a).

The probability of the ring closure calculated by Jacobson and Stockmayer [21] is ${\left(\frac{3}{2\pi n}\right)}^{3\u22152}$ for the diamond lattice. In order for a walk on the diamond lattice to terminate in the origin, it has to have even number of segments and the number of segments has to be greater than or equal to six. Figure 15(a) shows the probabilities of the ring closure on the diamond lattice. The two results are obtained by the Jacobson-Stockmayer method (a solid line) and our method (crosses). Figure 15(b) shows the difference between the two results in Figure 15(a). We define this difference in the same way as in the above two lattices.

Lattice random walks with no immediate reversals have applications in several various fields such as polymer science, finance, crystallography, and robotics. In particular, we are interested in studying properties of polymers that depend mainly on their conformations. The statistics of these conformations are studied by simulating them as lattice random walks. As the number of lattice segments increases, the number of all possible conformations increases exponentially. In this paper we developed a method for calculating the distribution of the distal ends of the *N*-segment NRRWs in $\mathcal{O}\left({N}^{2}\phantom{\rule{thinmathspace}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{thinmathspace}{0ex}}N\right)$ computational cost for the square lattice and $\mathcal{O}\left({N}^{3}\phantom{\rule{thinmathspace}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{thinmathspace}{0ex}}N\right)$ computational costs for the spatial lattices (e.g., cubic and diamond). This is a significant improvement compared to the exponential computational cost required by brute-force enumeration, or the random sampling that is often used (e.g., Monte Carlo methods). Our method generated the distribution of the distal end of long NRRWs using convolution of short NRRWs. This convolution was implemented using the group Fourier transform for the lattice motion group.

In order to verify our method, we used our method to study statistical properties of lattice random walks, and then compared them with the statistical quantities that other existing methods computed. We considered the statistics of the end-to-end distance, which are $\frac{\langle {R}^{4}\rangle}{{\langle {R}^{2}\rangle}^{2}}$, $\frac{\langle {R}^{6}\rangle}{{\langle {R}^{2}\rangle}^{3}}$ and $\frac{\langle {R}^{8}\rangle}{{\langle {R}^{2}\rangle}^{4}}$, where *R* is the end-to-end of distance the random walks. First, these quantities were computed using the position information of the distal end of the random walks that are obtained using our method. Then the same statistical quantities were computed using the Mattice method [32]. We also considered the probability of the ring closure. This quantity was computed using two methods: Jacobson-Stockmayer theory [21] and our method. All the comparison between the statistical quantities that we considered here verified that our method generates the accurate distribution of the conformations of the non-reversible random walks.

This work was supported by NIH Grant 3R01GM075310-04S1.

A lattice is an infinite array of regularly spaced points in ${\mathbb{R}}^{d}$. Given a linearly independent set of not-necessarily-orthogonal basis vectors in ${\mathbb{R}}^{d}$, i.e.,

$$\{{\mathbf{b}}_{1},\dots ,{\mathbf{b}}_{d}\}\phantom{\rule{1em}{0ex}}\text{with}\phantom{\rule{1em}{0ex}}\mathrm{det}[{\mathbf{b}}_{1},\dots ,{\mathbf{b}}_{d}]\ne 0,$$

a lattice is defined as

$$\mathbb{L}=\left\{\sum _{i=1}^{d}{m}_{i}{\mathbf{b}}_{i}\phantom{\rule{thinmathspace}{0ex}}\mid \phantom{\rule{thinmathspace}{0ex}}{m}_{i}\in \mathbb{Z}\right\}$$

where $\mathbb{Z}$ denotes the integers. The vectors **k**, for the case of the multidimensional lattice Discrete Fourier Transform are defined to be of the form

$$\mathbf{k}=\sum _{j=1}^{d}{k}_{j}{\widehat{\mathbf{b}}}_{j}$$

(21)

where the set of vectors $\left\{{\widehat{\mathbf{b}}}_{j}\right\}$ are defined by the conditions

$${\mathbf{b}}_{i}\cdot {\widehat{\mathbf{b}}}_{j}=2\pi {\delta}_{ij}.$$

(22)

Written for all *i*, *j* {1,…, *d*} this becomes

$$\left[\begin{array}{c}\hfill {\mathbf{b}}_{1}^{T}\hfill \\ \hfill {\mathbf{b}}_{2}^{T}\hfill \\ \hfill \vdots \hfill \\ \hfill {\mathbf{b}}_{d}^{T}\hfill \end{array}\right]\left[{\widehat{\mathbf{b}}}_{1},{\widehat{\mathbf{b}}}_{2},\dots ,{\widehat{\mathbf{b}}}_{d}\right]=2\pi \mathbb{I}.$$

From this, it is clear that a set of vectors $\left\{{\widehat{\mathbf{b}}}_{j}\right\}$ can always be found when a basis $\left\{{\mathbf{b}}_{i}\right\}$ is given, since

$$\left[{\widehat{\mathbf{b}}}_{1},{\widehat{\mathbf{b}}}_{2},\dots ,{\widehat{\mathbf{b}}}_{d}\right]=2\pi {[{\mathbf{b}}_{1},{\mathbf{b}}_{2},\dots ,{\mathbf{b}}_{d}]}^{-T}$$

is well defined.

The set of vectors $\left\{{\widehat{\mathbf{b}}}_{j}\right\}$ forms a basis for a new lattice, called the *reciprocal lattice*, denoted as

$$\widehat{\mathbb{L}}=\left\{\sum _{i=1}^{d}{m}_{i}{\widehat{\mathbf{b}}}_{i}\phantom{\rule{thinmathspace}{0ex}}\mid \phantom{\rule{thinmathspace}{0ex}}{m}_{i}\in \mathbb{Z}\right\}.$$

It is possible for a lattice to be self-reciprocal, i.e., $\widehat{\mathbb{L}}=\mathbb{L}$, as in our cases of the unit square, the cubic and the diamond lattices.

^{†}Recall that the support of a function is the part of its domain corresponding to nonzero values of the function.

[1] Alexandrowicz Z. Monte carlo of chains with excluded volume - a way to evade sample attrition. Journal of Chemical Physics. 1969;51:561–565.

[2] Blokker E. A theory for the construction of the irreducible representations of finite groups. International Journal of Quantum Chemistry. 1972;6(5):925–933.

[3] Blokker E. A theory for the construction of the irreducible representations of finite groups. II. International Journal of Quantum Chemistry. 1973;7(6):1091–1097.

[4] Bradley CJ, Cracknell AP. Mathematical Theory of Symmetry in Solids. Oxford U. Press; 1971.

[5] Chechin GM, Popov VP, Raspopov VN. The irreducible representations of hexagonal space-groups. Kristallogra ya. 1980;25(4):661–674.

[6] Chirikjian GS. Stochastic Models, Information Theory, and Lie Groups. Vols. I and II. Birkhäuser; Boston: 2009/11.

[7] Chirikjian GS, Kyatkin AB. Engineering Applications of Noncommutative Harmonic Analysis. CRC Press; Boca Raton, FL: 2001.

[8] Diaconis P, Rockmore D. Efficient computation of the Fourier transform on finite groups. Journal of the American Mathematical Society. 1990;3(2):297–332.

[9] Diaconis P, Saloff-Coste L. Comparison techniques for random walk on finite groups. The Annals of Probability. 1993;21(4):2131–2156.

[10] Erschler A. On drift and entropy growth for random walks on groups. The Annals of Probability. 2003;31(3):1193–1204.

[11] Evarestov RA, Smirnov VP. Site Symmetry in Crystals: Theory and Applications. 2nd edition Springer-Verlag; Berlin: 1997.

[12] Flory PJ. Foundations of rotational isomeric state theory and general methods for generating configurational averages. Rotational Isomeric State Theory and Methods. 1974;7(3):381–392.

[13] Flory PJ. Statistical Mechanics of Chain Molecules. Hanser/Gardner Publications; Cincinnati, OH: 1985.

[14] Flory PJ, Jernigan RL. Second and fourth moments of chain molecules. Journal Of Chemical Physics. 1965;42(10):3509–3519.

[15] Furstenberg H. Random walks and discrete subgroups of Lie groups. Advances in Probability and Related Topics. 1971;1:1–63.

[16] Grenander U. Probabilities on Algebraic Structures. Dover: 2008.

[17] Hahn T. International tables for crystallography. Brief teaching edition of volume A, Space-group symmetry. Kluwer Academic Publishers; Boston, MA: 1996.

[18] He SQ, Scheraga HA. Macromolecular conformational dynamics in torsional angle space. Journal of Chemical Physics. 1998;108:271–286.

[19] Heyer H. Probability Measures on Locally Compact Groups. Springer-Verlag; 1977.

[20] Iversen B. Lectures on Crystallographic Groups. Matematisk Institut, Aarhus Universitet; 1990.

[21] Jacobson H, Stockmayer WH. Intramolecular reaction polycondensations. I. the theory of linear systems. Journal of Chemical Physics. 1950;18(12):1600–1606.

[22] Janssen T. Crystallographic Groups. North Holland/American Elsevier; New York: 1972.

[23] Jernigan RL, Flory PJ. Moments of chain vectors for models of polymer chains. Journal of Chemical Physics. 1969;50(10):4178–4185.

[24] Kesten H. Symmetric random walks on groups. Transactions of the American Mathematical Society. 1959;92(2):336–354.

[25] Kesten H. On the number of self-avoiding walks. Journal of Mathematical Physics. 1963;4(7):960–969.

[26] Kotelyanskii M, Theodorou DN. Simulation methods for Polymers. Marcel Dekker Inc.; New York, NY: 2004.

[27] Kuhn W. Concerning the shape of thread shapes molecules in solution. Kolloid-Zeitschrift. 1934;68:2–15.

[28] Lawler GF. Intersections of Random Walks. Birkhäuser; Boston: 1996.

[29] Mackey GW. The Theory of Unitary Group Representations. The University of Chicago Press; Chicago: 1976.

[30] Madras N, Slade G. The self-avoiding walk. Birkhäuser; Boston: 1996.

[31] Mark JE, Abou-Hussein R, Sen TZ, Kloczkowski A. Some simulations on filler reinforcement in elastomers. Polymer. 2005;46:8894–8904.

[32] Mattice WL, Sienicki K. Extent of the correlation between the squared radius of gyration and squared end-to-end distance in random flight chains. Journal of Chemical Physics. 1989;90(3):1956–1959.

[33] Mattice WL, Suter UW. Conformational Theory of Large Molecules, the Rotational Isomeric State Model in Macromolecular Systems. Wiley; New York, NY: 1994.

[34] Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E. Equation of state calculations by fast computing machines. Journal of Chemical Physics. 1953;21:1087–1092.

[35] Meyer P. Lattice geometries. http://www.hermetic.ch/compsci/lattgeom.htm.

[36] Montroll EW, Weiss GH. Random walks on lattices. II. Journal of Mathematical Physics. 1965;6(2):167–181.

[37] Neto N. Irreducible representations of space groups. Acta Crystallographica. 1973;29:464–472.

[38] Neto N. Numerical-calculations of irreducible representations of space groups. Computer Physics Communications. 1975;9(4):231–246.

[39] Sharaf MA, Mark JE. Monte carlo simulations on the effects of nanoparticles on chain deformations and reinforcement in amorhous polyethylene networks. Polymer. 2004;45:3943–3952.

[40] Skliros A, Chirikjian GS. Torsional random walk statistics on lattices using convolution on crystallographic motion groups. Polymer. 2007;48(7):2155–2173. [PMC free article] [PubMed]

[41] Spitzer F. Principles of Random Walk. 2nd edition Springer; 1976.

[42] Vanderzande C. Lattice models of polymers. Cambridge University Press; 1998.

[43] Weiss GH. Aspects and applications of the random walk. North Holland: 1994.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |