Steven R. Dunbar
Department of Mathematics
203 Avery Hall
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Stochastic Processes and

__________________________________________________________________________

Intuitive Introduction to Diﬀusions

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________

Section Starter Question

Suppose you wanted to display the function $y=\sqrt{x}$ with a computer plotting program or a graphing calculator. Describe the process to choose a proper window to display the graph.

_______________________________________________________________________________________________

Key Concepts

1. This section introduces the passage from discrete random walks to continuous time stochastic processes from the probability point of view and the partial diﬀerential equation point of view.
2. To get a sensible passage from discrete random walks to a continuous time stochastic process the step size must be inversely proportional to the square root of the stepping rate.

__________________________________________________________________________

Vocabulary

1. A diﬀusion process, or a diﬀusion for short, is a Markov process for which all sample functions are continuous.

__________________________________________________________________________

Mathematical Ideas

Visualizing Limits of Random Walks

The question is “How should we set up the limiting process so that we can make a continuous time limit of the discrete time random walk?” First we consider a discovery approach to this question by asking what do we require so that we can visualize the limiting process. Next we take a probabilistic view using the Central Limit Theorem to justify the limiting process to pass from a discrete probability distribution to a probability density function. Finally, we consider the limiting process to a diﬀerential equation derived from the diﬀerence equation that is the result of ﬁrst-step analysis.

The Random Walk

Consider a random walk starting at the origin. The $n$th step takes the walker to the position ${T}_{n}={Y}_{1}+\cdots +{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=1-p$ respectively. Then recall that the mean of a sum of random variables is the sum of the means:

$𝔼\left[{T}_{n}\right]=\left(p-q\right)n$

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

$Var\left[{T}_{n}\right]=4pqn.$

Trying to use the mean to derive the limit

Now suppose we want to display a video of the random walk moving left and right along the $x$-axis. This would be a video of the “phase line” diagram of the random walk.

Suppose we want the video to display 1 million steps and be a reasonable length of time, say 1000 seconds, between 16 and 17 minutes. This ﬁxes the time scale at a rate of one step per millisecond. What should be the window in the screen to get a good sense of the random walk? For this question, we use a ﬁxed unit of measurement, say centimeters, for the width of the screen and the individual steps. Let $\delta$ be the length of the steps. To ﬁnd the window to display the random walk on the axis, we then need to know the size of $\delta \cdot {T}_{n}$. Now

$𝔼\left[\delta \cdot {T}_{n}\right]=\delta \cdot \left(p-q\right)n$

and

$Var\left[\delta \cdot {T}_{n}\right]={\delta }^{2}\cdot 4pqn.$

We want $n$ to be large (about 1 million) and to see the walk on the screen we want the expected end place to be comparable to the screen size, say 30 cm. That is,

so $\delta$ must be to get the end point on the screen. But then the movement of the walk measured by the standard deviation

will be so small as to be indistinguishable. We will not see any random variations!

Trying to use the variance to derive the limit

Let us turn the question around: We want to see the variations in many-step random walks, so the standard deviations must be a reasonable fraction $D$ of the screen size

For $n=1{0}^{6}$ this is possible if We still want to be able to see the expected ending position which will be

To be consistent with the requirement that the ending position is on the screen this will only be possible if $\left(p-q\right)\approx 1{0}^{-3}$. That is, $p-q$ must be at most comparable in magnitude to $\delta =3×1{0}^{-2}$.

The limiting process

Now generalize these results to visualize longer and longer walks in a ﬁxed amount of time. Since $\delta \to 0$ as $n\to \infty$, then likewise $\left(p-q\right)\to 0$, while $p+q=1$, so $p\to 1∕2$. The analytic formulation of the problem is as follows. Let $\delta$ be the size of the individual steps, let $r$ be the number of steps per unit time. We ask what happens to the random walk in the limit where $\delta \to 0$, $r\to \infty$, and $p\to 1∕2$ in such a manner that:

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

and

$4pq\cdot {\delta }^{2}\cdot r\to D.$

Each of these says that we should consider symmetric ($p=1∕2=q$) random walks with step size inversely proportional to the square root of the stepping rate.

The limiting process taking the discrete time random walk to a continuous time process is delicate. It is delicate because we are attempting to scale in two variables, the step size or space variable and the stepping rate or time variable, simultaneously. The variables are not independent, two relationships connect them, one for the expected value and one for the variance. Therefore we expect that the scaling is only possible when the step size and stepping rate have a special relationship, namely the step size inversely proportional to the square root of the stepping rate.

Probabilistic Solution of the Limit Question

In our accelerated random walk, consider the $n$th step at time $t=n∕r$ and consider the position on the line $x=k\cdot \delta$. Let

${v}_{k,n}=ℙ\left[\delta \cdot {T}_{n}=k\delta \right]$

be the probability that the $n$th step is at position $k$. We are interested in the probability of ﬁnding the walk 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$ with the additional conditions that $\left(p-q\right)\cdot \delta \cdot r\to c$ and $4pq\cdot {\delta }^{2}\cdot r\to D$.

Remember 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 in all cases $n+k$ is even and $\left(n+k\right)∕2$ is an integer. Likewise $n-k$ is even and $\left(n-k\right)∕2$ is an integer. We reach position $k$ at time step $n$ if the walker takes $\left(n+k\right)∕2$ steps to the right and $\left(n-k\right)∕2$ steps to the left. The mix of steps to the right and the left can be in any order. So the walk $\delta \cdot {T}_{n}$ reaches position $k\delta$ at step $n=rt$ with binomial probability

${v}_{k,n}=\left(\genfrac{}{}{0.0pt}{}{n}{\left(n+k\right)∕2}\right){p}^{\left(n+k\right)∕2}{q}^{\left(n-k\right)∕2}.$

From the Central Limit Theorem

$\begin{array}{llll}\hfill ℙ\left[\delta \cdot {T}_{n}=k\cdot \delta \right]& =ℙ\left[\left(k-1\right)\cdot \delta <\delta \cdot {T}_{n}<\left(k+1\right)\cdot \delta \right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =ℙ\left[\frac{\left(k-1\right)\delta -\left(p-q\right)\delta n}{\sqrt{4pq{\delta }^{2}n}}<\frac{\delta {T}_{n}-\left(p-q\right)\delta n}{\sqrt{4pq{\delta }^{2}n}}<\frac{\left(k+1\right)\delta -\left(p-q\right)\delta n}{\sqrt{4pq{\delta }^{2}n}}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \approx {\int }_{\frac{\left(k-1\right)\delta -\left(p-q\right)\delta n}{\sqrt{4pq{\delta }^{2}n}}}^{\frac{\left(k+1\right)\delta -\left(p-q\right)\delta n}{\sqrt{4pq{\delta }^{2}n}}}\frac{1}{\sqrt{2\pi }}{e}^{-{u}^{2}∕2}\phantom{\rule{0.3em}{0ex}}du\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={\int }_{\left(k-1\right)\delta }^{\left(k+1\right)\delta }\frac{1}{\sqrt{2\pi \cdot 4pq{\delta }^{2}n}}{e}^{-{\left(z-\left(p-q\right)\delta n\right)}^{2}∕\left(2\cdot 4pq{\delta }^{2}n\right)}\phantom{\rule{0.3em}{0ex}}dz\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \approx \frac{2\delta }{\sqrt{2\pi \cdot 4pq{\delta }^{2}n}}{e}^{-{\left(k\delta -\left(p-q\right)\delta n\right)}^{2}∕\left(2\cdot 4pq{\delta }^{2}n\right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \approx \frac{2\delta }{\sqrt{2\pi \cdot 4pq{\delta }^{2}rt}}{e}^{-{\left(k\delta -\left(p-q\right)\delta rt\right)}^{2}∕\left(2\cdot 4pq{\delta }^{2}rt\right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{2\delta }{\sqrt{2\pi Dt}}{e}^{-{\left(x-ct\right)}^{2}∕\left(2\cdot Dt\right)}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Similarly

$ℙ\left[a\cdot \delta <\delta \cdot {T}_{n}\cdot \delta

The integral on the right may be expressed in terms of the standard normal cumulative distribution function.

Note that we derived the limiting approximation of the binomial distribution

${v}_{k,n}\sim \left(\frac{2\delta }{\sqrt{2\pi Dt}}\right)exp\left(\frac{-{\left(x-ct\right)}^{2}}{2Dt}\right)$

by applying the general form of the Central Limit Theorem. However, it is possible to derive this limit directly through careful analysis. The direct derivation is the de Moivre-Laplace Limit Theorem and it is the most basic form of the Central Limit Theorem.

Diﬀerential Equation Solution of the Limit Question

Another method is to start from the diﬀerence equations governing the random walk, and then pass to a diﬀerential equation in the limit. Later we can generalize the diﬀerential equation and ﬁnd that the generalized equations govern new continuous-time stochastic processes. Since diﬀerential equations have a well-developed theory and many tools to manipulate, transform and solve them, this method turns out to be useful.

Consider the position of the walker in the random walk at the $n$th and $\left(n+1\right)$st trial. Through a ﬁrst step analysis the probabilities ${v}_{k,n}$ satisfy the diﬀerence equations:

${v}_{k,n+1}=p\cdot {v}_{k-1,n}+q\cdot {v}_{k+1,n}.$

In the limit as $k\to \infty$ and $n\to \infty$, ${v}_{k,n}$ will be the sampling of the function $v\left(t,x\right)$ at time intervals $r$, so that $n=rt$, and space intervals so that $k\delta =x$. That is, the function $v\left(t,x\right)$ should be an approximate solution of the diﬀerence equation:

$v\left(t+{r}^{-1},x\right)=pv\left(t,x-\delta \right)+qv\left(t,x+\delta \right).$

We assume $v\left(t,x\right)$ is a smooth function so that we can expand $v\left(t,x\right)$ in a Taylor series at any point. Using the ﬁrst 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\left(t,x\right)$ )

$\frac{\partial v\left(t,x\right)}{\partial t}=\left(q-p\right)\cdot \delta r\frac{\partial v\left(t,x\right)}{\partial x}+\frac{1}{2}{\delta }^{2}r\frac{{\partial }^{2}v\left(t,x\right)}{\partial {x}^{2}}.$

In our passage to limit, the omitted terms of higher order tend to zero, so we neglect them. The remaining coeﬃcients are already accounted for in our limits and so the equation becomes:

$\frac{\partial v\left(t,x\right)}{\partial t}=-c\frac{\partial v\left(t,x\right)}{\partial x}+\frac{1}{2}D\frac{{\partial }^{2}v\left(t,x\right)}{\partial {x}^{2}}.$

This is a special diﬀusion equation, more speciﬁcally, a diﬀusion equation with convective or drift terms, also known as the Fokker-Planck equation for diﬀusion. It is a standard problem to solve the diﬀerential equation for $v\left(t,x\right)$ and therefore, we can ﬁnd the probability of being at a certain position at a certain time. One can verify that

$v\left(t,x\right)=\frac{1}{\sqrt{2\pi Dt}}exp\left(\frac{-{\left[x-ct\right]}^{2}}{2Dt}\right)$

is a solution of the diﬀusion equation, so we reach the same probability distribution for $v\left(t,x\right)$.

The diﬀusion equation can be immediately generalized by permitting the coeﬃcients $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 diﬀusions.

Sources

This section is adapted from W. Feller, in Introduction to Probability Theory and Applications, Volume I, Chapter XIV, page 354.

_______________________________________________________________________________________________

Problems to Work for Understanding

1. Consider a random walk with a step to right having probability $p$ and a step to the left having probability $q$. The step length is $\delta$. The walk is taking $r$ steps per minute. What is the rate of change of the expected ﬁnal position and the rate of change of the variance? What must we require on the quantities $p$, $q$, $r$ and $\delta$ in order to see the entire random walk with more and more steps at a ﬁxed size in a ﬁxed amount of time?
2. Verify the limit taking to show that
${v}_{k,n}\sim \frac{1}{\sqrt{2\pi Dt}}exp\left(\frac{-{\left[x-ct\right]}^{2}}{2Dt}\right).$

3. Show that
$v\left(t,x\right)=\frac{1}{\sqrt{2\pi Dt}}exp\left(\frac{-{\left[x-ct\right]}^{2}}{2Dt}\right)$

is a solution of

$\frac{\partial v\left(t,x\right)}{\partial t}=-c\frac{\partial v\left(t,x\right)}{\partial x}+\frac{1}{2}D\frac{{\partial }^{2}v\left(t,x\right)}{\partial {x}^{2}}$

by substitution.

__________________________________________________________________________

References

[1]   William Feller. An Introduction to Probability Theory and Its Applications, Volume I, volume I. John Wiley and Sons, third edition, 1973. QA 273 F3712.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

1. Brownian Motion in Biology.. A simulation of a random walk of a sugar molecule in a cell.
2. Virtual Laboratories in Probability and Statistics.. Search the page for Random Walk Experiment.

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.