We are almost ready to fully exploit the connection, established in earlier chapters, between the statistics of a self-avoiding random walk and the statistical mechanics of a magnet near the phase transition from its paramagnetic and ferromagnetic states. Because of the mathematical similarity between the two systems, we will be able to make use of an array of calculational strategies that, collectively, represent realizations of the renormalization group. This generic method for the study of systems with long-range correlations has fundamentally altered the way in which physicists view the world around them. The method is so powerful and so widespread in its application, that it seems worthwhile to do a little more than simply explain how to use it in the present context. This chapter consists of a discussion of the philosophy underlying the renormalization group and of a general description of the way in which it is applied. We will finish off by taking the reader through a simple calculation that is relevant to random walks and the associated magnetic system. Then, we will generalize the method to encompass a wide class of systems, the O(n) model being one of them. In the next chaper, the reader will be subjected to a full-blown introduction to the method, as it applies to the self-avoiding walk. Those already familiar with the renormalization group may wish to skip directly to Chapter 12.

Scale invariance in mathematics and nature

The notion of scale invariance is not exactly new. A famous poem by Jonathan Swift goes as follows:

The notion and quantification of shape

Shape is an intuitively accessible notion. We organize visual information in terms of shapes, and the shape of an object represents one of the first of its qualities referred to in an informal descriptive rendering of it. While our language presents us with a wide repertoire of verbal images for the approximate portrayal of the shape of a physical entity (“round,” “oblong,” “crescent,” “stellate” …) the precise characterization of a shape, in terms of a number, or set of numbers, has remained elusive. This is with good reason. It is well-known to mathematicians that the class consisting of the set of all curves is a higher order of infinity than the set of all real numbers. This means that there can be no one-to-one correspondence between curves and real numbers. As shapes, intuitively at least, bear a conceptual relationship to curves, it is plausible that the set of all shapes dwarfs in magnitude the set of real numbers, or of finite sets of real numbers.

On the other hand, if one is willing to content oneself with a general paradigm for the measurement of shape, there are ways of quantifying it in terms of numbers that have a certain descriptive and predictive utility. In fact, the numerical specification of shapes has acquired a certain urgency of late, in light of the widespread use of computer imaging and the concomitant focus on the development of codes for the creation and manipulation of pictorial quantities.

In this chapter, we will look at different ways of characterizing and measuring the shape of a random walk.

The concept of a field dates back to Euler, who introduced the notion to describe fluid flows in his study of hydrodynamics. Methods and concepts based on field theory now pervade the physical sciences and engineering. Field-theoretical ideas exert a strong influence on physical intuition and shape modern nomenclature. In addition, some of the most powerful analytical tools available to the modern scientist are those developed to study the behavior of fields.

In the context of models designed to describe the physical world, a field is a quantity that varies continuously in space and time. Examples are the electric and magnetic fields, the velocity and density distributions of a liquid or vapor and the quantum-mechanical wavefunction of a microscopic particle. In some cases, such as the velocity and density fields introduced by Euler, the notion of continuity must be taken advisedly. Because of the atomic structure of matter, one cannot carry the notion of a smooth density distribution down to the length scales on which molecules can be distinguished. There, the classical description is necessarily in terms of particles. Quantum mechanically, wavefunctions replace the classical density and velocity fields as the appropriate mode of description. This proviso notwithstanding, in the regimes in which density and velocity fields accurately describe the state of a liquid or vapor, they form the basis of an extremely useful theoretical model that yields important physical properties of these systems.

It turns out that the random walk also lends itself to description in terms of a field. As in the case of a liquid or vapor, the field-based description maintains its validity in a restricted range of length scales.

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 Internet is the result of the bold effort of a group of people in the 1960s, who foresaw the great potential of a computer-based communication system to share scientific and research information. While in the early times it was not a user-friendly environment and was only used by a restricted community of computer experts and scientists, nowadays the Internet connects more than one hundred million hosts and keeps growing at a pace unknown in any other communication media. From this perspective, the Internet can be considered as one of the most representative accomplishments of sustained investment in research at both the basic and applied science levels.

The success of the Internet is due to its world-wide broadcasting capability that allows the interaction between individuals without regard for geographic location and distance. The information exchanged between computers is divided into data packets and sent to special devices, called routers, that transfer the packets across the Internet's different networks. Of course a router is not linked to every other router. It just decides on the direction the data packets take. In order to work reliably on a global scale, such a network of networks must be very slightly affected by local or even extensive failures in the network's nodes. This means that if a site is not working properly or it is too slow, data packets can be rerouted, on the spot, somewhere else.

At the large-scale level, the modeling of the Internet focuses on the construction of graphs that reproduce the topological properties observed in the AS and IR level maps. Representing the Internet as a graph implies ignoring the physical features of routers and connections (capacity, bandwidth, etc.), in a effort to gain a more simplified perspective that is still able to reproduce the empirical observations. From this perspective, Internet modeling initially relied on the traditional framework where complex networks with no apparent regularities were described as static random graphs, such as the model of Erdös and Rényi (1959). The graph model of Erdös–Rényi is the simplest conceivable one, characterized by an absolute lack of knowledge of the principles that guide the creation of connections between elements. Lacking any information, the simplest assumption one can make is to connect pairs of vertices at random with a given connection probability p.

Based on the random graph model paradigm, the computer science community has developed models of the Internet to test new communication protocols. The basic idea underlying the use of models to test protocols is that these should be independent (at least in principle) from the network topology. However, it turns out that their performance can be very sensitive to topological details (Tangmunarunkit et al., 2002a; Labovitz, Ahuja, Wattenhofer, and Srinivasan, 2001; Park and Lee, 2001). The use of an inadequate model can lead to the design of protocols that run very efficiently on the model, but perform quite poorly on the real Internet.