Beyond One Dimension

This chapter is devoted to the first-passage properties of fractal and nonfractal networks including the Cayley tree, hierarchically branched trees, regular and hierarchical combs, hierarchical blob structures, and other networks. One basic motivation for extending our study of first passage to these geometries is that many physical realizations of diffusive transport, such as hopping conductivity in amorphous semiconductors, gel chromatography, and hydrodynamic dispersion, occur in spatially disordered media. For general references see, e.g., Havlin and ben-Avraham (1987), Bouchaud and Georges (1990), and ben-Avraham and Havlin (2000). Judiciously constructed idealized networks can offer simple descriptions of these complex systems and their first-passage properties are often solvable by exact renormalization of the master equations.

In the spirit of simplicity, we study first passage on hierarchical trees, combs, and blobs. The hierarchical tree is an iterative construction in which one bond is replaced with three identical bonds at each stage; this represents a minimalist branched structure. The comb and the blob structures consist of a main backbone and an array of sidebranches or blob regions where the flow rate is vanishingly small. By varying the relative geometrical importance of the sidebranches (or blobs) to the backbone, we can fundamentally alter the first-passage characteristics of these systems.

When transport along the backbone predominates, first-passage properties are essentially one dimensional in character. For hierarchical trees, the role of sidebranches and the backbone are comparable, leading to a mean first-passage time that grows more quickly than the square of the system length. As might be expected, this can be viewed as the effective spatial dimension of such structures being greater than one.

Introduction

We now develop the ideas of the previous chapter to determine basic first-passage properties for both continuum diffusion and the discrete randomwalk in a finite one-dimensional interval. This is a simple system with which we can illustrate the physical implications of first-passage processes and the basic techniques for their solution. Essentially all of the results of this chapter are well known, but they are scattered throughout the literature. Much information about the finite-interval system is contained in texts such as Cox and Miller (1965), Feller (1968), Gardiner (1985), Risken (1988), and Gillespie (1992). An important early contribution for the finite-interval system is given by Darling and Siegert (1953). Finally, some of the approaches discussed in this chapter are similar in spirit to those of Fisher (1988).

For continuum diffusion, we start with the direct approach of first solving the diffusion equation and then computing first-passage properties from the time dependence of the flux leaving the system. Much of this is classical and well-known material. These same results will then be rederived more elegantly by the electrostatic analogies introduced in Chap. 1. This provides a striking illustration of the power of these analogies and sets the stage for their use in higher dimensions and in more complex geometries (Chaps. 5–7).

We also derive parallel results for the discrete random walk. One reason for this redundancy is that random walks are often more familiar than diffusion because the former often arise in elementary courses. It will therefore be satisfying to see the essential unity of their first-passage properties. It is also instructive to introduce various methods for analyzing the recursion relations for the discrete randomwalk.

You arrange a 7 P.M. date at a local bistro. Your punctual date arrives at 6:55, waits until 7:05, concludes that you will not show up, and leaves. At 7:06, you saunter in – “just a few minutes” after 7 (see Cover). You assume that you arrived first and wait for your date. The wait drags on and on. “What's going on?” you think to yourself. By 9 P.M., you conclude that you were stood up, return home, and call to make amends. You explain, “I arrived around 7 and waited 2 hours! My probability of being at the bistro between 7 and 9 P.M., P(bistro, t), was nearly one! How did we miss each other?” Your date replies, “I don't care about your occupation probability. What matteredwas your first-passage probability, F(bistro, t), which was zero at 7 P.M. GOOD BYE!” Click!

The moral of this juvenile parable is that first passage underlies many stochastic processes in which the event, such as a dinner date, a chemical reaction, the firing of a neuron, or the triggering of a stock option, relies on a variable reaching a specified value for the first time. In spite of the wide applicability of first-passage phenomena (or perhaps because of it), there does not seem to be a pedagogical source on this topic. For those with a serious interest, essential information is scattered and presented at diverse technical levels. In my attempts to learn the subject, I also encountered the proverbial conundrum that a fundamental result is “well known to (the vanishingly small subset of) those who know it well.”

Introduction

This chapter is devoted to first-passage properties in spherically symmetric systems. We shall see how the contrast between persistence, for spatial dimension d ≤ 2, and transience, for d > 2, leads to very different first-passage characteristics. We will solve first-passage properties both by the direct time-dependent solution of the diffusion equation and by the much simpler and more elegant electrostatic analogy of Section 1.6.

The case of two dimensions is particularly interesting, as the inclusion of a radial potential drift ν(r) ∝ 1/r is effectively the same as changing the spatial dimension. Thus general first-passage properties for isotropic diffusion in d dimensions are closely related to those of diffusion in two dimensions with a superimposed radial potential bias. This leads to nonuniversal behavior for the two-dimensional system.

As an important application of our study of first-passage to an isolated sphere, we will obtain the classic Smoluchowski expression for the chemical reaction rate, a result that underlies much of chemical kinetics. Because of the importance of this result, we will derive it by time-dependent approaches as well as by the quasi-static approximation introduced in Section 3.6. The latter approach also provides an easy way to understand detailed properties of the spatial distribution of reactants around a spherical trap.

First Passage between Concentric Spheres

We begin by computing the splitting (or exit) probabilities and the corresponding mean hitting times to the inner and outer the boundaries of the annular region R− ≤ r ≤ R+ as functions of the starting radius r (Fig. 6.1).

Reactions as First-Passage Processes

In this last chapter, we investigate simple particle reactions whose kinetics can be understood in terms of first-passage phenomena. These are typically diffusion-controlled reactions, in which diffusing particles are immediately converted to a product whenever a pair of them meets. The term diffusion controlled refers to the fact that the reaction itself is fast and the overall kinetics is controlled by the transport mechanism that brings reactive pairs together. Because the reaction occurs when particles first meet, first-passage processes provide a useful perspective for understanding the kinetics.

We begin by treating the trapping reaction, in which diffusing particles are permanently captured whenever they meet immobile trap particles. For a finite density of randomly distributed static traps, the asymptotic survival probability S(t) is controlled by rare, but large trap-free regions.We obtain this survival probability exactly in one dimension and by a Lifshitz tail argument in higher dimensions that focuses on these rare configurations [Lifshitz, Gredeskul, & Pastur (1988)]. At long times, we find that S(t) exp(−Atd/d+2), where A is a constant and d is the spatial dimension. This peculiar form for the survival probability was the focus of considerable theoretical effort that ultimately elucidated the role of extreme fluctuations on asymptotic behavior [see, e.g., Rosenstock (1969), Balagurov & Vaks (1974), Donsker & Varadhan (1975, 1979), Bixon & Zwanzig (1981), Grassberger & Procaccia (1982a), Kayser & Hubbard (1983), Havlin et al. (1984), and Agmon & Glasser (1986)].

We next discuss diffusion-controlled reactions in one dimension.

The Basic Dichotomy

A natural counterpart to the finite interval is the first-passage properties of the semi-infinite interval [0,∞] with absorption at x = 0. Once again, this is a classical geometry for studying first-passage processes, and many of the references mentioned at the outset of Chap. 2 are again pertinent. In particular, the text by Karlin and Taylor (1975) gives a particularly comprehensive discussion about first-passage times in the semi-infinite interval with arbitrary hopping rates between neighboring sites. Once again, however, our focus is on simple diffusion or the nearest-neighbor randomwalk. For these processes, the possibility of a diffusing particle making arbitrarily large excursions before certain trapping takes place leads to an infinite mean lifetime. On the other hand, the recurrence of diffusion in one dimension means that the particle must eventually return to its starting point. This dichotomy between infinite lifetime and certain trapping leads to a variety of extremely surprising first-passage-related properties both for the semi-infinite interval and the infinite system.

Perhaps the most amazing such property is the arcsine law for the probability of long leads in a symmetric nearest-neighbor random walk in an unbounded domain. Although this law applies to the unrestricted random walk, it is intimately based on the statistics of returns to the origin and thus fits naturally in our discussion of first-passage on the semi-infinite interval. Our natural expectation is that, for a random walk which starts at x = 0, approximately one-half of the total time would be spent on the positive axis and the remaining one-half of the time on the negative axis. Surprisingly, this is the least probable outcome.

Why Study the Wedge?

We now investigate the first-passage properties of diffusion in wedge domains with absorption when the particle hits the boundary (Fig. 7.1). There are several motivations for studying this system. One is that first passage in the two-dimensional wedge can be mapped onto the kinetics of various one-dimensional diffusion-controlled reaction processes. By this correspondence, we can obtain useful physical insights about these reactions as well as their exact kinetic behavior. These connections will be discussed in detail in the next chapter.

A second motivation is more theoretical and stems from the salient fact the survival probability and related first-passage properties in the wedge decay as power laws in time with characteristic exponents that depend continuously on the wedge opening angle. This arises, in part, because a wedge with an infinite radial extent does not have a unique characteristic length or time scale. One of our goals is to compute this exponent and to develop intuition for its dependence on the wedge angle. These results naturally lead to the “pie wedge” of finite radial extent that exhibits an unexpected discontinuous transition in the behavior of the mean exit time as the wedge angle passes through π/2. This feature also manifests itself as a pathology in the flow of a viscous fluid in a wedge-shaped pipe [Moffat & Duffy (1979)].

Finally, the first-passage properties to a sharp tip (wedge angle > π) is an essential ingredient in diffusion-controlled growth processes, such as dendrites, crystals, and diffusion-limited aggregates. The stability of such perturbations depends on whether the first-passage probability is largest at the tip or away from it.

What Is a First-Passage Process?

This book is concerned with the first-passage properties of random walks and diffusion, and the basic consequences of first-passage phenomena. Our starting point is the first-passage probability; this is the probability that a diffusing particle or a random-walk first reaches a specified site (or set of sites) at a specified time. The importance of first-passage phenomena stems from its fundamental role in stochastic processes that are triggered by a first passage event. Typical examples include fluorescence quenching, in which light emission by a fluorescent molecule stops when it reacts with a quencher; integrate-and-fire neurons, in which a neuron fires only when a fluctuating voltage level first reaches a specified level; and the execution of buy/sell orders when a stock price first reaches a threshold. Further illustrations are provided throughout this book.

A Simple Illustration

To appreciate the essential features of first-passage phenomena, we begin with a simple example. Suppose that you are a nervous investor who buys stock in a company at a price of $100. Suppose also that this price fluctuates daily in a random multiplicative fashion. That is, at the end of each day the stock price changes by a multiplicative factor f < 1 or by f−1 compared with the previous day's price, with each possibility occurring with probability 1/2 (Fig. 1.1). The multiplicative change ensures that the price remains positive. To be concrete, let's take f = 90% and suppose that there is a loss on the first day so that the stock price drops to $90.

First Passage in Real Systems

The first-passage properties of the finite and the semi-infinite interval are relevant to understanding the kinetics of a surprisingly wide variety of physical systems. In many such examples, the key to solving the kinetics is to recognize the existence of such an underlying first-passage process. Once this connection is established, it is often quite simple to obtain the dynamical properties of the system in terms of well-known first-passage properties

This chapter begins with the presentation of several illustrations in this spirit. Our first example concerns the dynamics of integrate-and-fire neurons. This is an extensively investigated problem and a representative sample of past work includes that of Gerstein and Mandelbrot (1964), Fienberg (1974), Tuckwell (1989), Bulsara, Lowen, & Rees (1994), and Bulsara et al. (1996). In many of these models, the firing of neurons is closely related to first passage in the semi-infinite interval. Hence many of the results from the previous chapter can be applied immediately. Then a selection of self-organized critical models [Bak, Tang, & Wiesenfeld (1987) and Bak (1996)] in which the dynamics is driven by extremal events is presented. These include the Bak–Sneppen (BS) model for evolution [Bak & Sneppen (1993), Flyvbjerg, Sneppen, & Bak (1993), de Boer et al. (1994), and de Boer, Jackson, & Wetting (1995)] directed sandpile models [Dhar & Ramaswamy (1989)], traffic jam models [Nagel & Paczuski (1995)], and models for surface evolution [Maslov & Zhang (1995)]. All of these systems turn out to be controlled by an underlying first-passage process in one dimension that leads to the ubiquitous appearance of the exponent −3/2 in the description of avalanche dynamics.

When the lattice gas was introduced in statistical physics around 1985 (see Frisch, Hasslacher and Pomeau, 1986), it was originally constructed as a physical model for hydrodynamics. In fact, the concept of the lattice gas is as much a physical concept – and we shall indeed start with intuitive physical ideas – as it is a mathematical concept, as a more formal definition can also be given. We first present the point of view of the physicist (Section 1.1), then we describe the lattice gas automaton from the mathematical viewpoint (Section 1.2), and in Section 1.3 we discuss the two aspects.

The physicist's point of view

A lattice gas can be viewed as a simple, fully discrete microscopic model of a fluid, where fictitious particles reside on a finite region of a regular Bravais lattice. These fictitious particles move at regular time intervals from node to node, and can be scattered by local collisions according to a node-independent rule that may be deterministic or non-deterministic. Thus, time, space coordinates and velocities are discrete at the microscopic scale, that is, at the scale of particles, lattice nodes and lattice links.

The stationary states in statistical equilibrium and thus the large-scale dynamics of a lattice gas will crucially depend on its conservation properties, that is, on the quantities preserved by the microscopic evolution rule of the system.

In Chapter 2, we established the equations governing the microscopic dynamics of the lattice gas. This microscopic dynamics provides the basics of the procedure for constructing automata simulating the behavior of fluid systems (see Chapter 10). However, in order to use LGAs as a method for the analysis of physical phenomena, we must go to a level of description which makes contact with macroscopic physics. Starting from a microscopic formalism, we adopt the statistical mechanical approach.

We begin with a Liouville (statistical) description to establish the lattice Liouville equation which describes the automaton evolution in terms of configuration probability in phase space. We then define ensemble-averaged quantities and, in particular, the average population per channel whose space and time evolution is governed by the lattice Boltzmann equation (LBE), when we neglect pre-collision correlations as well as post-collision re-correlations (Boltzmann ansatz). The LBE will be seen to play in LGAs the same crucial role as the Boltzmann equation in continuous fluid theory; an H-theorem follows from which the existence of a Gibbsian equilibrium distribution is established when the semi-detailed balance is satisfied.

The Liouville description

In Chapter 2 we introduced the notion of Boolean field ni(r*, t*) to obtain a complete microscopic description of the time-evolution of lattice gases. We also introduced the phase space Γ which is the set of all possible Boolean configurations of the whole lattice.

In Chapter 4, we gave a statistical mechanical analysis of lattice gases, and discussed the equilibrium properties; we described uniform uncorrelated statistical equilibria, and we showed that they have a Fermi–Dirac probability distribution. The existence of these uniform equilibrium solutions can be established without recourse to the Boltzmann approximation; the only required conditions are the semi-detailed balance and the existence of local invariants. These equilibrium solutions – the analogue of global equilibria in usual statistical mechanics – are uniform by construction: the macroscopic variables, i.e. the ensemble-averages of the local invariants, are space-and time-independent.

Now, we address the problem of space-and time-varying macrostates in the ‘hydrodynamic limit’, that is, macrostates for which macroscopic variables vary over space and time scales much larger than the characteristic microscopic scales (lattice spacing and time-step duration). This scale separation between microscopic and macroscopic variables is a crucial physical ingredient in the theory of lattice gas hydrodynamic equations, and it is at the core of the forthcoming derivation, which rests upon a discrete version of the well-known ‘Chapman–Enskog method’ (see Chapman and Cowling, 1970).

Although the principles of the method described hereafter apply to a wider class of models, we are led, at a certain point of the forthcoming algebraic procedure, to particularize our study to the (still wide) class of ‘single-species thermal models’ defined in Chapter 4, Section 4.5.2. The simpler case of nonthermal models is also treated, but in a less detailed manner (see Section 5.7).