next_inactive up previous


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.)

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 $ T_n = Y_1 + \dots + Y_n$, the sum of n independent, identically distributed Bernoulli random variables $ Y_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:

$\displaystyle E(T_n) = (p-q) n
$

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

$\displaystyle Var(T_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 T_n$, where $ \delta$ stands for the length of the steps. Now

$\displaystyle E(\delta \cdot T_n) = (p-q) \cdot \delta \cdot n
$

and

$\displaystyle Var(\delta \cdot T_n) = 4 \cdot p \cdot q \cdot \delta^2 \cdot n.
$

We want $ n$ to be large (about 1 million) and we want $ \delta \cdot n$ to be comparable to the screen size, (say 30cm), so $ \delta$ will be small $ (3 \cdot 10^{-5}$cm$ = 0.0003$   mm!). But then $ \delta^2 \cdot n
= \delta \cdot (\delta \cdot n)$ will be so small as to be indistinguishable $ (9 \cdot 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:

$\displaystyle (p-q) \cdot \delta \cdot r \to c
$

and

$\displaystyle 4 \cdot p \cdot q \cdot \delta^2 \cdot 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

$\displaystyle v_{k,n} = Pr[ T_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 \cdot \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 \cdot \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. This happens with probability

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

From the Central Limit Theorem

$\displaystyle v_{k,n} \asympt (1/(sqrt{2 \cdot \pi \cdot p \cdot q})) \cdot
\e...
...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 $ T_n \cdot \delta$ between $ k \cdot \delta$ and $ (k+2) \cdot \delta$, and since this interval has length $ 2 \cdot \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

$\displaystyle v(t,x) = ( (2 \cdot \delta)/(sqrt{2 \cdot \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

$\displaystyle Pr[ a < S_N \delta < b ] \to
(1/(\sqrt{2 \pi D t})) \int_a^b \exp( -(x-ct)^2/(Dt))
$

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 Central 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 random walk, 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 useful in the long-run. Consider the position of the particle in the random walk at the $ n$th and $ (n+1)$-st trial, thorugh a first step analysis it is obvious that the probabilities $ v_{k,n}$ satisfy the difference equations:

$\displaystyle v_{k,n+1} = p \cdot v_{k-1, n} + q \cdot 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,x)$ at time intervals $ r$, so that $ k r = t$, and space intervals so that $ n \cdot \delta = x$. That is the function $ v(t,x)$ should be an approximate solution of the difference equation:

$\displaystyle 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)$ )

$\displaystyle \frac{\partial v(t,x)}{\partial t} =
(q-p) \cdot \delta r \frac{\...
... v(t,x)}{\partial x} +
(1/2) \delta^2 r \frac{\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:

$\displaystyle \frac{\partial v(t,x)}{\partial t} =
-c \frac{\partial v(t,x)}{\partial x} +
(1/2) D \frac{\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

$\displaystyle 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</em>, by W. Feller, Chapter XIV, page 354, J Wiley and Sons, New York

Problems to Work for Understanding

Outside Readings/Links:

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html intro_diffusion.tex

The translation was initiated by Steven Dunbar on 2007-10-24


next_inactive up previous
Steven R. Dunbar
Department of Mathematics and Statistics
University of Nebraska-Lincoln
Lincoln, NE, 68588-0323 USA
email: sdunbar@math.unl.edu
Steve Dunbar's Home Page