[an error occurred while processing this directive] [an error occurred while processing this directive]
[Note this!]

Key Concepts:

The passage from discrete random walks to continuous stochastic processes, from the probability point of view and the partial differential equation point of view.


Lesson

Vocabulary:

  1. A diffusion process, or a diffusion for short, is a Markov process for which all sample functions are continuous. (From Karlin and Taylor, page 30.) Also, a solution to a stochastic differential equation. (From Baxter and Rennie, page 61.)
[Big Ideas!]

Mathematical Ideas

Limits of Random Walks

The following discussion is taken from W. Feller, in Introduction to Probability Theory and Applications, Volume I, Chapter XIV, page 354. Consider a random walk starting at the origin. The n-th step takes the particle to the position S_n = X_1 + ... + X_n, the sum of n independent, identically distributed Bernoulli random variables X_i assuming the values +1, and -1 with probabilities p and q respectively. Then recall that the mean of a sum of random variables is the sum of the means:

E(S_n) = (p-q)*n

and the variance of a sum of independent random variables is the sum of the variances:

Var(S_n) = 4*p*q*n

Now suppose we want to display a motion picture of the random walk moving left and right along the x-axis. We want the motion picture to display 1 million steps and be a reasonable length of time, say 1000 seconds, between 16 and 17 minutes. This fixes the time scale at a rate of one step per millisecond. What should be the spatial scale in order to get a good sense of the random walk? For this question, we use a fixed unit of measurement, say centimeters, for the length of the screen and the individual steps. We are then concerned with \delta*S_n, where \delta stands for the length of the steps. Now

E(\delta*S_n) = (p-q)*\delta*n

and

Var(\delta*S_n) = 4*p*q*\delta^2*n.

We want n to be large (like 1 million) and we want \delta*n to be comparable to the screen size, (say 30cm), so \delta will be small (3*10^{-5}cm = .0003 mm!). But then \delta^2*n = \delta*(\delta*n) will be so small as to be indistinguishable (9*10^{-4} cm) We will not see the random variations! We want to be able to see the drift induced by the difference (p-q), and to be consistent with the variance requirement this will only be possible if (p-q) is comparable in size to \delta. Since \delta \to 0, then likewise (p-q) \to 0, while p+q = 1, so p \to 1/2.

The analytical formulation of the problem is as follows. To every choice: let \delta be the size of the individual steps, let r be the number of steps per unit time. We ask what happens in the limit where \delta \to 0, r \to \infinity, and p \to 1/2 in such a manner that:

(p-q)*\delta*r \to c

and

4*p*q*\delta^2*r \to D.


Probabilistic Solution of the Limit Question

When we are in possession of an explicit expression for the relevant probabilities, we can pass to the limit directly. The method is of limited scope however, since it does not easily lend itself to generalizations. Furthermore, the limit manipulations on the explicit expression get more and more complicated. Let

v_{k,n} = Pr[ S_n = k ]

be the probability that the n-th step is at position k. In our accelerated random walk, the n-th step takes place at time t = n/r and the position is at x = k*\delta. We are interested in the probability of finding the particle at given instant t and in the neighborhood of a given point x, so we investigate the limit of v_{k,n} as n/r \to t,and k*\delta \to x.

Now think about it for a few minutes and you will see that the random walk can only reach an even-numbered position after an even number of steps, and an odd-numbered position after an odd number of steps. Therefore, (n+k)/2 is an integer and we reach position number k at timestep n if the particle takes (n+k)/2 steps to the right. which happens with probability

v_{k,n} = \choose(n, (n+k)/2 )*p^{(n+k)/2}*q^{(n-k)/2}

From the DeMoivre-Laplace limit theorem (more about this in the next section)

v_{k,n} \asympt (1/(sqrt{2*\pi*p*q})* exp( -[(n+k)/2 - n*p]^2/(2*\pi*n*p*q) )
= (1/(sqrt{2*\pi*p*q})* exp( -[k - n*(p-q)]^2/(8*\pi*n*p*q) )
\asympt ( (2*\delta)/(sqrt{2*\pi*D*t})* exp( -[x-c*t]^2/(2*D*t) )

Since v_{k,n} is the probability of finding S_n*\delta between k*\delta and (k+2)*\delta, and since this interval has length 2*\delta we can say that the ratio v_{k,n}/(2\delta) measures locally the probability per unit length, that is the probability density. The last relation above implies that the ratio v_{k,n}/n tends to

v(t,x) = ( (2*\delta)/(sqrt{2*\pi*D*t})* exp( -[x-c*t]^2/(2*D*t) )

It follows by the definition of integration as the sums of quantities representing densities times geometric lengths or areas, that sums of probabilities v_{k,n} can be approximated by integrals and the result may be restated to the effect that

Pr[ a < S_N*\delta < b ] \to (1/(\sqrt{2*\pi*D*t})*\int(exp( -(x-ct)^2/(Dt)), x = a..b)

The integral on the right may be expressed in terms of the standard normal distribution function and in fact is only a notational variant of the DeMoivre-Laplace limit theorem for the binomial distribution.

Differential Equation Solution of the Limit Question

Another fruitful method is to start from the difference equations governing the differential equations, and then pass to the differential equation in the limit. We can then obviously generalize the differential equations, and find out that the differential equations govern well-defined stochastic processes depending on continuous time. Since differential equations have a powerful theory and many available tools to manipulate, transform and solve them, this method turns out to be more useful in the long-run. Consider the position of the particle in the random walk at the nth and (n+1)st trial, it is obvious that the probabilities v_{k,n} satisfy the difference equations:

v_{k,n+1} = p*v_{k-1, n} + q*v_{k+1,n}

Now in the limit as k \to \infinity and n \to \infinity, v_{k,n} will be the sampling of the function v(t,n) at time intervals r, so that k*r = t, and space intervals so that n*\delta = x. That is the function v(t,x) should be an approximate solution of the difference equation:

v( t + r^{-1}, x ) = p*v(t, x - \delta) + q*v(t,x + \delta)

We assume v(t,x) is a smooth function so that we can expand v(t,x) in a Taylor series at any point. Using the first order approximation in the time variable on the left, and the second-order approximation on the right in the space variable, we get (after canceling the leading terms v(t,x) )

\partial v(t,x)/\partial t =
(q-p)*\delta*r*\partial v(t,x)/\partial x +
(1/2)*\delta^2*r*\partial^2 v(t,x)/\partial x^2

In our passage to the limit, the omitted terms of higher order tend to zero, so may be neglected. The remaining coefficients are already accounted for in our limits and so the equation becomes:

\partial v(t,x)/\partial t =
-c*\partial v(t,x)/\partial x +
(1/2)*D*\partial^2 v(t,x)/\partial x^2

This is a special diffusion equation, more specifically, a diffusion equation with convective or drift terms, also known as the Fokker-Planck equation for diffusion. It is a relatively standard problem to solve the differential equation for v(t,x) and therefore, we can find the probability of being at a certain position at a certain time, relatively easily. The diffusion equation can be immediately generalized by permitting the coefficients c and D to depend on x, and t. Furthermore, the equation possesses obvious analogues in higher dimensions and all these generalization can be derived from general probabilistic postulates. We will ultimately describe stochastic processes related to these equations as diffusions.
One can verify that

v(t,x) = ( 1/(sqrt{2*\pi*D*t})* exp( -[x-c*t]^2/(2*D*t) )

is a solution of the diffusion equation, so we reach the same probability distribution for v(t,x).

Illustration 1


Reading Suggestion:

  1. Introduction to Probability Theory and Applications, Volume I, by W. Feller, Chapter XIV, page 354, J Wiley and Sons, New York

Problems to Work for Understanding

Outside Readings/Links:


[an error occurred while processing this directive] [an error occurred while processing this directive]

Last modified: [an error occurred while processing this directive]