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 <x},   - oo < x s£ oo
A discrete-parameter random process {Xk,k = 0,1,2,...,»} may be characterized by the joint distribution function of all the random variables involved,
F(x0,Xi,..., x„) = Pt{X0 < x0,X1 < Xj,...,X„ < x„}, xke{-oo, oc),     k= 1,2,...,n,
Definitions and classifications 125
Deaths 4r
3 2
1 h
(o)
Vehicles
(c)
Rainfall 4
3
21-
1 -
—        0 2
(b)
Temperature 40
30 20 10
(d)
6     k —
t —
Figure 7.1 Sketches of representative sample paths for the various kinds of random processes.
and by the joint distributions of all distinct subsets of {Xk}. Similar, but more complicated descriptions apply to continuous time random processes. The probabilistic structure of some processes, however, enables them to be characterized much more simply. One important such class of processes is called Markov processes.
Markov processes
Definition Let A' = {Xk,k = 0,1,2,...} be a random process with a discrete index set and a discrete state space 5= {s1,s2»s3»»" }■ If
= Pr{^ = SJX._i=Vi}
(7.1)
for any n ^ 1 and any collection of sk.eS, j = 0,1,... n, then A" is called a Markov process.
126    Simple random walks
Equation (7.1) states that the values of X at all times prior to n — 1 have no effect whatsoever on the conditional probability distribution of Xn given X„-v Thus a Markov process has memory of its past values, but only to a limited extent.
The collection of quantities
for various n,St and , is called the set of one-time-step transition probabilities. It will be seen later (Section 8.4) that these provide a complete description of the Markov process, for with them the joint distribution function of (X„, Xn-l,...,Xl,X0),or any subset thereof, can be found for any n. Furthermore, one only has to know the initial value of the process (in conjunction with its transition probabilities) to determine the probabilities that it will take on its various possible values at all future times. This situation may be compared with initial-value problems in differential equations, except that here probabilities are determined by the initial conditions.
All the random processes we will study in the remainder of this book are Markov processes. In the present chapter we study simple random walks which are Markov processes in discrete time and with a discrete state space. Such processes are examples of Markov chains which will be discussed more generally in the next chapter.
One note concerning terminology. We often talk of the value of a process at time t, say, which really refers to the value of a single random variable (X(t)), even though a process is a collection several random variables.
7.2 UNRESTRICTED SIMPLE RANDOM WALK
Suppose a particle is initially at the point x = 0 on the x-axis. At each subsequent time unit it moves a unit distance to the right, with probability p, or a unit distance to the left, with probability q, where p + q = 1.
At time unit n let the position of the particle be X„. The above assumptions yield
X0 = 0,     with probability one,
and in general,
*n = ^»-i+zn> 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„ = *!*,,_!=/}=<( <f, iffc=;-l
L 0, otherwise
and in this case these do not depend on n.
Mean and variance
We first observe that
Xl — X0 + Zj
X 2 = X {-\- Z2 — Xq-\-Z^-\-Z2
xn = x0 + z1 + z2 + - + zn.
Then, because the Z„ are identically distributed and independent random variables and X0 = 0 with probability one,
E(X„) = E^tiZ^ = nE(zJ
Var(X„) = Var^f Z^ = » Var^).
E(Z1)=lp + (-\)q = p-q
E{Z\)=\p+\q = p + q=L
Var(Z1) = £(Z?)-£2(Z1)
= l-(p-q? = l-(p2 + q2-2pq) = l-(p2+q2 + 2pq) + 4pq = 4pq,
and
Now, and
Thus
Unrestricted simple random walk 129
since p2 + q2 + 2pq = (p + q)2 = 1. Hence we arrive at the following expressions for the mean and variance of the process at epoch n:
(7.2)
(7.3)
E(Xn) = n(p-q) Var(Xa) = 4npq
We see that the mean and variance grow linearly with time.
The probability distribution of x„
Let us derive an expression for the probability distribution of the random variable x„, the value of the process (or x-coordinate of the particle) at time O 1- That is, we seek
p(M) = Pr =
where k is an integer.
We first note that p(k, n) = Oif n < \k\ because the process cannot get to level k in less than \k\ steps. Henceforth, therefore, n> \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-<i) i
N(0,l).
Thus for example,
Pr {n{p -q)-<Xn< n(p -q)+ 1.96v/4«pq} =s 0.95.
Pdf
100
Figure 7J Mean of the random walk versus n for p = 0.5 and p = 0.8 and normal density approximations for the probability distributions of the process at epochs n = 50 and n = 100.
Random walk with absorbing states 131 After n = 10000 steps with p = 0.6, E(Xn) = 2000 an
Pr {1808 < X10000 < 2192} ^0.95,
whereas when p = 0.5 the mean is 0 and
Pr {- 196 <X10000< 196}* 0.95.
Figure 7.3 shows the growth of the mean with increasing n and the approximating normal densities at n = 50 and n = 100 for various p.
7.3 RANDOM WALK WITH ABSORBING STATES
The paths of the process considered in the previous section increase or decrease at random, indefinitely. In many important applications this is not the case as particular values have special significance. This is illustrated in the following classical example.
A simple gambling game
Let two gamblers, A and B, initially have Sa and $b, respectively, where a and b are positive integers. Suppose that at each round of their game, player A wins $1 from B with probability p and loses $1 to B with probability q = 1 — p. The total capital of the two players at all times is
c = a + b.
Let Xn be player X's capital at round n where n = 0,1,2,... and X0 = a. Let Z„ be the amount A wins on trial n. The Z„ are assumed to be independent. It is clear that as long as both players have money left,
X„ — -Xn-i + Z„, «=1,2,...,
where the Z„ are i.i.d. as in the previous section. Thus {Xn, n = 0,1,2,...} is a simple random walk but there are now some restrictions or boundary conditions on the values it takes.
Absorbing states
Let us assume that A and B play until one of them has no money left; i.e., has 'gone broke'. This may occur in two ways. A's capital may reach zero or A's capital may reach c, in which case B has gone broke. The process X = {X0,Xl,X2,...} is thus restricted to the set of integers {0,1,2,..., c} and it terminates when either the value 0 or c is attained. The values 0 and c are called absorbing states, or we say there are absorbing barriers at 0 and c. Figure 7.4 shows plots of A's capital Xn versus trial number for two possible