Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
Stochastic Processes and
Advanced Mathematical Finance
Approximation of Brownian Motion by Coin-Flipping Sums
Mathematically Mature: may contain mathematics beyond calculus with proofs.
Suppose you know the graph of the function . What is the eﬀect on the graph of the transformation where ? What is the eﬀect on the graph of the transformation where ? What about the transformation where and ?
As we have now assumed many times, for let
be a sequence of independent, identically distributed Bernoulli random variables. Note that , which we will need to use in a moment. Let for convenience and let
be the sequence of sums which represent the successive net fortunes of our notorious gambler. Sketch the random fortune versus time using linear interpolation between the points and to obtain a continuous, piecewise linear function. The interpolation deﬁnes a function deﬁned on with . This function is piecewise linear with segments of length . The notation reminds us of the piecewise linear nature of the function.
We will compress time, and rescale the space in a special way. Let be a large integer, and consider the rescaled function
This has the eﬀect of taking a step of size in time unit. For example,
According to the Central Limit Theorem, this quantity is approximately normally distributed, with mean zero, and variance 1. More generally,
If is an integer, is normally distributed with mean and variance . Furthermore, and is a continuous function, and so is continuous at . At times , , , and with (so ) the function diﬀerences and are the diﬀerences and , hence independent.
Altogether, this should be a strong suggestion that is an approximation to Standard Brownian Motion. We will deﬁne the very jagged piecewise linear function as approximate Brownian Motion.
as where . That is, the joint distributions of converges to the joint normal distribution
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 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.
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.
Simulate a sample path of the Wiener process as follows, see . Divide the interval into a grid of nodes with . The nodes may be indexed from either to or from to depending on the language. Create a Bernoulli random walk of steps with . Given a value the prior node with is for -based arrays (or for -based arrays.). The subsequent node with is for -based arrays (or for -based arrays.). Then deﬁne the value of the approximation function by linear interpolation between the values of the random walk at and .
A feature of this -step random walk scaling approximation algorithm is that it creates the approximation as a function on . This function can then be plotted with a function plotting routine on any time grid on the interval . If the time grid used for plotting on has less than points, then some of the information in the -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 is greater than points, then the plotted function will just represent the linear interpolation between the random-walk points at and no new information is represented.
Depending on the internal plotting routines used by the language, plotting the approximation function 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 coordinate pairs 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.
R script for approximation.
Create scripts that plot this random walk approximation for , and .
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.
Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1
Email to Steve Dunbar, sdunbar1 at unl dot edu
Last modiﬁed: Processed from LATEX source on July 28, 2016