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

__________________________________________________________________________

Approximation of Brownian Motion by Coin-Flipping Sums

_______________________________________________________________________

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 know the graph $y=f\left(x\right)$ of the function $f\left(x\right)$. What is the eﬀect on the graph of the transformation $f\left(ax\right)$ where $a>1$? What is the eﬀect on the graph of the transformation $\left(1∕b\right)f\left(x\right)$ where $b>1$? What about the transformation $f\left(ax\right)∕b$ where $a>1$ and $b>1$ ?

_______________________________________________________________________________________________ ### Key Concepts

1. A properly scaled “random fortune” process (i.e. random walk) approximates Brownian motion.
2. Brownian motion is the limit of “random fortune” discrete time processes (i.e. random walks), properly scaled. The study of Brownian motion is therefore an extension of the study of random fortunes.

__________________________________________________________________________ ### Vocabulary

1. We deﬁne approximate Brownian Motion ${Ŵ}_{N}\left(t\right)$ to be the rescaled random walk with steps of size $1∕\sqrt{N}$ taken every $1∕N$ time units where $N$ is a large integer.

__________________________________________________________________________ ### Mathematical Ideas

#### Approximation of Brownian Motion by Fortunes

As we have now assumed many times, for $i\ge 1$ let

be a sequence of independent, identically distributed Bernoulli random variables. Note that $Var\left[{Y}_{i}\right]=1$, which we will need to use in a moment. Let ${Y}_{0}=0$ for convenience and let

${T}_{n}=\sum _{i=0}^{n}{Y}_{i}$

be the sequence of sums which represent the successive net fortunes of our notorious gambler. Sketch the random fortune ${T}_{n}$ versus time using linear interpolation between the points $\left(n-1,{T}_{n-1}\right)$ and $\left(n,{T}_{n}\right)$ to obtain a continuous, piecewise linear function. The interpolation deﬁnes a function $Ŵ\left(t\right)$ deﬁned on $\left[0,\infty \right)$ with $Ŵ\left(n\right)={T}_{n}$. This function is piecewise linear with segments of length $\sqrt{2}$. The notation $Ŵ\left(t\right)$ reminds us of the piecewise linear nature of the function.

We will compress time, and rescale the space in a special way. Let $N$ be a large integer, and consider the rescaled function

${Ŵ}_{N}\left(t\right)=\left(\frac{1}{\sqrt{N}}\right)Ŵ\left(Nt\right).$

This has the eﬀect of taking a step of size $±1∕\sqrt{N}$ in $1∕N$ time unit. For example,

${Ŵ}_{N}\left(1∕N\right)=\left(\frac{1}{\sqrt{N}}\right)Ŵ\left(N\cdot 1∕N\right)=\frac{{T}_{1}}{\sqrt{N}}=\frac{{Y}_{1}}{\sqrt{N}}.$

Now consider

${Ŵ}_{N}\left(1\right)=\frac{Ŵ\left(N\cdot 1\right)}{\sqrt{N}}=\frac{Ŵ\left(N\right)}{\sqrt{N}}=\frac{{T}_{N}}{\sqrt{N}}.$

According to the Central Limit Theorem, this quantity is approximately normally distributed, with mean zero, and variance 1. More generally,

${Ŵ}_{N}\left(t\right)=\frac{Ŵ\left(Nt\right)}{\sqrt{N}}=\sqrt{t}\frac{Ŵ\left(Nt\right)}{\sqrt{Nt}}$

If $Nt$ is an integer, ${Ŵ}_{N}\left(t\right)$ is normally distributed with mean $0$ and variance $t$. Furthermore, ${Ŵ}_{N}\left(0\right)=0$ and ${Ŵ}_{N}\left(t\right)$ is a continuous function, and so is continuous at $0$. At times ${t}_{j}=j∕N$, ${t}_{k}=k∕N$, ${t}_{\ell }=\ell ∕N$, and ${t}_{m}=m∕N$ with ${t}_{j}<{t}_{k}\le {t}_{\ell }<{t}_{m}$ (so $j) the function diﬀerences ${Ŵ}_{N}\left({t}_{k}\right)-{Ŵ}_{N}\left({t}_{j}\right)$ and ${Ŵ}_{N}\left({t}_{m}\right)-{Ŵ}_{N}\left({t}_{\ell }\right)$ are the diﬀerences $\left({T}_{k}-{T}_{j}\right)∕\sqrt{N}$ and $\left({T}_{m}-{T}_{\ell }\right)∕\sqrt{N}$, hence independent.

Altogether, this should be a strong suggestion that ${Ŵ}_{N}\left(t\right)$ is an approximation to Standard Brownian Motion. We will deﬁne the very jagged piecewise linear function ${Ŵ}_{N}\left(t\right)$ as approximate Brownian Motion.

Theorem 1. The limit of the rescaled random walk deﬁning approximate Brownian Motion is Brownian Motion in the following sense:

1. More generally, the limit of the rescaled random walk deﬁning approximate Brownian Motion is Brownian Motion in the following sense:

as $N\to \infty$ where ${t}_{1}<{t}_{2}<\cdots <{t}_{n}$. That is, the joint distributions of ${Ŵ}_{N}\left(t\right)$ converges to the joint normal distribution

$\begin{array}{cc}& f\left({x}_{1},{t}_{1};{x}_{2},{t}_{2};\dots ;{x}_{n},{t}_{n}\right)=\\ & p\left({x}_{1},t\right)p\left({x}_{2}-{x}_{1},{t}_{2}-{t}_{1}\right)\dots p\left({x}_{n}-{x}_{n-1},{t}_{n}-{t}_{n-1}\right)& \text{(2)}\end{array}$

of the Standard Brownian Motion.

With some additional foundational work, a mathematical theorem establishes that the rescaled fortune processes actually converge to the mathematical object called the Standard Brownian Motion as deﬁned in the previous section. The proof of this mathematical theorem is beyond the scope of a text of this level, but the theorem above should strongly suggest how this can happen, and give some intuitive feel for the approximation of Brownian motion through the rescaled coin-ﬂip process.

Using a scaled random walk is not the only way to approximate Brownian Motion. Other approximations of the Wiener process use “global” approximations such as Fourier series (or more generally ${L}^{2}\left[0,T\right]$ expansions in an orthogonal basis) or Bernstein polynomials. The Fourier series representation is also known at the Karhunen-Loève expansion of the Wiener process, for elementary details, see . For the representation as a limit of Bernstein polynomials, see Introduction to Bernstein Polynomials and Brownian Motion. or . Both of these approximations use ideas from probability theory and analysis which are beyond the scope of this book. When one only needs to simulate the position of a sample path of Brownian Motion at one or even several time points, then the scaled random walk approximation is simple and the accuracy can be estimated with the Central Limit Theorem or the Berry-Esseen Theorem. If one needs information on a whole sample path of Brownian Motion, then the “global” methods are more appropriate approximations. The “global” methods are not only more mathematically sophisticated, they also are more expensive in terms of processing and rely on the eﬃciency of the underlying implementations of the mathematical functions used.

#### Sources

This section is adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Section 12.2, page 251. This section also beneﬁts from ideas in W. Feller, in Introduction to Probability Theory and Volume I, Chapter III and An Introduction to Stochastic Modeling 3rd Edition, H. M. Taylor, S. Karlin, Academic Press, 1998.

_______________________________________________________________________________________________ ### Algorithms, Scripts, Simulations

#### Algorithm

Simulate a sample path of the Wiener process as follows, see . Divide the interval $\left[0,T\right]$ into a grid of $N+1$ nodes $0={t}_{0}<{t}_{1}<\cdots <{t}_{N-1}<{t}_{N}=T$ with ${t}_{i+1}-{t}_{i}=\Delta$. The nodes may be indexed from either $0$ to $N$ or from $1$ to $N+1$ depending on the language. Create a Bernoulli random walk ${T}_{0},{T}_{1},{T}_{2},\dots {T}_{N}$ of $N+1$ steps with ${T}_{0}=0$. Given a value $x\in \left[0,T\right]$ the prior node with ${t}_{k}\le x$ is $⌊x∕\Delta ⌋$ for $0$-based arrays (or $⌊x∕\Delta ⌋+1$ for $1$-based arrays.). The subsequent node with $x\le {t}_{k+1}$ is $⌈x∕\Delta ⌉$ for $0$-based arrays (or $⌈x∕\Delta ⌉+1$ for $1$-based arrays.). Then deﬁne the value of the approximation function ${Ŵ}_{N}\left(x\right)$ by linear interpolation between the values of the random walk at ${T}_{k}$ and ${T}_{k+1}$.

A feature of this $N+1$-step random walk scaling approximation algorithm is that it creates the approximation as a function on $\left[0,T\right]$. This function can then be plotted with a function plotting routine on any time grid on the interval $\left[0,T\right]$. If the time grid used for plotting on $\left[0,T\right]$ has less than $N$ points, then some of the information in the $N$-step scaling approximation is ignored, and the plotted function will be less representative of the approximation than it could be. If the time grid on $\left[0,T\right]$ is greater than $N$ points, then the plotted function will just represent the linear interpolation between the random-walk points at ${t}_{j}=jT∕N$ and no new information is represented.

Depending on the internal plotting routines used by the language, plotting the approximation function ${Ŵ}_{N}\left(t\right)$ can result in plot artifacts. One simple artifact may be horizontal segments in the plot. If the plotting algorithms attempt to use adaptive point selection to densely position a greater portion of a ﬁxed number of plotting points in a region of rapid variation, then other regions will have fewer plotting points. Those regions with fewer plotting points will miss some of the information in that region. Depending on the language, the plotting routine may use smoothing or some other nonlinear interpolation between plotting points which will result in curved segments instead of a piecewise linear function. If the intention is to plot an approximate Brownian Motion, then there are more direct and eﬃcient ways to create and plot the $N+1$ coordinate pairs $\left(jT∕N,\sqrt{T∕N}{S}_{j}\right)$ deﬁning the vertices of the piecewise linear scaled random walk approximation with an appropriate amount of information. (This is approach taken in the Geogebra script, because the language does not support building a separate function as in the other languages.) Here the intention is to ﬁrst to demonstrate the creation of the approximation function as a piecewise linear function, then second to use the function to plot a graph.

#### Scripts

Geogebra
R
1p <- 0.5
2N <- 400
3
4T <- 1
5
6S <- array(0, c(N+1))
7rw <- cumsum( 2 * ( runif(N) <= p)-1 )
8S[2:(N+1)] <- rw
9
10WcaretN <- function(x) {
11    Delta <- T/N
12
13    # add 1 since arrays are 1-based
14    prior = floor(x/Delta) + 1
15    subsequent = ceiling(x/Delta) + 1
16
17    retval <- sqrt(Delta)*(S[prior] + ((x/Delta+1) - prior)*(S[subsequent] - S[prior]))
18}
19
20plot(WcaretN, 0,1, n=400)
21
22# # alternative plotting method
23# # time point grid
24# t <- seq(0,T, length=N+1)
25# # approximate Wiener process at time point grid
26# W <- sapply(t, WcaretN)
27# plot(t, W, type = "l")
Octave
1p = 0.5;
2
3global N = 400;
4global T = 1;
5
6global S
7S = zeros(N+1, 1);
8S(2:N+1) = cumsum( 2 * (rand(N,1)<=p) - 1);
9
10function retval = WcaretN(x)
11  global N;
12  global T;
13  global S;
14  Delta = T/N;
15
16  # add 1 since arrays are 1-based
17  prior = floor(x/Delta) + 1;
18  subsequent = ceil(x/Delta) + 1;
19
20  retval = sqrt(Delta)*(S(prior) + ((x/Delta+1) - prior).*(S(subsequent)-S(prior)));
21
22endfunction
23
24fplot(@WcaretN, [0,T])
25
26## alternative plotting method
27## time point grid; must be same orientation as S, i.e. column vector
28# t = transpose(0:T/N:T);
29# plot(t, WcaretN(t));
Perl
1use PDL::NiceSlice;
2
3$p = 0.5; 4 5$N = 400;
6$T = 1; 7 8# the random walk 9$S = zeros( $N + 1 ); 10$S ( 1 : $N ) .= cumusumover( 2 * ( random($N) <= $p ) - 1 ); 11 12# function WcaretN interpolating random walk 13sub WcaretN { 14 my$x = shift @_;
15    $Delta =$T / $N; 16 17$prior      = floor( $x /$Delta );
18    $subsequent = ceil($x / $Delta ); 19 20$retval =
21        sqrt($Delta) 22 * ($S ($prior) 23 + ( ($x / $Delta ) -$prior )
24            * ( $S ($subsequent) - $S ($prior) ) );
25}
26
27# file output to use with external plotting programming
28# such as gnuplot, R, octave, etc.
29# Start gnuplot, then from gnuplot prompt
30#   plot "wienerprocess.dat" with lines
31$M = 300; 32$tgrid = zeros( $M + 1 )->xlinvals( 0,$T );
33$W = WcaretN($tgrid);
34
35open( F, ">wienerprocess.dat" ) || die "cannot write: $! "; 36foreach$j ( 0 .. $M ) { 37 print F$tgrid->range( [$j] ), " ",$W->range( [\$j] ), "\n";
38}
39close(F);
SciPy
1import scipy
2
3p = 0.5
4
5N = 400
6T = 1.
7
8# the random walk
9S = scipy.zeros(N+1)
10S[1:N+1] = scipy.cumsum( 2*( scipy.random.random(N) <= p ) - 1 )
11
12def WcaretN(x):
13    Delta = T/N
14    prior = scipy.floor(x/Delta).astype(int)
15    subsequent = scipy.ceil(x/Delta).astype(int)
16    return scipy.sqrt(Delta)*(S[prior] + (x/Delta - prior)*(S[subsequent] - S[prior]))
17
18M = 300
19tgrid = scipy.linspace(0, T, M+1)
20W = WcaretN(tgrid)
21
22# optional file output to use with external plotting programming
23# such as gnuplot, R, octave, etc.
24# Start gnuplot, then from gnuplot prompt
25#    plot "wienerprocess.dat" with lines
26f = open(wienerprocess.dat, w)
27for j in range(0,M+1):
28    f.write( str(tgrid[j])+ +str(W[j])+\n);
29
30f.close()

__________________________________________________________________________ ### Problems to Work for Understanding

1. Flip a coin $25$ times, recording whether it comes up Heads or Tails each time. Scoring ${Y}_{i}=+1$ for each Heads and ${Y}_{i}=-1$ for each ﬂip, also keep track of the accumulated sum ${T}_{n}={\sum }_{i=1}^{n}{T}_{i}$ for $i=1\dots 25$ representing the net fortune at any time. Plot the resulting ${T}_{n}$ versus $n$ on the interval $\left[0,25\right]$. Finally, using $N=5$, plot the rescaled approximation ${Ŵ}_{5}\left(t\right)=\left(1∕\sqrt{5}\right)T\left(5t\right)$ on the interval $\left[0,5\right]$ on the same graph.
1. What are the slopes of the linear segments of ${Ŵ}_{N}\left(t\right)$ ?
2. Is the slope necessarily undeﬁned at the nodes deﬁning ${Ŵ}_{N}\left(t\right)$ ?
3. Explain how a plotting routine could create a horizontal segment in the plot of ${Ŵ}_{N}\left(t\right)$.
2. Modify one of the scripts in the following ways:
1. Plot more than one Wiener process sample path on the same set of axes.
2. Change $p$ to a value greater than $0.5$ and describe the eﬀect on the sample paths. Change $p$ to a value less than $0.5$ and describe the eﬀect on the sample paths.
3. Plot the approximation functions for increasing values of $N$ and describe the eﬀects on the sample paths.
4. For a ﬁxed, large value of $N$, plot the approximation at increasing values of the number of plotting points which are not divisors of $N$ and describe the eﬀects on the sample paths.
5. Change the value of $T$ and plot the resulting sample paths, both without increasing the value of $N$ and increasing the value of $N$ proportionally to $T$ and describe the resulting sample paths.
3. Iacus  uses a diﬀerent random walk step function approximation to Brownian Motion:
${\stackrel{̄}{W}}_{N}\left(t\right)=\frac{{T}_{⌊Nt⌋}}{\sqrt{N}}.$

Create scripts that plot this random walk approximation for $N=10$, $N=100$ and $N=1000$.

4. Under the assumption of the theorem that the joint distributions of ${Ŵ}_{N}\left(t\right)$ converges to the joint normal distribution is true, show then that
$ℙ\left[\frac{{T}_{⌊Nt⌋}}{\sqrt{N}}

__________________________________________________________________________ ### References

   Leo Breiman. Probability. SIAM, 1992.

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

   Stefano M. Iacus. Simulation and Inference for Stochastic Diﬀerential Equations. Number XVIII in Springer Series in Statistics. Springer-Verlag, 2008.

   Emmanuel Kowalski. Bernstein polynomials and brownian motion. American Mathematical Monthly, 113:865–886, December 2006.

   H. M. Taylor and Samuel Karlin. An Introduction to Stochastic Modeling. Academic Press, third edition, 1998.

__________________________________________________________________________ __________________________________________________________________________

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.