Discrete-Time Random Walk

In the following section we restrict ourselves to one-dimensional models for expository purposes. The material is presented by means of examples of random walk models and corresponding mesoscopic equations and is sometimes supported by general theory. 

We begin with a simple example of a particle performing a discrete-time random walk (DTRW) in one dimension. Assume that it is initially at point 0. The random walk can be defined by the stochastic difference equation for the particle position 

Equation (3.8) provides a microscopic description of the particle transport. After n 

It follows from (3.8) and (3.9) that the PDF p x, n) obeys the Kolmogorov forward equation 

3 Random Walks and Mesoscopic Reaction-Transport Equations 

---

The MC method considers the configuration space of a model and generates a discrete-time random walk through configuration space following a master equation41,51... 

An ancient but still instructive example is the discrete-time random walk. A drunkard moves along a line by making each second a step to the right or to the left with equal probability. Thus his possible positions are the integers — oo < n < oo, and one asks for the probability pn(r) for him to be at n after r steps, starting from n = 0. While we shall treat this example in IV.5 as a stochastic process, we shall here regard it as a problem of adding variables. 

Exercise. In the discrete-time random walk the steps were taken at fixed time points. Suppose now that the times of the steps are randomly distributed as given by the Poisson process. Show that this is identical to the situation described by (2.1). )... 

Thus the mean square of the distance covered between 0 and t grows proportionally with t, just as in the discrete-time random walk. How could this have been shown a priori (without explicitly solving the M-equation) ... 

Chapter 8 by W. T. Coffey, Y. P. Kalmykov, and S. V. Titov, entitled Fractional Rotational Diffusion and Anomalous Dielectric Relaxation in Dipole Systems, provides an introduction to the theory of fractional rotational Brownian motion and microscopic models for dielectric relaxation in disordered systems. The authors indicate how anomalous relaxation has its origins in anomalous diffusion and that a physical explanation of anomalous diffusion may be given via the continuous time random walk model. It is demonstrated how this model may be used to justify the fractional diffusion equation. In particular, the Debye theory of dielectric relaxation of an assembly of polar molecules is reformulated using a fractional noninertial Fokker-Planck equation for the purpose of extending that theory to explain anomalous dielectric relaxation. Thus, the authors show how the Debye rotational diffusion model of dielectric relaxation of polar molecules (which may be described in microscopic fashion as the diffusion limit of a discrete time random walk on the surface of the unit sphere) may be extended via the continuous-time random walk to yield the empirical Cole-Cole, Cole-Davidson, and Havriliak-Negami equations of anomalous dielectric relaxation from a microscopic model based on a... 

T. L. Hill. Discrete-time random walks on diagrams (graphs) with cycles. Proc. Natl. Acad. Sci. USA, 85 5345-5349, 1988. 

Thus the Debye equation [Eq. (1)] may be satisfactorily explained in terms of the thermal fluctuations of an assembly of dipoles embedded in a heat bath giving rise to rotational Brownian motion described by the Fokker-Planck or Langevin equations. The advantage of a formulation in terms of the Brownian motion is that the kinetic equations of that theory may be used to extend the Debye calculation to more complicated situations [8] involving the inertial effects of the molecules and interactions between the molecules. Moreover, the microscopic mechanisms underlying the Debye behavior may be clearly understood in terms of the diffusion limit of a discrete time random walk on the surface of the unit sphere. 

As far as the physical mechanism underlying the Cole-Cole equation is concerned, we first remark that Eq. (9) arises from the diffusion limit of a continuous-time random walk (CTRW) [17] (see Section II.A). In this context one should recall that the Einstein theory of the Brownian motion relies on the diffusion limit of a discrete time random walk. Here the random walker makes a jump of a fixed mean-square length in a fixed time, so that the only random... 

This concept which is based on a random walk with a well-defined characteristic waiting time (thus called a discrete-time random walk) and which applies when collisions are frequent but weak leads to the Smoluchowski equation for the evolution of the concentration of Brownian particles in configuration space. If inertial effects are included (see Note 8 of Ref. 2, due to Fiirth), we obtain the Klein-Kramers equation for the evolution of the distribution function in phase space which describes normal diffusion. The random walk considered by Einstein [2] is a walk in which the elementary steps are taken at uniform intervals in time and so is called a discrete time random walk. The concept of collisions which are frequent but weak can be clarified by remarking that in the discrete time random walk, the problem [5] is always to find the probability that the system will be in a state m at some time t given that it was in a state n at some earlier time. 

Consider the discrete-time random walk model for the particle position... 

In a previous section reference was made to the random walk problem (Montroll and Schlesinger [1984], Weiss and Rubin [1983]) and its application to diffusion in solids. Implicit in these methods are the assnmptions that particles hop with a fixed jump distance (for example between neighboring sites on a lattice) and, less obviously, that jumps take place at fixed equal intervals of time (discrete time random walks). In addition, the processes are Markovian, that is the particles are without memory the probability of a given jump is independent of the previous history of the particle. These assumptions force normal or Gaussian diffusion. Thus, the diffusion coefficient and conductivity are independent of time. 

In the previous paragraphs it was pointed out that a discrete time random walk, or a CTRW with a finite hrst moment for the waiting time distribution, on a lattice with a fixed jump distance led to a Gaussian diffusion process with a probability density given by Eq. (84). The spatial Fourier transform of this equation is... 

---