Random Walks

3.1 The Simple Random Walk

A random walk is a sequence of random variables X0, X1, X2, . . . such that the successive differences Jn = Xn-Xn-1 form a sequence of independent, identically distributed random variables.

If the distribution of the Jn takes the form

P(Jn = +1) = p, P(Jn = -1) = q = 1-p,
then the process X is called a simple random walk.

Three random walks
The blue process is a simple symmetric random walk (p=q=½)
The magenta process is a SRW with downward drift (q=2p).
The red process is a SRW with downward drift (q=2p), with a reflecting barrier at 0.

In this instance the same sequence of pseudo-random numbers has been used to generate all three processes: observe that the two walks with downward drift make identical transitions, except when the red one is at zero.

3 random walks

Example: binomial lattice model for share prices

Notice that this structure implies that Xn-X0 is a sum of i.i.d. random variables, so that we can apply a number of general results. Among these is the Central Limit Theorem:

(Xn-X0) - n(p-q)

Ö(4npq)
® N(0,1).

as n®¥. We can use this to show that, if p > q, then

P(Xn < 0 | X0 = 0) ® 0

and that a similar result holds when p < q.

If p = q = ½ we have a simple symmetric random walk. The CLT tells us nothing useful in this case.

The Weak Law of Large Numbers states that, as n ® ¥

P(-c < Xn - X0

n
- (p - q) < c) ® 1

for any c>0. In the case of the SSRW this tells us no more than the Central Limit Theorem. We still know nothing about the path taken by the random walk, only about where it might be at a specific time n.

(The Strong Law of Large Numbers gives additional information, stating that the sequence {(Xn - X0)/n} is convergent with probability 1.)

3.2 Hitting Probabilities

The CLT only deals in general tendencies.
Consider hk = P(X ever hits 0 | X0=k), where k > 0. We can obtain an equation for hk in terms of hk+1 and hk-1 by looking at the first step: for k > 1,

hk = p hk+1 + q hk-1

(Careful with k=1.)

Difference equation theory gives the solution, hk = A + B(q/p)k, for some A and B. Imposing a barrier at k=K, a very large number, gives a solution for A and B, which can be extended to the case k=¥.

3.3 Barriers

An absorbing barrier for a random walk is a value c such that, if Xn=c for some n0, then Xn=c for all n>n0. In other words, if the random walk hits the barrier it becomes stuck there.

An upwards reflecting barrier is a value c such that, if Xn=c, then Xn+1=c+1. (Downwards similarly.)

A random walk with two absorbing barriers is certain to hit one or other of them in the end. If there is one absorbing barrier and one reflecting one, the random walk will always get to the absorbing barrier.

3.4 Modelling with Random Walks

Many models are based on the simple random walk. Random walks may be used for minor elements of complex models. The process of fitting and testing a random walk model is the same in all cases.

Assume, then, that we have a sequence of observations x1, …, xn.

Transformation

First decide whether the raw process needs a transformation. A standard method is to investigate whether the increment xn+1 - xn depends on xn.
A plot should do. A typical transformation is the log-transform.

Discretisation

Next decide if you want to use a discrete state-space model.
If so, the data will need to be adjusted to a grid, by rounding off every observation to the nearest multiple of the mesh size, d.

Fitting a model

Let y1, …, yn be the observations after possible transformation and discretisation, and define jm = ym - ym-1.

Under a random walk model these should all be i.i.d., so we can plot histograms to choose a distribution (unless already specified), then use standard parameter estimation procedures.

Testing the model

Test to ensure that the distribution, with estimated parameter values, fits the increment data (goodness of fit test).

Run a few simulations to see whether they look like the real thing.

3.5 Simulating Random Walks

Once we can simulate a sequence of i.i.d. variables from the required distribution, it is easy to simulate the random walk. See the first lab session.


Previous Index Next
This page is maintained by Russell Gerrard: R.J.Gerrard@city.ac.uk