1
Simple random walks
7.1 RANDOM PROCESSES-DEFINITIONS AND CLASSIFICATIONS
Definition of random process
Physically, the term random (or stochastic) process refers to any quantity that evolves randomly in time or space. It is usually a dynamic object of some kind which varies in an unpredictable fashion. This situation is to be contrasted with that in classical mechanics whereby objects remain on fixed paths which may be predicted exactly from certain basic principles.
Mathematically, a random process is defined as a collection of random variables. The various members of the family are distinguished by different values of a parameter, a, say. The entire set of values of a, which we shall denote by A, is called an index set or parameter set. A random process is then a collection such as
of random variables. The index set A may be discrete (finite or countabiy infinite) or continuous. The space in which the values of the random variables {Xs} lie is called the state space.
Usually there is some connection which unites, in some sense, the individual members of the process. Suppose a coin is tossed 3 times. Let Xk, with possible values 0 and 1, be the number of heads on the kih toss. Then the collection {Xl,X2,X3j fits our definition of random process but as such is of no more interest than its individual members since each of these random variables is independent of the others. If however we introduce Y1 = XUY2=X1 +X2, Y3 = Xl + X2 + XV so that Yk records the number of heads up to and including the klh toss, then the collection {Yk, ke{ 1,2,3}} is a random process which fits in with the physical concept outlined earlier. In this example the index set is A = (1,2,3} (we have used k rather than a for the index) and the state space is the set {0,1,2,3}.
The following two physical examples illustrate some of the possibilities for index sets and state spaces.
124 Simple random walks Examples
(i) Discrete time parameter
Let Xy be the amount of rainfall on day it with it=0,1.2,.... The collection of random variables X — {k = 0,1,2,...} is a random process in discrete time. Since the amount of rainfall can be any non-negative number, the Xk have a continuous range. Hence X is said to have a continuous state space.
(ii) Continuous time parameter
Let X(i) be the number of vehicles on a certain roadway at time t where t 0 is measured relative to some reference time. Then the collection of random variables X = {X(t), t ^ 0} is a random process in continuous time. Here the state space is discrete since the number of vehicles is a member of the discrete set {0,1,2,,.., iV} where N is the maximum number of vehicles that may be on the roadway.
Sample paths of a random process
The sequences of possible values of the family of random variables constituting a random process, taken in increasing order of time, say, are called sample paths (or trajectories or realizations). The various sample paths correspond to 'elementary outcomes' in the case of observations on a single random variable. It is often convenient to draw graphs of these and examples are shown in Fig. 7.1 for the cases:
(a) Discrete time-discrete state space, e.g., the number of deaths in a city due to automobile accidents on day k;
(b) Discrete time-continuous state space, e.g., the rainfall on day fe;
(c) Continuous time-discrete state space, e.g., the number of vehicles on the roadway at time t;
(d) Continuous time-continuous state space, e.g., the temperature at a given location at time t.
Probabilistic description of random processes
Any random variable, X, may be characterized by its distribution function
F(x) = Pr{X n=l,2,...,
*
where the ZN are identically distributed with
Pr{Z, = + l}=p Pr{Z1=~l}=^.
Unrestricted simple random walk 127
It is further assumed that the steps taken by the particle are mutually independent random variables.
Definition. The collection of random variables ,Y= {X0, Xu X2,...} is called a simple random walk in one dimension. It is 'simple' because the steps take only the values ± 1, in distinction to cases where, for example, the Z„ are continuous random variables.
The simple random walk is a random process indexed by a discrete time parameter {n = 0,1,2,...) and has a discrete state space because its possible values are {0, ± 1, ± 2,...}. Furthermore, because there are no bounds on the possible values of X, the random walk is said to be unrestricted.
Sample paths
Two possible beginnings of sequences of values of X are
{0, + 1, + 2, + 1,0, - 1,0, + 1, + 2, + 3,...} {0, -1,0, -1,-2,-3,-4,-3,-4,-5,...}
The corresponding sample paths are sketched in Fig. 7.2.
Figure 7.2 Two possible sample paths of the simple random walk.
128 Simple random walks Markov property
A simple random walk is clearly a Markov process. For example,
Pr {X4 - 2\X3 = 3, X2 = 2, Xl = 1, X0 =0}
= Pr{X4 = 2|X3 = 3} = Pr{Z4 = + 1}=9.
That is, the probability is q that A"4 has the value 2 given that AT3 = 3, regardless of the values of the process at epochs 0,1,2. The one-time-step transition probabilities are
'p, tfk=;+l pyt = Pr{X„ = *!*,,_!=/}=<( \k\.
Of the n steps let the number of magnitude + 1 be N* and the number of magnitude — 1 be N~, where /V„+ and N~ are random variables. We must have
x„ = n:-n;
and
Adding these two equations to eliminate N~ yields
Atf =*(» + *,). (7.4)
Thus x„ = k if and only if Ar„+ = |(k + k). We note that Ar„+ is a binomial random variable with parameters n and p. Also, since from (7.4), 2ArB+ = « + xn is necessarily even, x„ must be even if n is even and xn must be odd if n is odd. Thus we arrive at
*k'H)-{(k + n)/2)P q
n ^ \k\, k and n either both even or both odd. For example, the probability that the particle is at k = - 2 after n
p{-2A) = ^pq' = 4pq\
This will be verified graphically in Exercise 3.
= 4 steps is (7.5)
130 Simple random walks Approximate probability distribution
If Xo = 0, then
where the Zk are i.i.d. random variables with finite means and variances. Hence, by the central limit theorem (Section 6.4),
Xa-E{Xn) t
JV(0,1)
as n-> oo. Since E(Xn) and o(Xn) are known from (7.2) and (7.3), we have
xn-*ip-