as ?7-oo Show that Yn is a consistent estimator of 0 Chebyshev s inequality to find an upper bound for Fitly'
28. Prove that iiXn^X then XN-iz.
(#w: TJse
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 At is called an index set or parameter set. A random process is then a collection such as
{X,7iaeA}
of random variables. The index set A may be discrete (finite or countably infinite) or continuous. The space in which the values of the random variables {Xa} 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 fcth toss. Then the collection {XilX2>X3} 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 Yi=X1>Y2 = X1 +X2, Y3~Xx + X2 + X3, so that Yk records the number of heads up to and including the fcth toss, then the collection {Yk,ke{l, 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.
Examples
(i) Discrete time parameter
Let Xk be the amount of rainfall on day k with £=0,1,2,.... The collection of random variables X = {Xk, k = 0,1, %...} 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.
(it) Continuous time parameter
Let X(t) 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), i ^ 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,..., N] 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 k;
(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 L
Probabilistic description of random processes
Any random variable, X, may be characterized by its distribution function
F(x) = Pr{X< x}, -oo^x^oo
A discrete-parameter random process {Xk,k = Q, 1,2,...,??} may be characterized by the joint distribution function of all the random variables involved,
F(x0,xl5...,xn) = Pr{XQ ^x^X^x,,...,Xn<xn}, xfce(—oo, x),     k— 1,2,... ,n,
Definitions and classifications 125
Deaths
						
-1						
						
						
						
(a)
0
Vehicles
t
(c)
Rainfall 4 r
(b)
Temperature 40 r
30
20
10
(d)
Figure
processes
7.1 Sketches of representative sample paths for the various kinds of random
and by the joint distributions of all distinct subsets of {Xk}. Similar, but more compLted descriptions apply to continuous time random Processes. The probabilistic structure of some processes, h™™\ea^*™ characterized much more simply. One important such class of processes .s
called Markov processes.
Markov processes
Definition Let X~ 0,1,2,...} be a random process with a discrete
index set and a discrete state space S= {$i,s2^3> «
Pr {Xn - skn\Xtl_ j - V.*,X»-2 = *W• ■ •'Xí - Sfc" X° ~ho}
= Pr{Xn = %JlXtt_1=^.1]
(7.1)
for any « > I and any process.
collection of sk .eS, j = 0,1,...«, then Xis called a Markov
iou    uunpzt; iciiiaum wajKS
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„ . Thus a Markov process has memory of its past values, but only to a limited extent.
The collection of quantities
Pr{Xn = skJXn^ = skn J
for various n,skn and sk , 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 (Xn, Xn-ls..., Xy, 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 r, say, which really refers to the value of a single random variable {X(t)), even though a process is a collection of 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 Xn. The above assumptions yield
X0 m 0,     with probability one,
and in general,
Xn — Xn -1 ~v Zn,
where the Zn are identically distributed with
Pr{Z1 = +l} = p
Unrestricted simple random walK
It is further assumed that the steps taken by the particle are mutually independent random variables.
Definition. The collection of random variables X == {Xot Xr,X2,...} is called a simple random walk in one dimension. It is 'simple' because the steps take only the values ± I, 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, ± X,. .}• 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, + l,+2, + l,0,-l,0, + l,+2, + 3,...} (0,-1,0,-1,-2,-3,-4,-3,-4,-5,...}
The corresponding sample paths are sketched in Fig. 7.2.
x
n
0
t
I [
I
!
-5
L
I I
_i
I
\ I
1
I I
i
15
i i
i
i
i
i i
t i i
10
Figure 12 Two possible sample paths of the simple random walk.
Markov property
A simple random walk is clearly a Markov process. For example,
Pr {X4 = 2\X, = 3, X2 = 2, X, = 1, X0 = 0}
= Pr {X4 = 2|X3 - 3} = Pr (Z4 = + 1} = q.
That is, the probability is q that XA has the value 2 given that X3 regardless of the values of the process at epochs 0.1,2. The one-time-step transition probabilities are
''/;,      if k = j + 1
Pj* = Pr{*« = fc|*B-i=./} = |*
, 0, otherwise
and in this case these do not depend on n.
= 3,
Mean and variance
We first observe that
X2 = $f ^ + Z2 =? X0 +2^1+^2
p
Xn = X0 4- Z2 4- Z2 + - - • + Z„.
Then, because the Z„ are identically distributed and independent random variables and XQ = 0 with probability one,
£<X„) = £( £ Zk ) = nE(Zl)
and
Var (XJ = Var   £ Zk = KVar(ZL),
k= 1
Now.
and
Thus
EiZJ^lp + i-^q^p-q
E(Z2)^lp+lq = p + q = L
Var(Z1) = £(Zf)-£2(Z1)
= l-(p-<?)2
= l-(p2 + q2-2pq)
= \~(p2 + q2 + 2pq) + 4pq
= 4pq,
Unrestricted simple random walk 129
since p2 + </2 4- 2pq = (p 4 g)2 = 1. Hence we arrive at the following expressions for the mean and variance of the process at epoch n:
E(Xti) = nip - q) Var (Xnj = Anpq
v--1
We see that the mean and variance grow linearly with time.
(7.2)
(7.3)
The probability distribution of Ar„
Let us derive an expression for the probability distribution of the random variable Xn, the value of the process (or .Y-coordinate of the particle) at time n ^ 1. That is, we seek
p(hn) = Pr{Xt=k}>
where k is an integer.
We first note that p(k, n) = 0 if n < j 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     and N~ are random variables. We must have
and
X = 7V+ —N~
Adding these two equations to eliminate Nn yields
N:=Un + XJ. (7.4)
Thus Xn = k if and only if N£ =j{n + k). We note that is a binomial random variable with parameters n and p. Also, since from (7.4), 2AT* —n + Xn is necessarily even, Xn must be even if n is even and Xn must be odd if n is odd. Thus we arrive at
n^\k\, k and n either both even or both odd. For example, the probability that the particle is at k = - 2 after n = 4 steps is
p(-2,4) = [ ljpqi = Apq\ This will be verified graphically in Exercise '3.
(7.5)
Approximate probability distribution
If x0 = 0, then
k~ 1
where the Zk are i.i.d. random variables with finite means and variances, Hence, by the central limit theorem (Section 6.4),
X„ — E(Xn) a
N(0,1)
as n-± oc. Since E{X„) and a{Xti) are known from (7.2) and (7.3), we have
XH-n{p-q) d
iV(0, 1).
Thus for example,
Pr{n(p~q)~ \.96x/4np~q <X„<n(p-q) + 1.96^/4^} ~0.95.
80
60
40
20
20
Pdf
E(X ) when p = 0.8 n
pdf of xioo
n
ECX ) - 0 when p = 0.5
ri
Figure 7.3 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.
i^aiiuuiii vvciik wim aDsorning states 131
After n = 10 000 steps with p = 0.6, E(Xtl) = 2000 and
Pr {1808 < X,0000 < 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 %a 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 <j = 1 - /?. The total capital of the two players at all times is
c = a + b.
Let Xn be player 4's capital at round n where  = 0,1,2,... and X0 = a. Let Z„ be the amount A wins on trial n. The Zn are assumed to be independent. It is clear that as long as both players have money left,
Xn — Xn..! + Zm
1 j 2., . i , ■
where the Zn are i.i.d. as in the previous section. Thus [Xti, 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 A' == {X0, Xu 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 e. Figure 7.4 shows plots of A-s capital Xn versus trial number for two possible
11
löö     Difiipie ranaoiri waixs
B broke -
*
+
n
4
4
A broke
n
Figure 7.4 Two sample paths of a simple random walk with absorbing barriers at 0 and c. The upper path results in absorption at c (corresponding to player A winning all the money) and the lower one in absorption at 0 (player A broke).
games. One of these sample paths leads to absorption of X at 0 and the other to absorption at c.
1A THE PROBABILITIES OF ABSORPTION AT 0
Let Pa, a = 0, ls %..,, c denote the probabilities that player A goes broke when his initial capital is %a. Equivalently Pa is the probability that X is absorbed at 0 when ^0 = a. The calculation of Pa is referred to as a gambler's ruin problem. We will obtain a difference equation for Pa.
First, however, we observe that the following boundary conditions must apply:
since if a = 0 the probability of absorption at 0 is one whereas if a = c, absorption at c has already occurred and absorption at 0 is impossible.
Now, when a is not equal to either 0 or c, all games can be divided into two mutually exclusive categories;
Probabilities of absorption at 0 133
(i) A wins the first round;
(ii) A loses the first round.
Thus the event {,4 goes broke from a} is the union of two mutually exclusive events:
[A goes broke from a]■ =
{A wans the first round and goes broke from a + 1} u{A loses the first round and goes broke from a
(7.6)
Also, since going broke after winning the first round and winning the first round are independent,
Pr {A wins the first round and goes broke from a + 1}
= Pr [A wins the first round) Pr {A goes broke from a + 1}
= pPa + i-
(7.7)
Similarly,
Pr {A loses the first round and goes broke from a — 1} = qP*~i,
(7.8)
Since the probability of the union of two mutually exclusive events is the sum of their individual probabilities, we obtain from (7.6)-(7.8), the key relation
(7.9)
This is a difference equation for Pa which we will solve subject to the above boundary conditions.
Solution of the difference equation (7.9)
There are three main steps in solving (7.9).
(i) The first step is to rearrange the equation Since p + q = 1, we have
or
(P + 4)Pa = pPa+i + qPa-i, p(P(,+ l-Pa) = q(Pa~Pa-l).
Dividing by p and letting
r —
1
gives
Pa* 1     Pa — r\P(t ~ Pa-l)-
I        L        I    H I
(ii) The second step is to find P1
To do this we write out the system of equations and utilize the boundary condition P0 — 1:
a = 1
a = 2
a — c
VP    — P
'*     1 c—l      r c- 2
u   p _ p
#1 - Po)
r{Px - 1) r2(Pi - 1)
r(Pc_2~jPc_3) = rĽ-2(Pi-l) r(Pc -1 -^c-2) = rc"I(i3i-l)
(7.10)
Adding all these and cancelling gives
Pc - Pi = - P: = (Ft - l)(r + r2 4 ■ • ■ + r*" 1):
(V. 11)
where we have used the fact that P, = 0.
Special case: p = q = ± }[p = q=j then r — 1 so r + r2 + ■ + rc~ 1 = c - 1 Hence
-Pi^-iXc-i),
Solving this gives
r= 1.
(7.12)
General case: p^q Equation (7.11) can be rearranged to give
(Pi-l)(l+r + r2 + ...+rc-1)^-l=0
so
Pi = l-
1
1 + r + r2 +----Kí
..c - 1 '
For r 1 we utilize the following formula for the sum of a finite number of terms of a geometric series;
1 — rQ
1 + r + r2 + ■ ■ ■ + ŕ'1 =--—
l — r
(7.13)
Hence, after a little algebra,
Pi =
r — r
r # 1
(7.14)
Equations (7.12) and (7.14) give the probabilities that the random walk i.
j. ivwjjiiiuvu   w j.   uk/uw j. ^ Lívii w
absorbed at zero when X0 = 1, or the chances that player A goes broke when starting with one unit of capital.
(hi) The third and final step is to solve for Pa, a^\. From the system of equations (7.10) we get
P2 = P1 + r(P1-l)
P3 = P2 + r2(P, - 1)       = P1 + (P1 _      + r2)
Pa~ P-a.-i +ra~% - 1) = P." + (Px - l)(r + r2 + ■ ■ ■ + ra~% Adding and subtracting one gives
Pa = (Pl-l)(\ + r + r2 + -+ra-1) + l.
(7.15)
Special case: p = q = \ When r — 1 we have 1 +1 + r2 H-----h ra~1 = a, so
using (7.12) gives
a
P = 1 --
c
p = q.
(7.16)
General case: p^q From (7.14) we find
Pi - 1 =
r - 1
1 -ř
Substituting this in (7.15) and utilizing (7.13) for the sum of the geometric series,
P =
r- 1 \/l -ŕ
o
l-rc  \ 1-r
+ 1
which rearranges to
_ra-rc
r ŕ 1
Thus, in terms of p and q we finally obtain the following results.
Theorem 7.1 The probability that the random walk is absorbed at 0 when it starts at X0 = a> (or the chances that player A goes broke from a) is
(qipf ~ (g/py 1 - (q/pY
(7.17)
■
Table 7,1 Values of Pa for various values of p.
a	p = 0.25	p = QA	p = 0.5
0	1	1	1
1	0.99997	0,99118	0.9
2	0.99986	0.97794	0.8
3	0.99956	0.95809	0.7
4	0.99865	0.92831	0.6
5	0.99590	0.88364	0.5
6	0.98767	0.81663	0.4
7	0.96298	0.71612	0.3
8	0.88890	0.56536	0.2
9	0.66667	0.33922	0.1
10	0	0	0
p = 0.25
a
Figure 7.5 The probabilities Pa that player A goes broke. The total capital of both players is 10, a is the initial capital of A, and p = chance that A wins each round.
When p = q = %
Some numerical values
Table 7.1 lists values of Pa for f =10, a-0,1,..., 10 for the three values p = 0.25, p = 0.4 and p = 0.5. The values of Pa are plotted against a in Fig. 7.5. Also shown are curves for p = 0.75 and p = 0.6 which are obtained from the relation (see Exercise 8)
Pa{p)~l-Pc,-a(l-p).
In the case shown where p = 0.25, the chances are close to one that X will be absorbed at 0 {A will go broke) unless X0 is 8 or more. Clearly the chances that A does not go broke are promoted by:
(i) a large p value, i.e. a high probability of winning each round;
(ii) a large value of X0, i.e. a large share of the initial capital.
7.5 ABSORPTION AT c> 0
We have just considered the random Walk {Xn, n = 0,1,2,... ] where X„ was player A's fortune at epoch n, Let Y„ be player B's fortune at epoch n. Then { Yn, » = 0,1,2,...} is a random walk with probability q of a step up and p of a step down at each time unit. Also, YQ = c-a and if Y is absorbed at 0 then X is absorbed at c. The quantity
Qa = Pr [X is absorbed at c when X0 = a}i
can therefore be obtained from the formulas for Pa by replacing a by c — a and interchanging p and q.
Special case: p = q = \ In this case P„ = 1 - a/c so Qa — 1 - (c - a)/a Hence
p = q.
General case: p # q From (7.17) we obtain
Qa =
(p/qra-(p/q)1 1 - (p/qf
i
138    Simple random walks
Multiplying the numerator and denominator by (q/pf and rearranging gives
p^q.
In all cases we find
Thus absorption at one or the other of the absorbing states is a certain event.
That the probabilities of absorption at 0 and at c add to unity is not obvious. One can imagine that a game might last forever, with A winning one round, B winning the next, A the next, and so on. Equation (7.18) tells us that the probability associated with such never-ending sample paths is zero. Hence sooner or later the random walk is absorbed, or in the gambling context, one of the players goes broke.
7.6 THE CASE c = ao
la, which is player A*s initial capital, is kept finite and we let b become infinite, hen player A is gambling against an opponent with infinite capital Then, ince c = a + b,c becomes infinite. The chances that player A goes broke are )btained by taking the limit c ~* co in expressions (7.16) and (7,17) for pu. There ,re three cases to consider.
:) p>q
"hen player A has the advantage and since q/p < 1,
8m P„ - Kin(qlpf -{q/pY- = («/„)",
C~* CO
1 - (q/p)'
hich is less than one.
i) p = q
hen the game is 'fair' and
CO
00
lim pa = lim 1 - l.
c
i) p<q
ere player A is disadvantaged and
urn p. = lim m - m
i - (g/py
= 1
How long will absorption take? 13$
Note that even when A and B have equal chances to win each round, playet A goes broke for sure when player B has infinite initial capital, In casinos the situation is approximately that of a gambler playing someone with infinite capital, and, to make matters worse p < q so the gambler goes broke with probability one if he keeps on playing. Casino owners are not usually referred to as gamblers!
7.7 HOW LONG WILL ABSORPTION TAKE?
In Section 7.5 we saw that the random walk X on a finite interval is certain to be absorbed at 0 or c. We now ask how long this will take. Define the random variable
Ta = time to absorption of X when X0 — a,      a = 0,1,2,..., c.
The probability distribution of Ta can be found exactly (see for example Feller, 1968, Chapter 14) but we will find only the expected value of Ta:
Da = E(Ta).
Clearly, if a = 0 or a = c, then absorption is immediate so we have the boundary conditions
(7.19)
(7.20)
Do	= 0
	= 0
n
a+1 a
a-1
p t
"q1
k-1
l   i_<
i   i i.
i   t I
i I
1
14U    simple random walks We will derive a difference equation for Da. Define
P{a>k) = Vr{Ta = k}ik = l,2,...
which is the probability that absorption takes k time units when the process begins at a. Considering the possible results of the first round as before (see the sketch in Fig. 7.6), we find
P{a, k) = pP{a + 1, k- 1) + qP{a -\,k- 1). Multiplying by k and summing over k gives
go
E(Ta) = £ kP(a,k) = p X kP(a+hk-l) + q g kP(a - 1, k - 1).
Putting j~k— 1 this may be rewritten
co
P I (/+ 1)F(« +lj) + q Z Q + Wo
00
j-0 j = 0
■X
oc
+ pZ P(a-Mj) + 4 Z ^(«~ W)-But we have seen that absorption is certain, so
Hence
co
Z m+i,j) = z
Table 7.2 Values of Da from (7.22) and (7.23) with
c=10			
a	p = 0.25	p = 0.4	p = 0.5
0	0	0	0
1	1.999	4.559	9
2	3.997	8.897	16
3	5.991	12.904	21
4	7.973	16.415	24
5	9.918	19.182	25
6	11.753	20.832	24
7	13.260	20.806	21
8	13.778	18.268	16
9	11.334	11.961	9
10	0	0	0
How long will absorption take? 141
or, finally,
A, = pDa + i+ 1
a = 1,2, ...,c — 1.
(7.21)
This is the desired difference equation for Da, which can be written down without the preceding steps (see Exercise 11).
The solution of (7.21) may be found in the same way that we solved the difference equation for Pa. In Exercise 12 it is found that the solution satisfying the boundary conditions (7.19), (7.20) is
! Da - a(c - a)
(7.22)
1
q-p
a — c
1 - {q/pf 1 - (q/pf
(7.23)
Numerical values
Table 7.2 lists calculated expected times to absorption for various values of a when c = 10 and for p = 0.25, p - 0.4 and p = 0.5. These values are plotted functions of a in Fig. 7.7.
as
10 a
Figure 7.7 The expected times to absorption, Da> of the simple random walk starting at a when c = 10 for various p.
i
142    Simple random walks
It is seen that when p = q and c = 10 and both players in the gambling game start with the same capital, the expected duration of the game is 25 rounds. If the total capital is c = 1000 and is equally shared by the two players to start with, then the average duration of their game is 250 000 rounds!
Finally we note that when c — oc, the expected times to absorption are
r a
q-p cc.
p<q
p^q
(7.24)
as will be proved in Exercise 13
7.8 SMOOTHING THE RANDOM WALK-THE WIENER PROCESS AND BROWNIAN MOTION
In Fig. 7.8a are shown portions of two possible sample paths of a simple unrestricted random walk with steps up or down of equal magnitudes. The illustrations in Fig. 7,8b~f were obtained by successive reductions of Fig. 7.8a. In (a), the 'steps' are discernible, but after several reductions the paths become smooth in appearance. In terms of the position and time scales in (a), the steps in (f) are very small and so is the time between them. The point of this is to illustrate that paths may be discontinuous but appear quite smooth when viewed from a distance.
Consider the time interval (0, (]. Subdivide this into subintervals of length At so that there are t/At such subintervals. We now suppose that a particle, initially at x = 0, makes a step (in one space dimension) at the times At, 2At, and that the size of the step is either + Ax or — Ax, the probability being 1/2 that the move is to the left or the right. Thus the position of the particle, X{t), at time t, is a random walk which has executed t/At steps. Since the position will depend on the choice of At and Ax, we write the position as X(t; At, Ax).
We may write
(,'Af
X(t; At, Ax) = X z;>
(7.25)
Position X (t) i
x - 0
At
Ax ■
# *
(a)
■ * 4 m *> ■ mm* • *
* *
» + +
i * mm**
i *■
J
(b)
where the Z{ are independent and identically distributed with
Pr [Z,- - + A.x] - Pr [Zt = - Ax] = 1/2,     i =1,2,.
For the Zt we have.
E[Z J = 0:
and
1- r r* 7-1
(e)
Figure 7.8 In (a) are shown two sample paths of
144    Simple random walks
From (7.25) we get
E[X(t;At, Ax)] = 0,
and since the Z{ are independent,
Var [X{t; At, Ax)] = (t/At) Var [ZJ -
t{Ax)2
Now we let Af and Ax get smaller so the particle moves by smaller amounts but more often. If we let At and Ax approach zero we won't be able to find the limiting variance as this will involve zero divided by zero, unless we prescribe a relationship between At and Ax.
A convenient choice is Ax — ^/At which makes Var [X(t; At, Ax)] — t for all values of At. In the limit Af 0 the random variable X(t; At, Ax) converges in distribution to a random variable which we denote by W(i). From the central limit theorem (Chapter 6) it is clear that W{t) is normally distributed. Furthermore,
The collection of random variables {W(t\t^0}, indexed by £, is a continuous process in continuous time called a Wiener process or Brownian motion, though the latter term also refers to a physical phenomenon (see below).
The Wiener process (named after Norbert Wiener, celebrated mathematician, 1894-1964) is a fascinating mathematical construction which has been much studied by mathematicians. Though it might seem just an abstraction, it has provided useful mathematical approximations to random processes in the real world. One outstanding example is Brownian motion. When a small particle is in a fluid (liquid or gas) it is buffeted around by the molecules of the fluid, usually at an astronomical rate. Each little impact moves the particle a tiny amount. You can see this if you ever watch dust or smoke particles in a stream of sunlight. This phenomenon, the erratic motion of a particle in a fluid, is called Brownian motion after the English botanist Robert Brown who observed the motion of pollen grains in a fluid under a light microscope. In 1905, Albert Einstein obtained a theory of Brownian motion using the same kind of reasoning as we did in going from random walk to Wiener process. The theory was subsequently confirmed by the experimental results of Perrin. For further reading on the Wiener process see, for example, Parzen (1962), and for more advanced aspects, Karlin and Taylor (1975) and Hida (1980).
Random walks have also been employed to represent the voltage in nerve cells (neurons). A step up in the voltage is called excitation and a step down is called inhibition. Also, there is a critical level (threshold) of excitation of which
E[_W{t)~] - 0 Var[W(f)] = r.