This entire book is, in one way or another, devoted to a single process: the random walk. As we will see, the rules that control the random walk are simple, even when we add elaborations that turn out to have considerable significance. However, as often occurs in mathematics and the physical sciences, the consequences of simple rules are far from elementary. We will also discover that random walks, as interesting as they are in themselves, provide a basis for the understanding of a wide range of phenomena. This is true in part because random walk processes are relevant to so many processes in such a wide range of contexts. It also follows from the fact that the solution of the random walk problem requires the use of so many of the mathematical techniques that have been developed and applied in contemporary twentieth-century physics. We'll start out simply, but it won't be long before we enounter aspects to the problem that invite – indeed require – intense scrutiny.

We begin our investigations by looking at the random walk in its most elementary manifestation. The reader may find that most of what follows in this chapter is familiar material. It is, nevertheless, useful to read through it. For one thing, review is always helpful. More importantly, connections that are hinted at in the early portions of this book will play an important role in later discussion.

The simplest walk

In the simplest example of a random walk the walker is confined to a straight line. This kind of walk is called, appropriately enough, a one-dimensional walk. In this case, steps take the walker in one direction or the other.

General introduction to generating functions

This book makes extensive use of generating functions. In that respect the discussions here are consistent with the approach that condensed matter physicists generally take when calculating properties of the random walk as it relates to problems of contemporary interest. This chapter is devoted to a discussion of the generating function and to an exploration of some of the ways in which the generating function method can be put to use in the study of the random walk. Many of the arguments in later chapters will call upon techniques and results that will be developed in the pages to follow. Thus, the reader is strongly urged to pay close attention to the discussion that follows, as topics and techniques that are introduced here will crop up repeatedly later on.

What is a generating function?

The generating function is a mathematical stratagem that simplifies a number of problems. Its range of applicability extends far beyond the mathematics of the random walk. Readers who have had an introduction to ordinary differential equations will have already seen examples of the use of the method of the generating function in the study of special functions. The generating function also plays a central role in graph theory and in the study of combinatorics, percolation theory, classical and quantum field theory and a myriad of other applications in physics and mathematics. Briefly, a generating function is a mathematical expression, depending on one or more variables, that admits a power series expansion. The coefficients of the expansion are the members of a family, or sequence, of numbers or functions.

The momentum-shell method

The method discussed in Section 11.3.1 will now be pursued further, in that it will be applied to the full effective Hamiltonian of an O(n) spin system, in which the effective Hamiltonian contains terms that are linear, quadratic, and of fourth order in the spin field. It is in the consideration of the higher order terms in the effective Hamiltonian (higher order than quadratic, that is) that the complications arise. The calculations that will be outlined here are not especially challenging in execution, but we will hint at extensions and generalizations that can become so.

In this chapter, the reader will be introduced to the field-theoretical version of the renormalization group, and to its first effective realization, the ∈ expansion for critical exponents. The approach will be that of the momentum-shell method developed in the previous chapters. The application of the method to the full O(n) Hamiltonian will be more complicated due to the coupling terms, which were neglected before.A straightforward, though somewhat tedious, calculation will lead to a modified set of renormalization equations. These differential equations will then be solved to lowest order in the variable ∈ = 4 – d, where d is the system's spatial dimensionality (three in the cases of interest to us). Using scaling arguments, the critical exponents will be obtained. Their relevance to the self-avoiding random walk will also be discussed.

The techniques to be discussed here are descendants of the original renormalization group method developed by Kenneth Wilson (Wilson, 1971a; Wilson, 1971b; Wilson and Kogut, 1974).

We've now had an introduction to the random walk. There has also been an introduction to the generating function and its utilization in the analysis of the process. Here we investigate some aspects of the random walk, both because they are interesting in their own right and because they further demonstrate the usefulness of the generating function as a theoretical technique in discussing this problem. In particular, we will apply the generating function method to study the problem of “recurrence” in the random walk. That is, we will address the question of whether the walker will ever return to its starting point, and, if so, with what probability.We will find that the spatial dimensions in which the walk takes place play a crucial role in determining this probability. Using an almost identical approach, the number of distinct points visited by the walker will also be determined.

We present the two studies below as a display of the power of the generating function technique in the study of the random walk process. For the skeptic, other examples will be provided in subsequent chapters.

Recurrence

We begin this chapter with a discussion of the question of recurrence of an unrestricted random walk. We will utilize the generating function, and an important statistical identity, to see how the dimensionality of the random walker's environment controls the probability of its revisiting the site from which it has set out. This study complements our earlier discussion and provides evidence for the power of the generating function approach.

A new generating function

A useful – but apparently little known – quantity enables one to obtain some key results with remarkably little effort.

We now have had an introduction to the random walk, and there has been a discussion of some of the most useful methods that can be utilized in the analysis of the process. The unifying theme of this chapter is the introduction of scaling arguments to provide insights into the behavior of the walker under a variety of circumstances. First, we will address in more depth the notion of universality of ordinary random walk statistics. Then, we will discuss the (mathematical) sources of non-Gaussian statistics. Finally, we will develop a few simple but central scaling results by looking once more at the path integral formulation of the random walk. In particular, using simple scaling arguments, we will be able to provide heuristic arguments leading to Flory's formula for the influence of self-avoidance on the spatial extent of a random walker's path.

Universality

Notions of universality play an important role in discussions of the statistics of the random walk.We have already seen a version of universality in Chapter 2, in which it was shown that the statistics of a long walk are Gaussian, regardless of details of the rules governing the walk, as long as the individual steps taken by the walker do not carry it too far. In the remainder of this section, the idea of universality will be developed in a way that will allow us to apply it to the random walk when conditions leading to Gaussian behavior do not apply.

As it turns out, universality in random walk statistics has a close mathematical and conceptual connection to fundamental properties of a system undergoing a special type of phase transition.

Mean field theory and spin wave contributions

Now that we have established the link between self-avoiding random walks and the O(n) model of magnetism, it is appropriate to look again at the magnetic system in the limit n → 0. Of special interest to us is its behavior in the immediate vicinity of the critical point. We will make extensive use of the insights provided by the study of critical phenomena that have emerged over the past three decades. Our initial approach to the problem of the statistical mechanics of the O(n) model will be to utilize the mean field ideas developed by Landau and others. Mean field theory will then be enhanced by the introduction of fluctuations which will be analyzed in a low order spin wave theory. The insights gained by this approach will lead us to a clearer picture of the phase transition as it pertains to the random walk problem. Finally, a full renormalization group calculation will be used to elucidate the scaling properties of this model. This final step in the analysis will be accomplished in Chapter 12.

Outline of the chapter

In this chapter we make use of the connection between the O(n) model and the self-avoiding walk to discuss aspects of the statistics of such a walk. We begin by reviewing the relationship between the spin model described by the O(n) energy function and the self-avoiding walk. Our initial focus will be on self-avoiding walks that are confined to a finite volume of space.

We begin this preface by reporting the results of an experiment. On April 23, 2003, we logged onto INSPEC – the physical science and engineering online literature service – and entered the phrase “random walk.” In response to this query, INSPEC delivered a list of 5010 articles, published between 1967 and that date. We then tried the plural phrase, “random walks,” and were informed of 1966 more papers. Some redundancy no doubt reduces the total number of references we received to a quantity less than the sum of those two figures. Nevertheless, the point has been made. Random walkers pervade science and technology.

Why is this so? Think of a system – by which we mean just about anything – that undergoes a series of relatively small changes and that does so at random. It is more likely than not that important aspects of this system's behavior can be understood in terms of the random walk. The canonical manifestation of the random walk is Brownian motion, the jittering of a small particle as it is knocked about by the molecules in a liquid or a gas. Chitons meandering on a sandy beach in search of food leave a random walker's trail, and the bacteria E. coli execute a random walk as they alternate between purposeful swimming and tumbling. Go to a casino, sit at the roulette wheel and see what kind of luck you have. The height of your pile of chips will follow the rules governing a random walk, although in this case the walk is biased (see Chapter 5), in that, statistically speaking, your collection of chips will inevitably shrink.

The modification of random walk statistics resulting from the imposition of constraints on the walkers will be repeatedly visited in this book. In fact, several chapters will be dedicated to the treatment of walkers that are forbidden to step on points they have previously visited. This kind of constraint represents the influence of a walk on itself. As we will see, calculations of the properties of the self-avoiding random walk require the use of fairly sophisticated techniques. The payoff is the ability to extract the fundamental properties of a model that accurately represents the asymptotic statistics of important physical systems, particularly long linear polymers.

The discussion referred to above will take place in later chapters. Here, we focus on other constraints, which embody the influence of a static environment on a walker. In the first part of this chapter, we will address the effect on a random walker of the requirement that it remain in a specified region of space. Specifically, we will look at walkers confined to a half-space, a linear segment in one dimension and a spherical volume in three dimensions. Then we will look at the case of walkers that are confined to the region outside a spherical volume. This case turns out to be relevant to issues relating to the intake of nutrients and the excretion of wastes by a simple, stationary organism, such as a cell. In fact, the final section of this chapter utilizes random walk statistics to investigate the limits on the size of a cell that survives by ingesting nutrients that diffuse to it from its surroundings.

The Born–Oppenheimer approximation is an essential element without which the very notion of a potential energy surface would not exist (1). It also provides an example of how different coordinates can often be treated independently as a first approximation. This approach has far-reaching consequences, since it greatly simplifies the construction of partition functions in statistical mechanics. The approximation involves neglect of terms that couple together the electronic and nuclear degrees of freedom. The nuclear motion is then governed entirely by a single PES for each electronic state because the Schrödinger equation can be separated into independent nuclear and electronic parts. The simplest approach to the nuclear dynamics then leads to the normal mode approximation via successive coordinate transformations. These developments are treated in some detail, partly because the results are used extensively in subsequent chapters, and partly because they highlight important general principles, which can easily be extended to other situations. The consequences of breakdown in the Born–Oppenheimer approximation, and treatments of dynamics beyond the normal mode approach, are discussed in Section 2.4 and Section 2.5, respectively.

Independent degrees of freedom

The Schrödinger equation that we normally wish to solve in order to identify wavefunctions and energy levels is a partial differential equation if more than one coordinate is involved. The most common method of solution for such equations involves separation of variables (2).

In this chapter we consider the calculation of thermodynamic and dynamic properties using stationary points sampled from the PES. In this approach attention is focused on local minima and transition states of the PES, defined as stationary points with zero and one negative Hessian eigenvalues, respectively (Section 4.1), and theories are required for the local densities of states and minimum-to-minimum rate constants, as outlined in Section 7.1.1 and Section 7.2.1. There can be several reasons to employ such techniques. In particular, it may be possible to calculate approximate thermodynamic and dynamic properties much faster than for conventional Monte Carlo or molecular dynamics simulations. For example, the equilibrium between competing structures separated by large potential energy barriers may be difficult to treat even with techniques such as parallel tempering. This situation arises for Lennard-Jones clusters with nonicosahedral global potential energy minima (Section 6.7.1, Section 8.3), where finite size analogues of a solid–solid phase transition can be identified (1–3). Such transitions probably represent the most favourable case for application of the superposition approximation discussed in Section 7.1, because only a few low-lying minima make significant contributions to the partition functions at the temperatures of interest. Some results for these transitions are illustrated in Section 7.1.1.

Dynamical properties have been calculated using databases of minima and transition states using a master equation approach (Section 7.2.2) for a number of different systems (4–28).

In Chapter 4 we discussed features of the potential energy surface such as minima, transition states, pathways and branch points. In this chapter some of the methods employed to locate and characterise these features will be outlined, while Chapter 7 will deal with techniques to calculate thermodynamic and dynamic properties that make explicit use of stationary point information. Other methods for sampling the PES and for calculating thermodynamic and dynamic quantities of interest will be summarised in the present chapter. Depending on the conditions of interest it may also be important to know what lies at the very bottom of the PES, for this is where the system will be found at low temperature if the dynamics permit equilibrium to be attained. Locating this global potential energy minimum is important in many different fields, and a diverse range of approaches have been suggested. Some of these are considered in Section 6.7, where we also discuss why certain potential energy surfaces make the global minimum relatively easy or difficult to locate.

Finding local minima

The field of geometry optimisation involves the location of stationary points on the PES, be they minima, transition states or higher index saddles with more than one negative Hessian eigenvalue (Section 4.1). Many algorithms have been suggested, even for the simplest problem of finding a local minimum, and there are even methods designed to locate branch points (Section 4.4) (1) and conical intersections (Section 2.4.2) (2–4).

The most interesting points of a potential energy surface are usually the stationary (or critical) points where the gradient vanishes. The geometrical definitions of local minima and transition states on a potential energy surface are given in Section 4.1. Here we also explain how the definition of a transition state is related to alternative interpretations based on free energy or dynamical considerations. Symmetry properties of steepest-descent pathways are then examined in Section 4.2, and a classification scheme for rearrangement mechanisms is presented in Section 4.3. The symmetry restrictions imposed by these results upon possible reaction pathways are illustrated with a number of examples. Branch points and quantum tunnelling are considered in Section 4.4 and Section 4.5, with emphasis on the symmetry properties of the pathways involved. The invariance of the potential energy surface, stationary points and pathways to coordinate transformations is discussed in Section 4.6. Finally, in Section 4.7, we investigate the origin of zero Hessian eigenvalues, which reveals a fundamental difference between the translational and rotational degrees of freedom (1).

Classification of stationary points

A stationary point on a PES is a nuclear configuration where all the forces vanish, i.e. every component of the gradient vector is zero, ∂V(X)/∂Xα = 0 for 1 ≤ α ≤ 3N. Here, and subsequently, we will drop the ‘e’ subscript from V, which served to remind us in Chapter 2 that the potential energy surface describes the variation of the electronic energy with the nuclear coordinates within the Born–Oppenheimer approximation.

In this final chapter we consider applications of energy landscape theory to structural glasses and supercooled liquids. The ultimate objective of this approach is to understand and predict how the glass transition and associated phenomena depend upon details of the underlying potential energy surface. The large number of different models proposed to explain the glass transition must partly reflect different ways of expressing similar ideas, as well as the fundamental importance of the problem (1, 2). An overview of some of these theoretical methodologies is given in Section 10.1. Detailed comparisons between theory and experiment for properties such as dielectric loss (3, 4) or light-scattering spectra (5, 6) of a molecular glass former clearly present a significant challenge, and hence discrimination between different models is relatively hard.

The most popular systems for computer simulations of structural glass formers are described in Section 10.2. Surveys of local minima and transition states, including theoretical approaches based on the superposition framework, are treated in Section 10.3 and Section 10.4, and results for model potential energy surfaces are summarised in Section 10.5. The influence of the system size on the PES is analysed in Section 10.6, where properties of the configuration space are compared with the scaling laws expected for random networks.