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

Stochastic Processes and
Advanced Mathematical Finance

__________________________________________________________________________

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

Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

Suppose you know the graph y = f(x) of the function f(x). What is the effect on the graph of the transformation f(ax) where a > 1? What is the effect on the graph of the transformation (1b)f(x) where b > 1? What about the transformation f(ax)b where a > 1 and b > 1 ?

_______________________________________________________________________________________________

Key Concepts

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

Vocabulary

  1. We define approximate Brownian Motion ŴN(t) to be the rescaled random walk with steps of size 1N taken every 1N time units where N is a large integer.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Approximation of Brownian Motion by Fortunes

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

Y i = +1 with probability 1/21 with probability 1/2

be a sequence of independent, identically distributed Bernoulli random variables. Note that Var Y i = 1, which we will need to use in a moment. Let Y 0 = 0 for convenience and let

Tn = i=0nY i

be the sequence of sums which represent the successive net fortunes of our notorious gambler. Sketch the random fortune Tn versus time using linear interpolation between the points (n 1,Tn1) and (n,Tn) to obtain a continuous, piecewise linear function. The interpolation defines a function Ŵ(t) defined on [0,) with Ŵ(n) = Tn. This function is piecewise linear with segments of length 2. The notation Ŵ(t) 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(t) = 1 NŴ(Nt).

This has the effect of taking a step of size ±1N in 1N time unit. For example,

ŴN(1N) = 1 NŴ(N 1N) = T1 N = Y 1 N.

Now consider

ŴN(1) = Ŵ(N 1) N = Ŵ(N) N = TN N.

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

ŴN(t) = Ŵ(Nt) N = tŴ(Nt) Nt

If Nt is an integer, ŴN(t) is normally distributed with mean 0 and variance t. Furthermore, ŴN(0) = 0 and ŴN(t) is a continuous function, and so is continuous at 0. At times tj = jN, tk = kN, t = N, and tm = mN with tj < tk t < tm (so j < k < m) the function differences ŴN(tk) ŴN(tj) and ŴN(tm) ŴN(t) are the differences (Tk Tj)N and (Tm T)N, hence independent.

Altogether, this should be a strong suggestion that ŴN(t) is an approximation to Standard Brownian Motion. We will define the very jagged piecewise linear function ŴN(t) as approximate Brownian Motion.

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

  1. ŴN(t) < x W(t) < xas N .

  2. More generally, the limit of the rescaled random walk defining approximate Brownian Motion is Brownian Motion in the following sense: ŴN(t1) < x1,ŴN(t2) < x2,ŴN(tn) < xn W(t1) < x1,W(t2) < x2,W(tn) < xn (1)

    as N where t1 < t2 < < tn. That is, the joint distributions of ŴN(t) converges to the joint normal distribution

    f(x1,t1; x2,t2; ; xn,tn) = p(x1,t)p(x2 x1,t2 t1)p(xn xn1,tn tn1)(2)

    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 defined 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-flip 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 L2[0,T] 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 [3]. For the representation as a limit of Bernstein polynomials, see Introduction to Bernstein Polynomials and Brownian Motion. or [4]. 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 efficiency 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 benefits 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

Algorithms, Scripts, Simulations

Algorithm

Simulate a sample path of the Wiener process as follows, see [3]. Divide the interval [0,T] into a grid of N + 1 nodes 0 = t0 < t1 < < tN1 < tN = T with ti+1 ti = Δ. 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 T0,T1,T2,TN of N + 1 steps with T0 = 0. Given a value x [0,T] the prior node with tk x is xΔ for 0-based arrays (or xΔ + 1 for 1-based arrays.). The subsequent node with x tk+1 is xΔ for 0-based arrays (or xΔ + 1 for 1-based arrays.). Then define the value of the approximation function ŴN(x) by linear interpolation between the values of the random walk at Tk and Tk+1.

A feature of this N + 1-step random walk scaling approximation algorithm is that it creates the approximation as a function on [0,T]. This function can then be plotted with a function plotting routine on any time grid on the interval [0,T]. If the time grid used for plotting on [0,T] 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 [0,T] is greater than N points, then the plotted function will just represent the linear interpolation between the random-walk points at tj = jTN and no new information is represented.

Depending on the internal plotting routines used by the language, plotting the approximation function ŴN(t) 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 fixed 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 efficient ways to create and plot the N + 1 coordinate pairs (jTN,TNSj) defining 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 first 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

GeoGebra.

R

R script for approximation.

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

Octave script for approximation.

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

Perl PDL script for approximation.

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

Scientific Python script for approximation.

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

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 flip, also keep track of the accumulated sum Tn = i=1nT i for i = 125 representing the net fortune at any time. Plot the resulting Tn versus n on the interval [0, 25]. Finally, using N = 5, plot the rescaled approximation Ŵ5(t) = (15)T(5t) on the interval [0, 5] on the same graph.
    1. What are the slopes of the linear segments of ŴN(t) ?
    2. Is the slope necessarily undefined at the nodes defining ŴN(t) ?
    3. Explain how a plotting routine could create a horizontal segment in the plot of ŴN(t).
  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 effect on the sample paths. Change p to a value less than 0.5 and describe the effect on the sample paths.
    3. Plot the approximation functions for increasing values of N and describe the effects on the sample paths.
    4. For a fixed, 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 effects 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 [3] uses a different random walk step function approximation to Brownian Motion:
    W̄N(t) = TNt 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(t) converges to the joint normal distribution is true, show then that
    TNt N < x W(t) < x.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   Leo Breiman. Probability. SIAM, 1992.

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

[3]   Stefano M. Iacus. Simulation and Inference for Stochastic Differential Equations. Number XVIII in Springer Series in Statistics. Springer-Verlag, 2008.

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

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

__________________________________________________________________________

Links

Outside Readings and Links:

__________________________________________________________________________

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 effort 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 reflects the thoughts, interests and opinions of its author. They do not explicitly represent official 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 modified: Processed from LATEX source on July 28, 2016