Lecture 1 Notes: Introduction to Random Walks and Diffusion

Lecture 1: Introduction to Random Walks and Diffusion History The term “random walk” was originally proposed by Karl Pearson in 19051 . In a letter to Na­ ture, he gave a simple model to describe a mosquito infestation in a forest. At each time step, a single mosquito moves a fixed length a, at a randomly chosen angle. Pearson wanted to know the distribution of the mosquitos after many steps had been taken. The letter was answered by Lord Rayleigh, who had already solved a more general form of this problem in 1880, in the context of sound waves in heterogeneous materials. Modeling a sound wave traveling through the material can be thought of as summing up a sequence of random wave­ vectors k of constant amplitude but random phase: sound waves in the material have roughly constant wavelength, but their directions are altered at scattering sites within the material. We wish to find the probability density function of the sound waves after many steps have been taken. We let PN (R)dR be the probability of traveling a distance between R and R + dR in N steps. For steps of unit length, Lord Rayleigh showed that as N → ∞, PN (R) ∼ 2R −R2 /N e . N (1) This function is shown in figure 1 for several values of N . We � see � that the expected distance traveled 2 scales according to the square root of the number of steps, R ∼ N , which is typical of “diffusion” phenomena. Around the same time, the theory of random walks was also developed by Louis Bachelier in his truly remarkable doctoral thesis, La Th´eorie de la Sp´eculation, published in 1900. Bachelier proposed the random walk as the fundamental model for financial time series (e.g. stock ticks), many decades before this idea became the basis for modern theoretical finance. Bachelier also was apparently the first to see the connection between discrete random walks and the continuous diffusion (or heat) equation, which is a major theme of this class, reflected in its title. It is curious that in the same year as Pearson’s letter, Albert Einstein also published his seminal paper on Brownian motion – the complicated path of a large dust particle in air – which he modeled as a random walk, driven by collisions with gas molecules. Einstein did not seem to be aware of the related work of Rayleigh and Bachelier, and he focused on a different issue: the calculation of the diffusion coefficient in terms of the viscosity and temperature of the gas (which we will study later in the class). Similar theoretical ideas were also published independently by Smoluchowski 1 See B. Hughes, Random Walks and Random Environments, Vol. I, Sec. 2.1 (Oxford, 1995), for excerpts and an entertaining historical discussion. 1 2 0.3 N = 10 N = 30 N = 50 N = 100 0.25 PN (r) 0.2 0.15 0.1 0.05 0 0 2 4 6 8 10 12 14 16 r Figure 1: Rayleigh’s asymptotic approximation for PN (r) in Pearson’s random walk for several large values of N . in 1906. The random­walk theory of Brownian motion had an enormous impact, because it gave strong evidence for discrete particles (“atoms”) at a time when most scientists still believed that matter was a continuum. As its historical origins demonstrate, the concept of the random walk has incredibly broad applicability, and today, a century later, it is nearly ubiquitous in science and engineering. Simple Analysis of Isotropic Random Walks Computer simulations of Pearson’s random walk, as in Fig. 3, demonstrate that Lord Rayleigh’s result rather accurate in describing the distribution of walkers at long times, roughly beyond 100 steps. It is impressive how the complicated collection of random walkers tends toward a simple, smooth distribution, at least in the central region. We now present a simple derivation of a generalization of Lord Rayleigh’s result, which will be covered again in more detail in subsequent lectures. Consider a random walker, who initially starts at the origin in d dimensions. At each step, the walker moves by an amount ΔXN , chosen from a probability distribution pN (r). For this derivation, which shall consider the case of independent, identically distributed (IID) steps, so that pN (r) = p(r). Furthermore, we shall assume that the steps are isotropic, so that p(r) is a function of the radial distance r = |r| only. This condition also automatically eliminates any drift, so that �ΔXN � = 0. Let XN be the position of the walker after N steps, and let PN (R) be the associated probability density function (PDF). For IID displacements, we have the following recursion for the PDF: � PN +1 (R) = p(r)PN (R − r) dd r. (2) In one dimension (d = 1), this is Bachelier’s Equation. The key assumption is the independence of the steps, which allows the probability of a transition from R − r to R in the N th step to be factored into the two terms in the integrand. 3 2.5 Frequency density 1 y 0.5 0 ­0.5 ­1 ­1 ­0.5 0 0.5 2 1.5 1 0.5 0 1 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 x R Figure 2: The positions of 2000 independent Pearson random walks released from the ori­ gin, after N = 2000 steps of length a = 0.01. Figure 3: A normalized histogram of the dis­ tances from the origin, RN , in Fig. 2 compared to Rayleigh’s asymptotic result, Eq. (1). Starting from Eq. (2), we can formally take the continuum limit to quickly arrive at Rayleigh’s solution (1) to Pearson’s problem. In subsequent lectures we will gain a better understanding of this approximation, but here we just give simple arguments. As N → ∞, PN (r) varies on length scales which are much larger than a typical r, and therefore we Taylor expand inside the integral to obtain � � � 1 PN +1 (R) = p(r) PN (R) − r · �PN (R) + r · ��PN · r + . . . dd r 2 2 � � 1 ∂ PN = PN (R) − 0 + �ri rj � + ... 2 ∂Ri ∂Rj i j �r · r� 2 � PN (R) + . . . . 2d We assume that steps are taken at intervals of Δt, and defining time by t = N Δt we obtain � 2� r PN +1 (R) − PN (R) = � 2 PN + . . . . Δt 2dΔt As N → ∞, the limiting distribution ρ(R, t), defined by PN (R) = ρ(R, N Δt), satisfies = PN (R) + ∂ρ = D�2 ρ ∂t � � where D = r2 /2dΔt, which is the diffusion equation. Since the walker starts from the origin, we have the initial condition ρ(R, 0) = δ(R). To solve this partial differential equation, we make use of the Fourier Transform, defined for this class to be � ρ̂(k, t) = e−ik·x ρ(x, t) dd x � 1 ρ(x, t) = eik·x ρ̂(k, t) dd k. (2π)d 4 Thus we obtain the ordinary differential equation ∂ρ̂ = −Dk 2 ρ̂ ∂t which has solution 2 2 ρ̂(k, t) = e−Dk t ρ(k, ˆ 0) = e−Dk t . Taking the inverse Fourier Transform gives ρ(R, t) = e−R 2 /4Dt (4πDt)d/2 . Thus in the corresponding discrete problem, as N → ∞, PN (R) ∼ e−dR 2 /2 �r2 �N (2π �r2 � N/d)d/2 . (3) This is the long time limit of PN (R) for an isotropic random walk in d dimensions. The PDF for the position tends to a Gaussian (or normal) distribution, whose width depends only on the variance of the individual � � displacements. Our derivation predicts the same asymptotic result for any PDF so long as r2 exists. For an isotropic walk, we can easily calculate the PDF of the distance R from the origin via PN (R) = Ad Rd−1 PN (R) where Ad is the surface area �of the � unit sphere in d dimensions (A1 = 1, A2 = 2π, A3 = 4π,...). For Pearson’s problem, we have r2 = a2 and d = 2, so Equation (3) gives the asymptotic result: 2 PN (R) ∼ PN (R) ∼ 2 e−R /a N πa2 N 2R −R2 /a2 N e a2 N which agrees with Lord Rayleigh’s solution, Eq. (1), for a = 1. More General Situations Normal Diffusion As our simple derivation suggests, the statistical properties of random walks tend toward universal distributions after large numbers of steps. In the case of the PDF for the final position, our result for isotropic random walks is a multi­dimensional generalization of the Central Limit Theorem (CLT) for� sums � of independent, identically distributed random variables. As long as a finite second moment r2 exists for the random displacements, the asymptotic form of PN (R) is given by Eq. (3). An important question, which we will address in the next lecture, is how quickly the asymptotic form is approached and for what values of R it is a good approximation. Note the “square­root scaling” of the width of the PDF, which grows like � R ∝ �r2 � N . 5 0.5 0.5 0.4 0.4 0.3 y y 0.3 0.2 0.2 0.1 0.1 0 0 ­0.1 ­0.5 ­0.4 ­0.3 ­0.2 ­0.1 0 0.1 ­0.1 x 0 0.1 0.2 0.3 0.4 0.5 x Figure 4: Two thousand steps of a random walk based on the Cauchy distribution. Figure 5: Two thousand steps of Pearson’s random walk, with a = 0.01. which is characteristic of spreading by “normal diffusion”. More generally, we will see that the variance of the position is given by Var(RN ) = N Var(�r). for independent, identically distributed random displacements. Anomalous Diffusion When the assumptions of the CLT break down, random walks can exhibit rather different behavior. For example, the limiting distribution for the position may not be Gaussian, and the scaling of its width, R ∝ Nν, is generally “anomalous” with ν �= 1/2. The second part of this class is devoted to various cases of anomalous diffusion. One way to violate the CLT with IID displacements is via “fat­tailed” probability distributions, which assign sufficient probability to very large steps that the variance is infinite. An example is PDF for a Cauchy random variable, p(x) = π(b2 b . + x2 ) Since the probability density function decays like x−2 as x → ∞, the variance is infinite. Figure 4 shows an example of a two dimensional, isotropic random walk, where the distances of the steps are chosen from a Cauchy distribution. We see that the walk mostly takes small steps, but occasionally makes very large jumps, comparable to the total displacement. This is rather different from the case of Pearson’s walk, shown in Figure 5, where the step size is constant and normal diffusion occurs. 6 Other ways to achieve anomalous diffusion include highly non­uniform step distributions, strong correlations between steps, and interactions between multiple random walkers. In such cases, the continuum limit is more subtle and leads to various generalizations of the diffusion equation.