CHAPTER 5 Random Processes ••

where dl is a parameter of the Wiener process which must be determined from observations. When dl = 1,X(t)
is called a standard Wiener (or standard Brownian motion) process.
The autocorrelation function Rx(t, s) and the autocovariance function Kx(t, s) of a Wiener process X(t) are
given by (see Prob. 5.23)

Rx(t, s) = Kx(t, s) = a2 min(t,s) s, t;:::: 0 (5.64)

DEFINITION 5.7.2

A random process {X( t), t ::::: 0} is called a Wiener process with drift coefficient !l if

1. X(t) has stationary independent increments.

2. X(t) is normally distributed with mean {lt.
3. X(O) = 0.

From condition 2, the pdf of a standard Wiener process with drift coefficient {lis given by

f 1
X(t) (X) -
_
-- e-(x-p,d /(21) (5.65)
&i

5.8 Martingales
Martingales have their roots in gaming theory. A martingale is a random process that models a fair game. It is a
powerful tool with many applications,especially in the field of mathematical finance.

A. Conditional Expectation and Filtrations:

The conditional expectation E(Y I X1, • • • ,Xn) is a r.v. (see Sec. 4.5 D) characterized by two properties:

1. The value of E(Y lXI' ...,Xn) depends only on the values of X1, ...,Xn,that is,

(5.66)

2. E[E(YIX1, ...,X)]= E(Y) (5.67)

'
If XI' ...'xn is a sequence of r.v. s ' we will use Fn to denote the information contained in XI' ...'xn and we write
E(YIFn) for E(YIX1, ...,Xn),that is,

(5.68)

'
We also define information carried by r.v. s X1, ..., Xn in terms of the associated event space (a-field),
a(XI' ...,Xn). Thus,

(5.69)

and we say that Fn is an event space generated by X1, • • • , Xn. We have

if 1:Sn:Sm (5.70)

A collection {Fn,n = 1, 2, ... } satisfying Eq. (5.70) is called a filtration.

Note that if a r.v. Z can be written as a function of X1, ..., Xn, it is called measurable with respect to
XI' ...'xn' or F n-measurable.
••• CHAPTER 5 Random Processes

Properties of Conditional Expectations:

1. Linearity:

(5.71)
where a and bare constants.

2. Positivity:

If Y� 0, then (5.72)
3. Measurabllty:

If Yis Fn-measurable, then (5.73)

4. Stability:

If Z is Fn-measurable, then (5.74)

5. Independence Law:

If Yis independent of Fn, then (5.75)

6. Tower Property:

(5.76)
7. Projection Law:

E[E(Y I Fn)] = E(Y) (5.77)

8. Jensen's Inequality:
If g i� a convex function and E( I Y.l) < oo, then

(5.78)

B. Martingale:

Definition:

A discrete random process {Mn, n � 0} is a martingale with respect to Fn if

(1) E(IMni)< oo for all n � 0

(2) E(Mn+ 1 1 Fn) = Mn for all n (5.79)
It immediately follows from Eq. (5.79) that for a martingale
form� n (5.80)

A discrete random process {Mn, n � 0} is a submartingale (supermartingale) with respect to Fn if

(1) E(jMnj)< oo for all n � 0

(2) E(Mn+ 1 1 Fn) � (�) Mn for all n (5.81)
While a martingale models a fair game, the submartingale and supermartingale model favorable and unfa­
vorable games, respectively.

Theorem 5.8.1

Let {Mn, n � 0} be a martingale. Then for any given n

(5.82)
CHAPTER 5 Random Processes

Equation (5.82) indicates that in a martingale all the r.v.'s have the same expectation (Prob. 5.67).

Theorem 5.8.2 (Doob decomposition)

Let X = {Xn, n ;::: 0} be a submartingale with respect to Fn. Then there exists a martingale M = {Mn, n ;::: 0}
and a process A = {An, n ;::: 0} such that

(1) M is a martingale with respect to Fn;

(2) A is an increasing process An+ 1 ;::: An;
(3) An is Fn _1-measurable for all n;
(4) Xn = Mn +An.
(For the proof of this theorem see Prob. 5.78.)

C. Stopping Time and the Optional Stopping Theorem:

Definition:

A r.v. T is called a stopping time with respect to Fn if

1. T takes values from the set {0, 1, 2, ... , oo}
2. The event {T = n} is Fn-measurable.
EXAMPLE 5.1: A gambler has $100 and plays the slot machine at $1 per play.

1. The gambler stops playing when his capital is depleted. The number T = n1 of plays that it takes the
gambler to stop play is a stopping time.
2. The gambler stops playing when his capital reaches $200. The number T = n2 of plays that it takes
the gambler to stop play is a stopping time.
3. The gambler stops playing when his capital reaches $200, or is depleted, whichever comes ftrst. The
number T = min(n1, n2) of plays that it takes the gambler to stop play is a stopping time.

EXAMPLE 5.2 A typical example of the event T is not a stopping time; it is the moment the stock price attains
its maximum over a certain period. To determine whether T is a point of maximum, we have to know the future
values of the stock price and event {T = n} ft. Fn.

Lemma 5.8.1

1. + T2•
If T1 and T2 are stopping times, then so is T1
2. If T1 and T2 are stopping times, then T = min(n1, n2) and T = max(n1, n2) are also stopping times.
3. min (T, n) is a stopping time for any ftxed n.

Let/A denote the indicator function of A, that is, the r.v. which equals 1 if A occurs and 0 otherwise. Note
that/{T>n}' the indicator function of the event {T > n}, is Fn-measurable (since we need only the information
up through time n to determine if we have stopped by time n).

Optimal Stopping Theorem:

Suppose {Mn, n ;::: 0} is a martingale and T is a stopping time. If

(1) E(T ) < oo (5.83)

(2) E(iMTi) < oo (5.84)

(3)
nli!!,E ( I Mn i i{T>n} ) =O (5.85)

Then

(5.86)

Note that Eqs. (5.84) and (5.85) are always satisfied if the martingale is bounded and P(T < oo) = 1.
 CHAPTER 5 Random Processes

D. Martingale in Continuous Time

A continuous-time filtration is a family {F1, t� 0} contained in the e vent space F such that F. C F1 fors< t.
The continuous random process X(t) is a martingale with respect to F, if

(1) E(iX (t)l) < oo (5.87)

(2) E(X(t) I F.) X (s) = for t� s (5.88)

Similarly, continuous-time submartingales and supermartingales can be defined by replacing equal ( = ) sign
by� and ::5, respecti vely, in Eq. (5.88).

SOLVED PROBLEMS

Random Processes

5.1. Let XI' X2 , • • • be independent Bemoulli r.v.'s (Sec. 2.7A) with P(Xn = 1) p and P(Xn = 0) = q = 1 - p
=

for all n. The collection of r.v.'s {Xn, n� 1} is a random process, and it is called a Bernoulli process.
(a) Describe the Bemoulli process.

(b) Construct a typical sample sequence of the Bemoulli process.

(a) The Bemoulli process {Xn, n 2: 1} is a discrete-parameter, discrete-state process. The state space is E = {0, 1},
and the index set is T ={1, 2, . . . }.
(b) A sample sequence of the Bemoulli process can be obtained by tossing a coin consecutively. If a head
appears, we assign 1, and if a tail appears, we assign 0. Thus, for instance,

n 2 3 4 5 6 7 8 9 10
Coin tossing H T T H H H T H H T

xn 0 0 0 0

The sample sequence {xn} obtained above is plotted in Fig. 5-4.

xn

'l
• • • • • •

• • • • �
0 2 4 6 8 10 n

Fig. 5-4 A sample function of a Bernoulli process.

5.2. Let Z1, Z2, • • • be independent identically distributed r.v.'s with P(Zn = 1) = p and P(Zn = - 1) = q =
1 - p for all n. Let

n=1,2,... (5.89)

and X0 = 0. The collection of r.v.'s {Xn , n� 0} is a random process , and it is called the simple random
walk X(n) in one dimension.
(a) Describe the simple random walk X(n).
(b) Construct a typical sample sequence (or realization) of X(n) .
CHAPTER 5 Random Processes

which yields

3 1
-pi +-pz = P1
4 2
1 1
-pi +-pz = P z
4 2

Each of these equations is equivalent to p1 = 2p2• Since p1 + p2 = 1, we obtain

(b) Since the Markov chain is regular, by Eq. (5.53), we obtain

n
3 1 2
-

n-oo
n
lim p = lim
4
n-oo -
1
4
1
-
= [!] =
3 3
2 1
-
2 2 3 3

(c) Setting a = � and b = i in Eq. (5.143) (Prob. 5.30), we get

2 1 1
-
- \ n
n
P =
3 3 { 1 3 3
2
-
1
- -,4) 2 2
3 3 3 3

n
Since lim•-"" (� ) = 0, we obtain

n
1 3 2 1
- -
n 4 4 3 3
lim p = lim
n-oo n-oo 1 2 -
1
-
2 2 3 3

Poisson Processes

5.48. Let Tn denote the arrival time of the nth customer at a service station. Let Zn denote the time interval
between the arrival of the nth customer and the (n - l)st customer; that is,

Zn =T-T
n n-1 n;?:l (5.172)

and T0 = 0. Let {X(t), t;;:: 0} be the counting process associated with {Tn, n;;:: 0}. Show that if X(t) has
stationary increments, then Zn, n = 1, 2, ..., are identically distributed r.v.'s.

We have

P(Zn > z) = 1 - P(Zn :s; z) = 1 - Fzn(z)

By Eq. (5.172), P(Zn > z) = P(T.- T. _ 1 > z) = P(T. > Tn-l + z)

Suppose that the observed value of T. _ 1 is r. _ 1• The event (T. > T. _ 1 + z IT. _ 1 = tn _ 1) occurs if and only if X(t)
does not change count during the time interval (tn-1' r. _ 1 + z) (Fig. 5-14). Thus,

P(Zn > ziTn-l = tn _ 1 ) = P(Tn > Tn-l + ziT._1 = t. _ 1)

= P[X(t. _ 1 + z)- X(t. _ 1) = 0]
or P(Z. :s; zl T. _ 1 = t. _ 1) = 1 - P[X(t. _ 1 + z)- X(t. _ 1) = 0] (5.173)
 CHAPTER 5 Random Processes

Since X(t) has stationary increments, the probability on the right-hand side ofEq. (5.173) is a function only of the
time difference z. Thus,

P(Zn � zl Tn-l = t n_1) = l - P[X(z) = 0] (5.174)

which shows that the conditional distribution function on the left-hand side ofEq. (5.174) is independent of the
particular value of n in this case, and hence we have

F2 n(z) = P(Zn � z) = 1 - P[X(z) = 0] (5.175)

which shows that the cdf of Zn is independent of n. Thus, we conclude that the Zn's are identically distributed r.v.'s.

Fig. 5-14

5.49. Show that Definition 5.6.2 implies Definition 5.6.1.

Letp/() = P[X(t) = n]. Then, by condition 2 of Definition 5.6.2, we have

p0(t + !l.t) = P[X(t + !l.t) = 0] = P[X(t) = 0, X(t + !l.t) - X(O) = 0]

= P[X(t) = 0] P[X(t + llt) - X(t) = 0]

Now, by Eq. (5.59), we have

P[ X(t + llt)- X(t) = 0] =1-A llt + o(!l.t)

Thus, p0(t + !l.t) = p0(t)[1 - A llt + o(llt)]
p0(t + llt)- p0(t) _ o(llt)
or = APo (t) +
llt llt

Letting llt-+ 0, and by Eq. (5.58), we obtain

(5.176)

Solving the above differential equation, we get

Po(t) = ke
-AI

where k is an integration constant. Since p0(0) = P[X(O) = 0] = 1 , we obtain

Po(t) = e-
AI
(5.177)

Similarly, for n > 0,

Pn(t + llt) = P[ X(t + llt) = n]

= P[ X(t) = n, X(t + llt)- X(O) = 0]
n
+ P[ X(t) = n-1, X(t + llt)- X(O) = 1] + � P[ X(t) = n- k, X(t + llt)-X(O) = k]
k=2

Now, by condition 4 of Definition 5.6.2, the last term in the above expression is o(llt). Thus, by conditions 2 and 3
of Definition 5.6.2, we have

Pn(t + llt) = Pn(t)[1-A llt + o(!l.t)] + Pn-!(t)[A llt + o(llt)] + o(llt)

Pn(t + llt)- Pn(t) _ , , o(!l.t)

Thus = A-Pn(t) + A-Pn -!(t) +
llt llt
CHAPTER 5 Random Processes

and letting At -+ 0 yields

(5.178)

;.'
Multiplying both sides by e , we get

d At At
Hence, -[e Pn(t)] =k Pn-l(t) (5.179)
dt

Then by Eq. (5.177), we have

or

where c is an integration constant. Since p1(0) = P[X(O) = 1] = 0, we obtain

(5.180)

To show that

-At ([Link]
pn(t)=e --

n!

we use mathematical induction. Assume that it is true for n - 1; that is,

Substituting the above expression into Eq. (5.179), we have

Integrating, we get

At ([Link]
e Pn(t)= -- +cl
n!

Since p/0) = 0, c1 = 0, and we obtain

n
-J.t (At) (5.181)
Pn(t)=e --

n.I

which is Eq. (5.55) of Defmition 5.6.1. Thus we conclude that Definition 5.6.2 implies Definition 5.6.1.

5.50. Verify Eq. (5.59).

We note first that X(t) can assume only nonnegative integer values; therefore, the same is true for the counting
increment X(t + M) - X(t). Thus, summing over all possible values of the increment, we get

""

}: P[X(t + !J.t)- X(t)=k]= P[X(t + !J.t)- X(t)=0]

k=O

+ P[X(t +M)- X(t)=1] + P[X(t + !J.t)- X(t) �2]

=1
 CHAPTER 5 Random Processes

Substituting conditions 3 and 4 of Definition 5.6.2 into the above equation, we obtain

P[X(t+llt) - X(t) = 0] = 1 - AAt+o(llt)

5.51. (a) Using the Poisson probability distribution inEq. (5.181), obtain an analytical expression for the
correction term o(At) in the expression (condition 3 of Definition 5.6.2)

P[X(t + At) - X(t) = 1] = A At + o(At) (5.182)

(b) Show that this correction term does have the property ofEq. (5.58); that is,

o(At )
lim =0
,Y--.Q At

(a) Since the Poisson process X(t) has stationary increments, Eq. (5.182) can be rewritten as

P[X(At) = 1] = p1(/lt) =)..At+o(At) (5.183)

Using Eq. (5.181) [or Eq. (5.180)], we have

p1(At) = AAt e-Ht = AAt(1+e-Mu- 1)

= )..flt+AAt(e-AAt- 1)

Equating the above expression with Eq. (5.183), we get

)..flt+o(At) = )..flt+AAt(e-AAt- 1)

from which we obtain

o(llt) =)..At(e-H•- 1) (5.184)

(b) From Eq. (5.184), we have

. o(llt ) }..Jlt(e-;.At -1) 1. ' -;. ru

Itm -- - 1im ( -1)- 0
_ _

- tmAe
_

�r�o llt ru�o At �r�o

5.52. Find the autocorrelation function Rx(t, s) and the autocovariance function Kx(t, s) of a Poisson process
X(t) with rate A.

From Eqs. (5.56) and (5.57),

E[X(t)] =At Var[X(t)] =At

Now, the Poisson process X(t) is a random process with stationary independent increments and X(O) = 0. Thus, by
Eq. (5.126) (Prob. 5.23), we obtain

Kx(t, s) = a1 2 min(t, s) =)..min(t, s) (5.185)

since a1 2 = Var[X(1)] = )... Next, since E[X(t)] E[X(s)] = }..2ts, by Eq. (5.10), we obtain

Rx(t, s) =)..min(t, s)+)..2ts (5.186)

5.53. Show that the time intervals between successive events (or interarrival times) in a Poisson process X(t)
with rate A are independent and identically distributed exponential r.v.'s with parameter A.

Let Z1, Z , be the r.v. 's representing the lengths of interarrival times in the Poisson process X(t). First, notice that
2
• • •

{Z1 > t} takes place if and only if no event of the Poisson process occurs in the interval (0, t), and thus by Eq. (5.177),

P(Z1 > t) = P{X(t) = 0} = e- JJ

or Fz (t) = P(Z1 s t) = 1 - e- JJ
1
CHAPTER 5 Random Processes

Hence, Z1 is an exponential r.v. with parameter 'A [Eq. (2.61)]. Let f(1 t) be the pdf of Z1. Then we have

P(Z2>t )=fP(Z2>t )jZ1=-r)Ji(-r)d-r

=IP[X(t +T)- X(T)=O]fi(T)dT

=e-;., Jfi(-r)d-r=e-AI (5.187)

·which indicates that Z2 is also an exponential r.v. with parameter 'A and is independent of Z1• Repeating the same
argument, we conclude that Z1, Z,2 • • • are iid exponential r.v.'s with parameter 'A.

5.54. Let T denote the time of the nth event of a Poisson process X(t) with rate A. Show that T is a gamma
n n
r.v. with parameters (n, A).

Clearly,

T=Z+
n 1 Z+···
2 +Z n

where Z,n n = 1, 2, . . . , are the interarrival times defined by Eq. (5.172). From Prob. 5.53, we know that Zn are iid
exponential r.v.'s with parameter 'A. Now, using the result of Prob. 4.39, we see that Tn is a gamma r.v. with
parameters (n, 'A), and its pdf is given by [Eq. (2 .65)]:

n
r..e-AI (At) -1
!1 --
t>O
frn(t )= (n-1)! (5.188)
0 t<O

The random process {T,n n <::: 1 } is often called an arrival process.

5.55. Suppose t is not a point at which an event occurs in a Poisson process X(t) with rate A. Let W(t) be the
r.v. representing the time until the next occurrence of an event. Show that the distribution of W(t) is
independent oft and W(t) is an exponential r.v. with parameter A.

Lets (0 ::S s < t) be the point at which the last event [say the (n - l)st event] occurred (Fig. 5-15) . The event
{W(t) > T} is equivalent to the event

{Z > t- s + -r!Z > t- s}

n n

Fig. 5-15

Thus, using Eq. (5.187), we have

P[W (t)>-r]= P(Zn>t- s+-rj Zn>t- s)

-.!.(t-s+r)
P(Zn>t- s+T) e
- - -.!.(t-s)
P(Zn>t- s) e
and P[W (t ) ::S T]=1-e'-.,. (5.189 )

which indicates that W(t) is an exponential r.v. with parameter 'A an d i s independent oft. Note that W(t) i s often
called a waiting time.
 CHAPTER 5 Random Processes

5.56. Patients arrive at the doctor's office according to a Poisson process with rate A= k minute. The doctor
will not see a patient until at least three patients are in the waiting room.

(a) Find the expected waiting time until the first patient is admitted to see the doctor.

(b) What is the probability that nobody is admitted to see the doctor in the first hour?

(a) Let Tn denote the arrival time of the nth patient at the doctor 's [Link]

T=Z+Z+···+Z
n 1 2 n

where Zn, n=1 , �

2, ..., are iid exponential r.v.'s with parameter A= - By Eqs. (4.132) and (2.62) ,

(5.190)

The expected waiting time until the first patient is admitted to see the doctor is

E(T3) =3(10)=30 minutes

(b) Let X(t) be the Poisson process with parameter A = �.The probability that nobody is admitted to see the
doctor in the first hour is the same as the probability that at most two patients arrive in the first 60 minutes.

Thus, by Eq. (5.55) ,

2
P[X(60) - X(O) ::;::; 2]=P[X(60) - X(O)=0]+P[X(60) - X(O) = 1]+P[X(60) - X(O) = 2]

-
-e
-60/10 + -60110
e
( )
-
60
10
+e
-60110 1
--
2 10
( )
60

=e -6 ( 1+6+18) = 0.062

5.57. Let Tn denote the time of the nth event of a Poisson process X(t) with rate A. Suppose that one event has
occurred in the interval (0, t). Show that the conditional distribution of arrival time T1 is uniform over (0, t).

For -r::;::; t,

P[T1::;::; 'f IX(t)=1]= , :; 'f, X(t)=1]

P[T::;:
P[X(t)=1]
P[X(-r)=1, X(t) - X(-r) = 0]
P[X(t) = 1]
P[X(-r)=1]P[X(t) - X(-r)=0]
P[X(t)=1]
A-re -kre -}.(t-T)
(5.191)
Ate-At

which indicates that T1 is uniform over (0, t) [see Eq. (2.57)].

5.58. Consider a Poisson process X(t) with rate A, and suppose that each time an event occurs, it is classified
as either a type 1 or a type 2 event. Suppose further that the event is classified as a type 1 event with
probability p and a type 2 event with probability 1 - p. Let X/t) and X2(t) denote the number of type 1
and type 2 events, respectively, occurring in (0, t). Show that {X1(t), t 2::: 0} and {X2(t), t 2::: 0} are both
Poisson processes with rates ).p and )..(1 - p), respectively. Furthermore, the two processes are
independent.

We have
CHAPTER 5 Random Processes

First we calculate the joint probability P[X/t) = k,Xz(t) = m].

00

P[X1(t)=k, X2(t)=m]= :L P[X1(t)=k, X2(t)=m I X(t)=n]P[X(t)=n]

n=O

Note that

P[X1(t) = k,X2(t) = miX(t) = n] = 0 when n =I= k + m

Thus, using Eq. (5.181), we obtain

P[X1(t)=k, X2(t)=m]=P[X1(t)=k, X2(t)=m I X(t)=k+m]P[X(t)=k+m]

(At)k+m
=P[X1(t)=k, X2(t)=m I X(t)=k+m]e -AI--­
(k+m)!

Now, given that k + m events occurred, since each event has probability p of being a type 1 event and probability
1 - p of being a type 2 event, it follows that

Thus,

(5.192)

00

Then P[X1(t)=k]= :L P[X1(t)=k,X2(t)=m]

m=1

=e
-Jcpt ().pt)k -;..<1-p)t
e
�[
).(1- p)t r
k! m=1 m!

().pt)k -Jc(1-p)t Jc(l-p)t

_
-e
-Jcpt
-- e e
k!
(Apd
=e
-Jcpt
-- (5.193)
k!

which indicates that X1(t) is a Poisson process with rate }..p. Similarly, we can obtain

00

P[X2(t)=m]= :L P[X1(t)=k, X2(t)=m]

k=1

=e
-;..<1-p)t ( }..(1- p)tr (5.194)
m!

and so X2 (t) is a Poisson process with rate ).(1 - p). Finally, from Eqs. (5.193), (5.194), and (5.192), we see that

Hence, X1(t) and Xz(t) are independent.

... CHAPTER 5 Random Processes

Wlener Processes

5.59. Let XI' ...' xn be jointly normal r.v.'s. Show that the joint characteristic function of XI' ... 'xn is given by

(5.195)

where ll; = E(X) and Dfk = Cov(X;, Xk) .

Let

By definition (4.66), the characteristic function of Y is

(5.196)

Now, by the results of Prob. 4.72, we see that Y is a normal r.v. with mean and variance given by [Eqs. (4.132)
and (4.135)]

n n

!Jy = E(Y) = }'; a;E(X;) = }'; a; /J; (5.197)

i=l i=l

n n n n

ay 2 = Var(Y) = }'; }'; a; ak Cov(X;. Xk) =: }'; }'; a; ak aik (5.198)

i =l k =l i =l k =I
Thus, by Eq. (4.167),

(5.199)

Equating Eqs. (5.199) and (5.196) and setting m= 1, we get

By replacing a;'s with m;'s, we obtain Eq. (5.195); that is,

Let

Then we can write

n n n

}'; W;/J; =
l
o I' }'; }'; m;mka ik = o
l
Km
i=l i =l k =l
CHAPTER 5 Random Processes

and Eq. (5.195) can be expressed more compactly as

(5.200)

5.60. Let X1, • • • , Xn be jointly normal r.v.'s Let

(5.201)

where aik (i = 1, ... , m;j = 1, ... , n) are constants. Show that Yl' ..., Ym are also jointly normal r.v.'s.

Let x= [1:] [l] Y=

Then Eq. (5.201) can be expressed as

Y=AX

Let o.=E(X)= [l ] [Z ] m= (5.202)

Then the characteristic function for Y can be written as

T
'l'"y( w, , ..., wm) = E(ejro y) = E(ejWTAX)
= E[&Wm)TX] = '�'"x(ATro)

Since X is a normal random vector, by Eq. (5.177) we can write

[ �
'l'"x(ATro)=exp j(Arol 1-'x- (Arro( Kx(ATw) ]
=exp [jwTAIJ.x- � roTAKxATw]
Thus, (5.203)

where 1-'y = AIJ.x (5.204)

Comparing Eqs. (5.200) and (5.203), we see that Eq. (5.203) is the characteristic function of a random vector Y.
Hence, we conclude that Y1, , Y are also jointly normal r.v.'s
• • •
m
Note that on the basis of the above result, we can say that a random process {X(t), t E D is a normal process if
every finite linear combination of the r.v.'s X(t), t; ET is normally distributed.

5.61. Show that a Wiener process X(t) is a normal process .

Consider an arbitrary linear combination

n
�a;X(t;) = a1 X(t 1) + a2X(t2) + ·· · + anX(tn)
(5.205)
i=l
 CHAPTER 5 Random Processes

where 0 :::; t1 < ... < tn and a ; are real constants. Now we write

n
L a1X (tJ=(a1+ +an)[ X(t1)- X(O)]+(a2+ + an)[X(t2)- X(t1)]
· · · · · ·

i=l

(5.206)

Now from conditions 1 and 2 of Definition 5.7 .1,the right-hand side ofEq. (5.206) is a linear combination of
independent normal r.v.'s. Thus, based on the result of Prob. 5.60, the left-hand side ofEq. (5.206) is also a normal
r.v.; that is, every finite linear combination of the r.v.'s X(t) is a normal r.v. Thus, we conclude that the Wiener
process X(t) is a normal process.

5.62. A random process {X(t), t ET} is said to be continuous in probability if for every E > 0 and t ET,

lim
h--+0
P{JX(t +h)- X(t )J > }E = 0 (5.207)

Show that a Wiener process X(t) is continuous in probability.

From Chebyshev inequality (2.116), we have

Since X(t) has stationary increments, we have

Var[X(t + h) - X(t)] = Var[X(h)] = dh

in view ofEq. (5.63). Hence,

{
limP jX(t+h)-X(t)j>e = lim } a h
=0
:
h--+0 h--+0 E

Thus, the Wiener process X(t) is continuous in probability.

Martingales

5.63. Let Y = X1 + X2 + X3 where Xi is the outcome of the ith toss of a fair coin. Verify the tower property
Eq. (5.76).

Let X;= 1 when it is a head and X;= 0 when it is a tail. Since the coin is fair, we have

1 1
P(Xi =1)=P(X;=O)=l and E(XJ=l

and X;'s are independent. Now

E[E <YIF2) IF,J = E[E(YIX2,X,)IX,J

= E(X1 + X2 + E(X3)IX1)
= X1 + E(X2) + E(X3) = X1 + 1
and

E(YiF,) = E(YIX,) = E(X1 + X2 + X3IX1)

= X1 + E(X2 + X3)
= X1 + E(X2) + E(X3) = X1 + 1
CHAPTER 5 Random Processes

Thus,

5.64. Let XI' X2, • • • be i.i.d. r.v.'s with mean 11-· Let

n
S= � Xi =X1 +X2 +···+Xn
i=l

Let Fn denote the information contained in XI, ..., xn. Show that

m<n (5.208)

Let m<n, then by Eq. (5.71)

E(SnIFm)=E(X l +... +XmIFm) +E(Xm+1 +... +XnIFn)

Since X1 +X +... +Xm is measurable with respect to Fm, by Eq. (5.73)

2

Since xm+ I +... + xn is independent of XI' ... ,xm, by Eq. (5.75)

E(Xm+1 +.. + XnIFn)=E(Xm+1 +.. +Xn)=(n-m)r

· " ·

Thus, we obtain

5.65. Let X1, X2, . . . be i.i.d. r.v.'s with E(X.)

l
= 0 and E(X l 2) = a 2 for all i. LetS = .� X.I =
1=1
XI + x2 + ... + xn. Let Fn denote the information contained in XI' ..., xn.
Show that

E(Sn 21Fm) = Sm 2 + (n - m) a2 m<n (5.209)

Let m<n , then by Eq. (5.71)

E(Sn 21Fm)=E([Sm + (Sn- Sm)]21Fm)

=E(Sm 21Fm)+2 E[S m(Sn- Sm)IFm] +E([(Sn- Sm)l21Fm)

Since Sm is dependent only on X" ... , Xm, by Eqs. (5.73) and (5.75)

2 E ([(Sn- Sm)2 IFm])=E(Sn-Sm )2=Var(Sn- Sm)=(n-m) a2

E(Sm 2 IFm )=Sm'

since E(X) =1-l =0, Var(X) =E(Xi 2)=a2 and Var(Sn- Sm )=Var(Xm+ 1 +... +Xn)=(n-m)a2• Next, by
Eq. (5.74)

Thus, we obtain

E(Sn 2IFm )=Sm 2 +(n-m) a2 m<n

••• CHAPTER 5 Random Processes

5.66. Verify Eq. (5.80), that is

for m 2: n

By condition (2) of martingale, Eq. (5.79), we have

for all n

Then by tower property Eq. (5.76)

and so on, and we obtain Eq. (5.80), that is

for m 2:: n

5.67. Verify Eq. (5.82), that is

Since {M
•• n 2:: 0} is a martingale, we have

for all n

Applying Eq. (5.77), we have

Thus, by induction we obtain

5.68. Let X1, X2, •• � be a sequence of independent r.v.'s with E[i Xn I] < oo and E(Xn) = = 0 for all n. Set

S0 = 0, Sn I X.
= .
r==l z
X1 + X2 + +Xn. Show that {Sn , n 2: 0} is a martingale.
= · · ·

E[[Link] � E(IXll + ... + IX.I)= E(IXli) + ... + E(IX.i) < 00

E(Sn+JIF.) = E(S. + xn+JIF.)
= s. + E(X.+1IF.) = s. + E(X.+1) = s.

sinceE(X.) = 0 for all n.

Thus, {S., n 2:: 0} is a martingale.

5.69. Consider the same problem as Prob. 5.68 except E(X.);;:: 0 for all n. Show that {Sn , n 2: 0} is a
submartingale.

Assume max E(IX.I) = k< oo, then

E[[Link] � E(IX11 + ... + IX.I) = E(IX1i) + ... + E(IX.i) � nk < oo

E(S.+1IF.) = E(S. + x.+1IF.)
= s. + E(x.; 1IF.) = s. + E(X.+1);;::: s.
sinceE(X.) 2:: 0 for all n.
Thus, {S., n 2:: 0} is a submartingale.
CHAPTER 5 Random Processes

5.70. Let X1,X2, • • • be a sequence of Bernoulli r.v.'s with

x.I = {
1

0
with probability p

with probability q = 1 - p

Let Sn = ,;1 Xi = X1 + X2 + ... + Xn. Show that ( 1) ifp = � then {Sn} is a martingale. ( 2) ifp > � then
{Sn} is a submartingale, and (3) ifp < � then {S"} is a supermartingale.

E(X) =p(1)+(1 -p)(-1)= 2p- 1

(1) If p = 1,E(X)= O,and

E[iSnl] $ E(IX;I+ "' +IXni) = E(IX11)+ "' +E(IXni) = 0 < 00

E(Sn+IIFn) = E(Sn +xn+IIFn)

= sn +E(Xn+IIFn) = sn +E(Xn+I) = sn

Thus,{S"} is a martingale.

( 2) If p > 1· 0 < E(X) $ 1, and

E[ISnll $ E(IXII+... +IXnl) = E(IXI!)+... +E(IXni) $ n < 00

E(Sn+I,Fn) = E(Sn +Xn+IIFn)

= sn +E(Xn+IIFn) = sn +E(Xn+I)> sn

Thus, {Sn} is a submartingale.

(3) If p < 1· E(X) < 0, and

E(Sn+IIFn) = E(Sn +Xn+IIFn)

= Sn +E(Xn+IIFn) = Sn +E(Xn+l) < Sn

Thus, {Sn} is a supermartingale.

Note that this problem represents a tossing a coin game,"heads" you win $1 and "tails" you lose $1. Thus,if
p = 1 ,it is a fair coin and ifp> 1· the game is favorable,and ifp < 1· the game is unfavorable.

5.71. LetXI X2, ... be a sequence ofi.i.d. r.v.'s with E(X;) = Jl > 0. Set
'
n

I X.1 = XI + X2 +
S0 = 0 S n = i�l + Xn and
'
· · ·

Mn = Sn- nJl (5.210)

Show that {Mn, n ;::: 0} is a martingale.

/
Next,using Eq. (5.208)ofProb. 5.64, we have

E(Mn+11Fn)=E(Sn+1-(n+ l)JliFn)
= E(Sn+IIFn)- (n + 1)/l
= S" +Jl-(n+1)Jl = Sn - nJl = Mn
Thus,{Mn, n :C: 0} is a martingale.
 CHAPTER 5 Random Processes

5.72. Let X1, X

2
, • . .

x. + x + ... + xn, and

be i.i.d. r.v.'s with E(X.)
z = 0 and E(X1 2) . = a2 for all i. Let S0 = 0, Sn = l:
J=l
. X.1 =

2
2 2
Mn = Sn -na (5.211)

Show that {Mn, n � 0} is a martingale.

( ) - na2
n 2 n
Mn =Sn2 - na2 = ""'
� x.� ""' Xz2 + 2""'
=LJ • J na 2
LJ x.x.-
i=l i=l i<j

Using the triangle inequality, we have

n
E(l Mn I) s }: Xi
E ( 2 )+ 2}: E(l XiXi I)+ na2
i=l i<j

Using Cauchy-Schwarz inequality (Eq. (4.41)), we have

Thus,

Next,

E(Mn+tiF n) = E[(Xn+t + Sn)2- (n + 1) a21Fn]

= E[X�+i + 2Xn+ 1Sn + S/- (n + 1) a21Fn]
= Mn + E(X�+1) + 2E(Xn+1)Sn- a2
= Mn + az - az = Mn

Thus, {Mn, n � 0} is a martingale.

5.73. Let XI'X , • • • be a sequence of i.i.d. r.v.'s with E(X) = !land E( I Xi!)< oo for all i. Show that
2
n
Mn = -
1
n
[l x' .
(5.212)
!l i=!

is a martingale.

E(Mn+tiFn)=E Mn ( � Xn+tiFn)
=M n .!_E(Xn+1)=M n }!_=Mn
1-l 1-l

Thus, {Mn} is a martingale.

CHAPTER 5 Random Processes ••

5.74. An urn contains initially a red and black ball. At each time n :::::: 1, a ball is taken randomly, its color
noted, and both this ball and another ball of the same color are put back into the urn Continue similarly .

aftern draws, the urn contains n + 2 balls. Let X n denote the number of black balls after n draws. Let
Mn Xn I (n + 2) be the fraction of black balls after n draws. Show that {Mn, n:::::: 0} is a martingale.
=

(This is known as Polya's Urn.)

, X=
0 1 and Xn is a (time-homogeneous) Markov chain with transition

P(Xn+l=k +1I Xn=k}=-k- and P(Xn+!=klXn=k}= n+2+k

n+2 n+2
andXn takes values in ) Xn + n 2
{1 , 2, ... , n + 1} and E(Xn+d Xn= � ·

Now,

and

(!
E(M n+dFn)=E n 3 Xn+dxn )
=-1-3 E(Xn+1IXn)=-1-3 xn +�=�=M n ( )
n+ n+ n+2 n+2
Thus, {Mn, n :.2: 0} is a martingale.

5.75. Let XI' X2, • • • be a sequence of independent r.v.'s with

P{X = 1} = P{X = - 1} = �
We can think of Xi as the result of a tossing a fair coin game where one wins $1 if heads come up and loses
$1 if tails come up. The one way of betting strategy is to keep doubling the bet until one eventually wins. At
this point one stops. (This strategy is the original martingale game.) Let Sn denote the winnings (or losses)
up through n tosses. S0 0. W henever one wins, one stops playing, so P(Sn+ 1
= 11Sn 1) 1. Show that = = =

{Sn, n:::::: 0} is a martingale-that is, the game is fair.

Suppose the first n tosses of the coin have turned up tails. So the loss S n is given by
s=n -(1 + 2 + 4 + ... + 2n-)l =-(2n-1)
At this time, one double the bet again and bet 2n on the next toss. This gives

n - (2n-1))=! P(Sn+l=-(2n-1)iS=-(
P(Sn+l=liS= n 2n-1))=!2
2'

and

E(Sn+d Fn)=E(Sn+!)= + [-(2n+I -1)]

�(1) �
=.!.2-2n +.!.2=-(2n -1)=sn

Thus, {Sn, n :.2: 0} is a martingale.

 CHAPTER 5 Random Processes

5.76. Let{Xn, 2::: 0} be a martingale with respect to the filtration Fn and let g be a convex function such that
n

E[g(Xn)] < for all 2::: 0. Then show that the sequence {Zn, 2::: 0} defined by
oo n n

(5.213)

is a submartingale with respect to Fn.

By Jensen's inequalityEq. (4.40) and the martingale property of Xn, we have

Thus, {Zn' n 2:: 0} is a submartingale.

5.77. Let Fn be a filtration and E(X) < oo. Define

(5.214)

Show that {Xn' n 2::: 0} is a martingale with respect to Fn.

E{l x n I)=E(l E{XI Fn)l)s lE[ E(XI Fn)] I=I E(X)I < 00

E(xn+dFn)=E[E(XiFn+t)IFn]
=E(XI Fn) byEq.(5.76)

=X n
Thus, {Xn, n 2:: 0} is a martingale with respect to Fn.
5.78. Prove Theorem 5.8.2 (Doob decomposition).

Since X is a submartingale, we have

E(Xn+ tiFn) Xn
2:: (5.215)

Let

dn = E(Xn+ 1 - xn IFn) = E(Xn+ tlFn)- xn 2:: 0 (5.216)

and dn is Fn-measurable.
= O,An =,�, di = d1+d2+ +dn-l' and Mn = Xn-An. Then it is easily seen that (2), (3), and (4) of
o-1
SetA0 · · ·

Theorem 5.82 are satisfied. Next,

n n-J
+
=� �-I�=�-I�=�-�=�
i=l i=l

Thus, (1) of Theorem 5.82 is also verified.

5.79. Let {Mn, n 2::: 0} be a martingale. Suppose that the stopping timeT is bounded, that isT ::5 k. Then
show that

(5.217)
CHAPTER 5 Random Processes

Note that /{T=j}' the indicator function of the event {T =j}, is Fn-measurable (since we need only the information
up to time n to determine if we have stopped by time n). Then we can write

and

k-1
E(Mr1Fk_1)=E(Mk I{T=k}IFk-1)+ � E(Mj I{T =j}IFk-1)
j=O
Forj :::s k- l,M/{T=j} is Fk_1-measurable, thus,

Since T is known to be no more thank, the event {T =k} is the same as the event {T > k- 1 which is
Fk_1-measurable. Thus,

E(Mk I{r=k}IFk_1)=E(Mk /{r>H}I Fk-1)

= /{T>k-1} E(MkI Fk-1)= /{T>k-1} Mk-1
since {Mn} be a martingale. Hence,

k-1
E(Mr1Fk_1)=l{T>k-1}Mk_1 + � E(Mj /{T=j})
j=O
In a similar way, we can derive

k-2
E(MTI Fk-2)= /{T>k-2} -2 + j�=O E(Mj I{T=j})
Mk

And continue this process until we get

and finally

5.80. Verify the Optional Stopping Theorem.

Consider the stopping times Tn = rnin{T, n}. Note that

(5.218)

Hence,

(5.219)

Since Tn is a bounded stopping time, by Eq. (5.217), we have

(5.220)
 CHAPTER 5 Random Processes

and J� P(T > n) = 0, then if E(l MT I)< 00, (condition (1), Eq. (5.83)) we have. J� CIMr II{T>n}) = 0. Thus, by
condition (3), Eq. (5.85), we get. � ( IMr II{T>n}) = 0. Hence, by Eqs. (5.219) and (5.220), we obtain

5.81. Let two gamblers, A andB, initially have a dollars and b dollars, respectively. Suppose that at each
round of tossing a fair coin A wins one dollar fromB if "heads" comes up, and gives one dollar toB if
"tails" comes up. The game continues until either A orB runs out of money.

(a) What is the probability that when the game ends, A has all the cash?
(b ) What is the expected duration of the game?

(a ) Let XI' x2, . . . be the sequence of play-by-play increments in A's fortune; thus, xi = ::!:: 1 according to whether
ith toss is "heads" or "tails." The total change in A's fortune after nplays is Sn= i X . The game continues
.
i=l l

until time T where T = min{n: s = -a or +b}. It is easily seen that T is a stopping time with respect to
.

F. = a(X1, X2, • • • , X.) and {S. } is a martingale with respect to F•. (See Prob. 5.68.) Thus, by the Optional
Stopping Theorem, for each n < oo

0=E(So)=E(Smin(T,n))
=- aP (T ::5 nand Sr =-a)+b P(T ::5 nand Sr =b)+E(S. l{T>n))

As n-+ oo, the probability of the event {T > n} converges to zero. Since s. must be between -a and b on the
event {T > n}, it follows that E(S. l{T > n}) converges to zero as n-+ oo. Thus, letting n-+ oo, we obtain

-aP(ST = -a) + bP(ST = b) = 0 (5.221)

Since Srmust be -a orb, we have

P(ST= -a) + P(ST= b) =1 (5.222)

Solving Eqs. (5.221) and (5.222) for P(ST= -a) and P(Sr = b), we obtain (cf. Prob. 5.43)

b a
P(Sr =-a)= -- , P(Sr =b)= -- (5.223)
a+b a+b

Thus, the probability that when the game ends,A has all the cash is a/(a + b).

(b ) It is seen that {S. 2- n} is a martingale (see Prob. 5.72, a2 = 1). Then the Optional Stopping Theorem
implies that, for each n= 1, 2, . . ,
.

E ( s�n(T,n)- min(T , n) )=0 (5.224)

Thus,

(5.225)

Now, as n-+ oo, min(T, n)-+ T and ST 2 /{T""n}-+ ST 2, and li_ll!, E[min(T, n)] = E(T)
.

lim
.�,
a
( ) ( )
a
E ( Sr 2 /{T""n} )=E(s;)=a2 - - +b2 - - =ab
a+b a+b

Since� is bounded on the event {T > n}, and since the probability of this event converges to zero as
n-+ oo, E(S�l{T > n})-+ 0 as n-+ oo. Thus, as n-+ oo, Eq. (5.225) reduces to

E(T) =ab (5.226)

CHAPTER 5 Random Processes ·-�·

5.82. Let X(t) be a Poisson process with rate).> 0. Show that x(t) - At is a martingale.

We have

E (IX(t)- .At!) s E[X(t)] +.At=[Link] < oo

since X(t) 2: 0 and by Eq. (5.56), E[X(t)]=At.

E[X(t)- AtIFs]=E[X(s)- At+X(t)- X(s)IF.J

=E[X(s)- .AtiFsl +E[X(t)- X(s)IFs]
=X(s)- At+E[X(t)- X(s)]
=X(s)- At+A(t- s)=X(s) - As

Thus, x(t)- At is a martingale.

[SUPPLEMENTARY PROBLEMS
5.83. Consider a random process X(n)= {Xn' n 2: 1}, where

X=Z+Z
n I 2
+···+Zn

and Z" are iid r.v.'s with zero mean and variance d. Is X(n) stationary?

5.84. Consider a random process X(t) defined by

X(t)= Y cos( rot+8)

where Y and e are independent r.v.'s and are uniformly distributed over (-A, A) and ( -n,n), respectively.

(a) Find the mean of X(t).

(b) Find the autocorrelation function Rx<t, s) of X(t).

5.85. Suppose that a random process X(t) is wide-sense stationary with autocorrelation

(a) Find the second moment of the r.v. X(5).

(b) Find the second moment of the r.v. X(5)- X(3).

5.86. Consider a random process X(t) defined by

X(t)=U cost+(V+ 1) sin t -oo < t< oo

where U and V are independent r.v.'s for which

E(U)=E(V =
) 0

(a) Find the autocovariance function Kx<t, s) of X(t).

(b) Is X(t) W SS?