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, |
| 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. |
 |
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.)
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=¥.
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.
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.
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.
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.
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.
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.
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.
 |
 |
 |