RANDOM PROCESS

CONTENTS:

•CLASSIFICATION OF RANDOM PROCESS

•STATIONARITY

•WSS and SSS PROCESS

•POISSON RANDOM PROCESS

•PURE BIRTH PROCESS

•RENEWAL PROCESS

•MARKOV CHAIN

•TRANSITION PROBILITIES
 CLASSIFICATION OF RANDOM PROCESS
RANDOM PROCESS:
A random process is a collection of random variables {X(s,t)}
that are functions of a real variable, namely time ‘t’ where sєS
and t єT.
• Concepts of deterministic and random processe
stationarity, ergodicity
• Basic properties of a single random process
mean, standard deviation, auto-correlation, spectral density
• joint properties of two or more random processes
correlation, covariance, cross spectral density, simple input-
output relations
 Random processes - Basic concepts
• Deterministic random processes :
• both continuous functions of time (usually), mathematical concepts

• deterministic processes :
physical process is represented by explicit mathematical relation

• Example :
response of a single mass-spring-damper in free vibration in
laboratory
• Random processes :
result of a large number of separate causes. Described in probabilistic
terms and by properties which are averages
 Random processes - basic concepts

• random processes :
fX(x)
x(t)

time, t

• The probability density function describes the general distribution of the

magnitude of the random process, but it gives no information on the
time or frequency content of the process
 Random processes - basic concepts

• Stationary random process :

• Ensemble averages do not vary with time

• Ergodic process :
stationary process in which averages from a single record are the same
as those obtained from averaging over the ensemble

Most stationary random processes can be treated as ergodic

Wind loading from extra - tropical synoptic gales can be treated as

stationary random processes
Wind loading from hurricanes - stationary over shorter periods <2 hours
- non stationary over the duration of the
storm
Wind loading from thunderstorms, tornadoes - non stationary
 Random processes - basic concepts
• Mean value :

x(t)

x

time, t T
1 T
T 0
x  Lim x(t)dt
T 

• The mean value,x , is the height of the rectangular area having the
same area as that under the function x(t)

• Can also be defined as the first moment of the p.d.f. (ref. Lecture 3)
 Random processes - basic concepts
• Mean square value, variance, standard deviation :

x
x(t)

x

time, t T
1 T 2
T 0
mean square value, x  Lim
2
x (t)dt
T 

variance, 
σ 2x  x(t)  x 
2 1 T
T  T 0
 Lim x(t) - x 2
dt
(average of the square of the deviation of x(t) from the mean value,x)

standard deviation, x, is the square root of the variance

 Random processes - basic concepts

• Autocorrelation :
x(t)

time, t T
• The autocorrelation, or autocovariance, describes the general
dependency of x(t) with its value at a short time later, x(t+)

 x ( )  Lim
1 T
T  T 0
  
x(t) - x . x(t  τ) - x dt

The value of x() at  equal to 0 is the variance, x2

Normalized auto-correlation : R()= x()/x2 R(0)= 1

 Random processes - basic concepts
• Autocorrelation :
1

R()

0
Time lag, 

• The autocorrelation for a random process eventually decays to zero at

large 

• The autocorrelation for a sinusoidal process (deterministic) is a cosine

function which does not decay to zero
 Random processes - basic concepts
• Autocorrelation :

1 
T1   R( )d
0
R()

0
Time lag, 
• The area under the normalized autocorrelation function for the
fluctuating wind velocity measured at a point is a measure of the average
time scale of the eddies being carried passed the measurement point,
say T1
• If we assume that the eddies are being swept passed at the mean
velocity, U.T1 is a measure of the average length scale of the eddies

• This is known as the ‘integral length scale’, denoted by lu

 Random processes - basic concepts

• Spectral density :
Sx(n)

frequency, n

• The spectral density, (auto-spectral density, power spectral density,

spectrum) describes the average frequency content of a random process,
x(t) 2 
Basic relationship (1) : σ x  S x (n) dn
0

The quantity Sx(n).n represents the contribution to x2 from the

frequency increment n

Units of Sx(n) : [units of x]2 . sec

 Random processes - basic concepts

• Spectral density :

Basic relationship (2) : 2 2

Sx (n)  Lim  X T (n) 
T  T
 

Where XT(n) is the Fourier Transform of the process x(t) taken over the
time interval -T/2<t<+T/2

The above relationship is the basis for the usual method of

obtaining the spectral density of experimental data

Usually a Fast Fourier Transform (FFT) algorithm is used

 Random processes - basic concepts

• Spectral density :

Basic relationship (3) :
-
Sx (n)  2  x ( )e i 2n dτ

The spectral density is twice the Fourier Transform of the

autocorrelation function

Inverse relationship :
 
i 2n
 0
ρ x ( )  Re al  Sx (n)e  0
dn   Sx (n)cos(2n )dn

Thus the spectral density and auto-correlation are closely linked -

they basically provide the same information about the process
x(t)
 Random processes - basic concepts
• Cross-correlation :
x(t)

x


time, t T
y(t)

y

time, t T

• The cross-correlation function describes the general dependency of x(t)

with another random process y(t+), delayed by a time delay, 
1 T
 
cxy ( )  Lim  x(t) - x . y(t  τ) - y dt
T  T 0

 Random processes - basic concepts

• Covariance :

• The covariance is the cross correlation function with the time delay, ,
set to zero

1 T
c xy (0)  x(t). y(t)  Lim x(t) - x . y(t) - y dt
  
T  T 0

Note that here x'(t) and y'(t) are used to denote the
fluctuating parts of x(t) and y(t) (mean parts subtracted)

(Section 3.3.5 in “Wind loading of structures”)

 Random processes - basic concepts

• Correlation coefficient :

• The correlation coefficient, , is the covariance normalized by the

standard deviations of x and y

x' (t).y' (t)

ρ
σ x .σ y

When x and y are identical to each other, the value of  is +1

(full correlation)

When y(t)=x(t), the value of  is  1

In general,  1<  < +1

 Random processes - basic concepts

• Correlation - application :
• The fluctuating wind loading of a tower depends on the correlation
coefficient between wind velocities and hence wind loads, at various heights

z2
z1

u' (z1 ).u' (z 2 )

For heights, z1, and z2 : ρ(z1 , z 2 ) 
σ u (z1 ).σ u (z 2 )
 Random processes - basic concepts

• Cross spectral density :


By analogy with the spectral density :
-
Sxy (n)  2 cxy ( )e i 2n dτ

The cross spectral density is twice the Fourier Transform of the cross-
correlation function for the processes x(t) and y(t)

The cross-spectral density (cross-spectrum) is a complex number

:
Sxy (n)  C xy (n)  iQ xy (n)

Cxy(n) is the co(-incident) spectral density - (in phase)

Qxy(n) is the quad (-rature) spectral density - (out of phase)
 Random processes - basic concepts

• Normalized co- spectral density :

C xy (n)
 xy (n) 
S x (n).S y (n)

It is effectively a correlation coefficient for fluctuations at frequency, n

Application : Excitation of resonant vibration of structures by

fluctuating wind forces

If x(t) and y(t) are local fluctuating forces acting at different parts
of the structure, xy(n1) describes how well the forces are
correlated (‘synchronized’) at the structural natural frequency, n1
 Random processes - basic concepts
• Input - output relationships :
Input x(t) Output y(t)
Linear system

There are many cases in which it is of interest to know how an input random
process x(t) is modified by a system to give a random output process y(t)

Application : The input is wind force - the output is structural

response (e.g. displacement acceleration, stress). The ‘system’ is
the dynamic characteristics of the structure.

Linear system : 1) output resulting from a sum of inputs, is equal

to the sum of outputs produced by each input individually
(additive property)
Linear system : 2) output produced by a constant times the input,
is equal to the constant times the output produced by the input
alone (homogeneous property)
 Random processes - basic concepts
• Input - output relationships :
Relation between spectral density of output and spectral density of input :
2
S y (n)  A . H(n) .Sx (n)

|H(n)|2 is a transfer function, frequency response function, or ‘admittance’

Sx(n) A.|H(n)|2 Sy(n)

frequency, n

Proof : Bendat & Piersol, Newland

 Random Processes (23)

Consider a random process f(t) of nth order joint p.d.f.

p(x1, x2, …, xn; t1, t2, …, tn).

Note that:
(1)
 n W ( x1 , ..., xn ; t1 , ..., t n )
p( x1 , ..., xn ; t1 , ..., t n ) 
x1    xn

(2) f(t1), f(t2), …, f(tn) are random variables obtained by sampling the
random process f(t) at time t1, t2,…, tn. The x1, x2,…, xn inside p(x1,
x2, …, xn; t1, t2, …, tn) and W(x1, x2, …, xn; t1, t2, …, tn) are not random
variables but are values of the random variable f(t1), f(t2),…, f(tn)
respectively.
 Random Processes (24)

Def: A random process f(t) is said to be stationary in the strict

sense if its statistics (i.e. p.d.f.s) are invariant to a shift  in
the time origin. That is, the 2 processes f(t) and f(t+) have
the same p.d.f.s for any arbitrary .

Consequently, the nth-order p.d.f. must be such that

p(x1, x2, …, xn ; t1, t2, …, tn) = p(x1, x2, …, xn ; t1 +, t2 +, …, tn +).

This implies for a stationary process,

• the 1st-order density p(x, t) is p(x) which is independent of t.
• the 2nd-order density is independent of ,
p(x1, x2 ; t1, t2) = p(x1, x2 ; t1 + , t2 + ) = p(x1, x2 ; t2 – t1).

In other words, the 2nd-order density depends on t2 – t1 (the time

interval between t2 and t1) but not t2 and t1.
 The 2nd-Order Distribution W(x1, x2; t1, t2) (25)

W(x1, x2; t1, t2) of f(t)

f(t)
An experiment is performed n times and t2
x1 t1
at each trial, a time function f(t) is x2 t
observed. Select 4 numbers x1, x2, t1 and f(t)
x1
t2 arbitrary. Let n(x1, x2; t1, t2) be the total
x2 t
number of trial for which the observed
f(t)
function f(t1)  x1 and f(t2)  x2. x1

The 2nd-order distribution W(x1, x2; t1, t2) x2 t

f(t)
x1
n( x1 , x2 ; t1 , t 2 ) x2 t
is lim . f(t)
n  n x1

x2 t

n = 5
n(x1, x2; t1, t2) =
1
W(x1, x2; t1, t2) =
1/5
 The 2nd-Order Distribution W(x1, x2; t1, t2) (26)

W(x1, x2; t1, t2) of f(t+) f(t+)

x1 t2
An experiment is performed n times and at t1 t
x2
each trial, the time function f(t+) is f(t+)
observed. Select 4 numbers x1, x2, t1 and t2 x1

arbitrary. Let n(x1, x2; t1, t2) be the total x2 t

number of trial for which the observed f(t+)

x1
function f(t1+)  x1 and f(t2+)  x2.
x2 t
The 2nd-order distribution W(x1, x2; t1+, t2+) f(t+)
x1

x2 t
n( x1 , x2 ; t1   , t 2   ) f(t+)
is lim x1
n  n
x2 t
n( x1 , x2 ; t1 , t 2 )
which is the same as lim .
n  n n = 5
n(x1, x2; t1+, t2+) =
1
W(x1, x2; t1+, t2+) =
1/5
 Random Processes (27)

Def: A random process, x(t) is said to be stationary of order k iff

p(x1, x2, …, xn ; t1, t2,…, tn) = p(x1, x2, …, xn ; t1+, t2+ ,…, tn+) for n  k .

Def: A random process, x(t) is said to be wide-sense stationary iff

(1) its mean is constant, E[x(t)] =  and
(2) its autocorrelation R() depends on  = t1 - t2, i.e. R() = E[x(t+ ) x(t)].

Note: (1) x(t) is stationary of order 2

x(t) is stationary in the wide-sense

(2) x(t) is Gaussian and stationary in the wide-sense

x(t) is Gaussian and stationary in the strict-sense

(3) x(t) is stationary in the strict-sense

x(t) is stationary in the wide-sense

(4) x(t) is stationary in the strict-sense

x(t) is stationary of order k
 Random Processes (28)
Given a random process x(t) of nth order joint p.d.f.
p(x1, x2, …, xn; t1, t2, …, tn).

Consider the following two statements:

Statement 1: The first order p.d.f. p(x;t) = p(x).
Statement 2: E[x(t)] =  (a constant, i.e. independent of t).

Note that Statement 1 implies Statement 2 but not vice versa.

Prove: statement 2 does not imply statement 1.

Pf: by a counter example where the p.d.f. p(x;t) of x(t) is

p(x;t<0) = uniform distribution with E[x(t)] = 
p(x;t0) = Gaussian distribution with E[x(t)] = .
Statement 2 ( E[x(t)] =  ) is valid but not Statement 1 ( as p(x;t)  p(x) ).
 Random Processes - Example (29)

Prove: (1) = 0 is a necessary condition for the random process

f(t) = sin(t+), where  is a constant and  is a random variable whose
characteristic function is (s) = E[ejs] = E[cos(s)] + j E[sin(s)], to be
stationary in the wide-sense.

Solution: For f(t) to be stationary in the wide-sense, its expected value must
be impendent of t; that is, E[f(t)] = constant.
E[f(t)] = E[sin(t+ )]
= E[sin(t) cos() + cos(t) sin()]
= sin(t) E[cos()] + cos(t) E[sin()]

If f(t) is stationary, the equation will be equal to a constant. This is

possible only when the coefficients of sin(t) & cos (t) are zero, i.e.
E[cos()] = E[sin()] = 0.
Since (1) = E[cos()] + jE[sin()]
 (1) = 0
 Random Processes - Example (30)

Given: a random process x(t) = a cos(t) + b sin(t), where a & b are random
variables and   0.
Prove:
(1) If x(t) is stationary, then E[a] = E[b] =0

(2) x(t) is wide-sense stationary iff

(i) E[a] = E[b] =0
(ii) a & b are uncorrelated
(iii) a & b have equal variance

(3) x(t) is strict-sense stationary iff

(i) E[a] = E[b] =0
(ii) the joint p.d.f. of a & b has circular symmetry,
i.e. p(a,b) = p ( )
which implies p(1,1) = p(2 ,0) = p(0,2)

a 2  b2
 Random Processes - Example (31)
Note:
x(t) = a cos(t) + b sin(t) = cos(t – ),
where  = tan-1(b/a)
a 2  b2 x(t)

3600 t
a b  x(t)
a 2  b2
900
1 0 1 0 cos(t)
t
0 1 1 900 sin(t)

1 1 22 450 cos(t) + sin(t) 

x(t) = a 2  b 2 [ cos cos( t) + sin sin(t) ] a 2  b2 b


a
 Random Processes - Example Q1 (32)

Given: x(t) = a cos(t) + b sin(t),

where a & b are r.v.s and   0 (1)
Prove: If x(t) is stationary, then E[a] = E[b] =0
Proof:
x(t) is stationary (SSS or WSS)
 The mean of the random process x(t)
x(t) is independent of t, that is
E[ x(t) ] = constant t1 t2

 cos(t) E[a] + sin(t) E[b] = constant t

900
 E[a] = E[b] = 0 ……..(2)
t
x(t1)
α

t
x(t2)
 Random Processes - Example Q2 (33)
Given: x(t) = a cos(t) + b sin(t), where a & b are r.v.s and   0.
Prove: x(t) is wide-sense stationary iff
(i) E[ a ] = E[ b ] =0
(ii) a & b are uncorrelated
(iii) a & b have equal variance, i.e. E[ a2 ] = E[ b2 ] = 2
Proof: x(t) is WSS
 E[x(t)] =  and
E[x(t1) x(t2)] = E[x(t+)x(t)] = R()

Consider R() when  = 0 and

t1 =t2 = 0 t1 =t2 = /2
 E[x2(0)] = E[ x2(/2) ] = R(0) ……. (3)

As x(0)= a & x(/2) = b ….…(4)

(3)&(4)  E[a2] = E[b2] = 2 = R(0) ……. (5)
 Random Processes - Example Q2 (34)
Given: x(t) = a cos(t) + b sin(t), where a & b are r.v.s and   0. Def: A random process, x(t) is said to be
Prove: x(t) is wide-sense stationary iff wide-sense stationary iff
(i) E[ a ] = E[ b ] =0 1) its means is constant, E[x(t)] =  and
(ii) a & b are uncorrelated
(iii) a & b have equal variance, i.e. E[ a2 ] = E[ b2 ] = 2. 2) its autocorrelation depends on =t1-t2,
i.e. R() = E[x(t+ ) x(t)].
Proof (continued):
E[x(t+) x(t)] = E[(a cos(t+ )+b sin(t+ ))(a cost + b sint)]
= 2 cos() + E[a b] sin(2t+ )…….(6)

This is independent of t only if E[a b]=0.

E[a b]=0 & (i) imply that a & b are uncorrelated.
Def: Random variables a & b are
Conversely, uncorrelated if 11  E [( a  a ) (b  b )]

i) E[a2] = E[b2] = 2 implies (6).  ab  a b  0

ii) (6) & E[a b] = 0 imply E[x(t+ ) x(t)] = R().

iii) E[a] = E[b] = 0 implies E[x(t)] = .

Together, ii) and iii) implies x(t) is wide-sense stationary.

 Probability Theory - 3 stages (35)
In order to develop a useful theory of probability, it is important to separate
3 stages in the consideration of any real probability.

1. The association of an events with a probability by

(i) experiments and (ii) reasoning.
e.g. P(1) = 1/6

2. Development of the relationship of the probability of an event

with the probabilities of some other events.
e.g. P(1) P(1)

3. The application of the results of stage 1 & stage 2 to the

real world.
The outcome of throwing a dice is
e.g.
governed by the probability theory.
 Random Processes - 3 stages (36)
In order to develop a useful theory of random processes, it is important
to separate 3 stages in the consideration of any real random process.

1. The association of a random process with an n th order joint p.d.f.

p(x1, x2, …, xn; t1, t2, …, tn) by (i) experiments and (ii) reasoning.

e.g. x(t) is stationary of order 2 and its p(x1, x2, …, xn; t1, t2, …, tn) is
Gaussian

2. Development of the relationship of the various p.d.f.s of a number of

random processes.

e.g. x(t) is stationary of order 2  x(t) is stationary in the wide-sense

3. The application of the results of stage 1 & stage 2 to the real world.

e.g. The noise at time t , i.e. x(t) on the

telephone lines in Shatin is a random
process.
 Stationary Random Process (37)
The mean of a random process, x(t) is
(t) = .
 x(t, s=1)
x  p( x; t ) dx
 
t
x(t, s=2)
If the process is stationary, then t
p(x;t) = x(t, s=3)
p(x)
and t
x(t, s=4)
the mean of the random process
(t) = t
• •
 • • t1
x  p( x )dx • •
  t0
=  ( a constant independent of t )
 Ergodicity (38)
x(t, S=1)
How to estimate the mean of a random
process?
t
x(t, S=2)
M
1 t
Ensemble-average =  x (t 0 ,S) x(t, S=3)
M s 1

• dependent on t0 t
x(t, S=4)
• natural way to estimate (t0)
t
• t0 •
1 T • •
Time-average = lim x(t , S ) dt
T  2T T
 • •

• dependent on the outcome S.

• if the process is stationary & E[ |x(t,s)| ] is finite, then
the limit exists for almost every S .

If a stochastic process is ergodic then its ensemble averages

equal appropriate time averages.
 Ergodic Random Processes (39)

Def: A random process x(t) is said to be ergodic if all its statistics can be
determined from a single sample of the process.

Thus, the nth-order p.d.f. of t2

the process can be deduced
t1 t
by examining either

(i) one member of the process over

a long time (time average) or t

(ii) x(t1), …, x(tn ) , the process at

t
t1 , …, tn many times (ensemble average).

If a process is ergodic,
then its time average & ensemble average are equal.
 Definition

What is A Poisson Process?

The Poisson Process is a counting that counts the number of
occurrences of some specific event through time

Examples:
- Number of customers arriving to a counter
- Number of calls received at a telephone exchange
- Number of packets entering a queue

40
 The Poisson Process
1st Event 2nd Event 3rd Event 4th Event
Occurs Occurs Occurs Occurs
X1 X2 X3 X4

4
time
1 2 3
t=0 S1   Xi S2   Xi S3   Xi S 4   Xi
i 1 i 1 i 1 i 1

• X1, X2, … represent a sequence of +ve independent random variables with

identical distribution
• Xn depicts the time elapsed between the (n-1)th event and nth event
occurrences
• Sn depicts a random variable for the time at which the nth event occurs
• Define N(t) as the number of events that have occurred up to some arbitrary
time t.
The counting process { N(t), t>0 } is called a Poisson process if the inter-
occurrence times X1, X2, … follow the exponential distribution
41
 The Poisson Process: Example

For some reason, you decide everyday at 3:00 PM to go

to the bus stop and count the number of buses that
arrive. You record the number of buses that have passed
after 10 minutes

Sunday N (t=10 min) = 2

1st Bus Arrival 2nd Bus 3rd Bus 4th Bus
Arrival Arrival Arrival
X1=5 min X2=4 min X3=7 min X4=2 min

time
42
t=0 S1 = 5 min S2 = 9 min S3 = 16 min S4 = 18 min
 The Poisson Process: Example

For some reason, you decide everyday at 3:00 PM to go

to the bus stop and count the number of buses that
arrive. You record the number of buses that have passed
after 10 minutes

Monday N (t=10 min) =4

1st Bus Arrival 2nd Bus 3rd Bus 4th Bus 5th Bus
Arrival Arrival Arrival Arrival
X1=1 min X2=2 min X3=4 min X4=2 min X5=6 min

time
43
t=0 S1 = 1 min S2 = 3 min S3 = 7 min S4 = 9 min S5 = 15 min
 The Poisson Process: Example

For some reason, you decide everyday at 3:00 PM to go

to the bus stop and count the number of buses that
arrive. You record the number of buses that have passed
after 10 minutes

Tuesday N (t=10 min) =1

1st Bus Arrival 2nd Bus
Arrival
X1=10 min X2=6 min

time
44
t=0 S1 = 10 min S2 = 16 min
The Poisson Process: Example

Given that Xi follow an exponential distribution then N(t=10)

follows a Poisson Distribution 45
PROPERTIES OF POISSON PROCESS

 The Poisson process is not a stationary process. It is

vivid from the expressions of moments of Poisson
process, that they are time dependent.

 The Poisson process is a Markov Process.

 The difference of two independent Poisson processes

is not Poisson.
Problems:
[Link] that customers arrive at a bank according to a
Poisson process with a mean rate of 3 per minute; find the
probability that dsuring a time interval of 2 min (i) exactly 4
customers arrive and (ii)more than 4 customers arrive.

2. A machine goes out of order, whenever a component fails.

The failure of this part follows a Poisson process with a mean
rate of 1 per week. Find the probability that 2 weeks have
elapsed since last failure. If there are 5 spare parts of this
component in an inventory and that the next supply is not due
in 10 weeks, find the probability that the machine will not be
out of order in the next 10 weeks.
 The Pure-Birth Process

• When deriving the Poisson distribution we assumed that the probability

of an event in a time interval is independent of the number of events that
have occurred up to time t
• This assumption does not always hold in biological applications
• In the pure-birth process it is assumed that given the value of a random
variable at time t is j, the probability that it increases to j+1 in a given
time interval (t,t+h) is λjh
• The Poisson case arises when λj is independent of j and is just written as λ
• As with the Poisson process we can arrive at a set of differential
equations for the probability that the random variable takes the value j at
time t
 The Pure-Birth Process (cont)

• One example of an application of the Pure-Birth

process is the Yule process, where it is assumed that
λj= jλ
– The motivation for this process arises from populations
where if the size of the population is j the probability that
it increases to size j+1 is proportional to j
• For this case, the solution to the differential
equations given before is:
 The Pure-Birth Process (cont)
• Another example of the application of the Pure-Birth process
comes from polymerase chain reaction (PCR)
• In PCR, sequential additions of base pairs to a primer occur to
create the product
• For this process, λj=m-j, which implies that once the length of
the product reaches m no further increase in length is
possible
• With this condition, the solution is:

• Neither this example nor the last follow the Poisson

distribution, which shows the importance of verifying the
event independence assumption
 Example: pure birth process
• Exponential interarrival times, mean 1/

• Arrival process is Poisson process

• Markov chain?
• Transition rates : let t0<t1<…<tn<t
P( X (t  h)  j  1 | X (t )  j , X (t 0)  j 0,..., X (tn)  jn) 
P( X (t  h)  j  1 | X (t )  j )  h  o( h )
P( X (t  h)  j  2 | X (t )  j )  o( h)
P( X (t  h)  j | X (t )  j )  1  h  o( h)

  k  j 1
q( j, k )  
  k  j

• Kolmogorov forward equations for P(X(0)=0)=1

dPt (0, j )
 Pt (0, j  1)  Pt (0, j )
dt
dPt (0,0)
 Pt (0, j )
dt

• Solution for P(X(0)=0)=1

(t ) j t
Pt (0, j )  e , j  0,1,2,..., t  0
j!
 Markov Process

• A continuous time stochastic process {Xt, t  0}

with state space E is called a Markov process
provided that
P{ X s t  j | X s  i, X u  xu , 0  u  s}
 P( X s t  j | X s  i}
• for all states i, j  E and all s, t  0.

known

0 s s+t
 Markov Process

• We restrict ourselves to Markov processes for which

the state space E = {0, 1, 2, …}, and such that the
conditional probabilities

Pij (t )  P{ X s t  j | X s  i}

• are independent of s. Such a Markov process is called

time-homogeneous.
• Pij(t) is called the transition function of the Markov
process X.
 Markov Process - Example

• Let X be a Markov process with

 r0 (t ) r1 (t ) r2 (t ) 
 
 r0 (t ) r1 (t ) 

P(t )   
r0 (t ) 
 
 0
• where  

e t (t ) j i
Pij (t )  r j i (t )  , 0i j
( j  i)!
• for some  > 0. X is a Poisson process.
Problems:
1. A raining process is considered as a two state Markov
chain. If it rains, it is considered to be in state 0 and of it
does not rain, the chain is in state 1. The transition
probability of the Markov chain is defined as P =

Find the probability that it will rain for three days from
today assuming that it is raining today. Find also the
unconditional probability that it will rain after three days.
Assume the initial probabilities of state 0 and state 1 as
0.4 and 0.6 respectively.
Ans: P(x3 = 0 ) = 0.4P 003 + 0.6P 103 = 0.3376
2. Evaluate P(2),P(3), ….,P(10) for the homogeneous Markov
chain given by the transition probability matrix
P(1) =

Find also the probabilities of each state in every step transition.

Assume the initial probabilities of the states as 0.5, 0.3 and 0.2
respectively.
 Chapman-Kolmogorov Equations
• Theorem 3. For i, j  E, t, s  0,

P ij ( s  t )   Pik ( s) Pkj (t ).
kE
Realization of a Markov Process

Xt()
7
S4
6
S2
5

4
S3
3
S1 S5
2
S0
1

0
t
T0 T1 T2 T3 T4 T5
 Time Spent in a State
• Theorem 4. Let t  0, and n satisfy Tn ≤ t < Tn+1, and let Wt =
Tn+1 – t. Let i  E, u  0, and define
G(u)  P{Wt  u | X t  i} .
• Then
G (u  v)  G (u )G (v).
• Note: This implies that the distribution of time remaining
in a state is exponentially distributed, regardless of the
time already spent in that state.
Wt

Tn t t+u Tn+1
 Time Spent in a State

• Proof: We first note that due to the time homogeneity of X,

G(u) is independent of t. If we fix i, then we have

G (u  v)  P{Wt  u  v | X t  i}
 P{Wt  u , W t u  v | X t  i}
 P{Wt  u | X t  i}P{W t u  v | Wt  u , X t  i}
 P{Wt  u | X t  i}P{Wt u  v | X t u  i}
 G (u ) G (v).
 An Alternative Characterization of a
Markov Process
• Theorem 5. Let X ={Xt, t  0} be a Markov process. Let T0, T1, …,
be the successive state transition times and let S0, S1, …, be
the successive states visited by X. There exists some number
i such that for any non-negative integer n, for any j  E, and t
> 0,
P{S n1  j, Tn1  Tn  t | S 0 ,, S n1 , S n  i ; T0 ,, Tn }
 Q(i, j ) e  it

• where Q ij  0, Qii  0,  1.
Q ij
jE
 An Alternative Characterization of
a Markov Process

• This implies that the successive states visited

by a Markov process form a Markov chain with
transition matrix Q.

• A Markov process is irreducible recurrent if its

underlying Markov chain is irreducible
recurrent.
 Kolmogorov Equations

• Theorem 6.
Pij (t )   i Qik Pkj (t )  iP ij (t )
k i

• and, under suitable regularity conditions,

Pij (t )   k Qkj Pik (t )  jP ij (t ) .

k j

• These are Kolmogorov’s Backward and Forward

Equations.
 Kolmogorov Equations

• Proof (Forward Equation): For t, h  0,

Pij (t  h)   Pik (t )  k h Qkj  P ij (t ) 1  v j h   o(h) .

k j

• Hence
Pij (t  h)  Pij (t ) o( h)
  k Qkj Pik (t )  jP ij (t )  .
h k j h

• Taking the limit as h  0, we get our result.

 Transition Probabilities

• Suppose a state has N possible values

– Xt=s1, Xt=s2,….., Xt=sN.
• N2 Transition Probabilities
– P(Xt=si|Xt-1=sj), 1≤ i, j ≤N
• The transition probabilities can be
represented as a NxN matrix or a directed
graph.
• Example: Gambler’s Ruin
 Transition Probabilities and the
Transition Probability Matrix
• If at time t a Markovian random variable is in state Ej the
probability that at time t+1 it is in state Ek is denoted by pjk,
which is the transition probability from Ej to Ek
– This notion implicitly contains both the properties mentioned before
• A transition probability matrix P of a Markov chain contains
all of the transition probabilities of that chain
 Transition Probabilities and the
Transition Probability Matrix (cont)
• It is also assumed that there is a initial probability distribution
for the states in the process
– This means that there is a probability πi that at the initial time point the
Markovian random variable is in state Ei
• To find the probability that the Markov chain process is in state
Ej two time steps after being in state Ei you must consider all
the possible intermediate steps after one time step that the
process could be in

• This can also be done for the whole process at once by matrix
multiplication, the notation Pn is used to denote an n-step
transition probability matrix
 Markov Chains with Absorbing
States
• A Markov chain with an absorbing state can be
recognized by the appearance of a 1 along the
main diagonal of its transition probability
matrix
• A Markov chain with an absorbing state will
eventually enter that state and never leave it
• Markov chains with absorbing states bring up
new questions, which will be addressed later,
but for now we will only consider Markov
chains without absorbing states
 Markov Chains with No Absorbing
States
• In addition to having no absorbing states, the Markov models
that we will consider are also finite, aperiodic, and irreducible
– Finite means that there are a finite number of possible states
– Aperiodic means that there is no state such that a return to that state is
possible only t0, 2t0, 3t0, … transitions later, where t0 > 1

– Irreducible means that any state can eventually be reached from any
other state, but not necessarily in one step
 Stationary Distributions

• Let the probability that at time t a Markov chain process is in

state Ej be φj
• This means that the probability that at time t+1 the process is
in state Ej is given by

• If we assume that these two probabilities are equal then we

get:

• If this is the case, then the process is said to be stationary,

that is, from time t onwards, the probability of the process
being in state Ej does not change
 Stationary Distributions (cont)

• If the row vector φ’ is defined by:

• Then we get the following from (4.25)

• The row vector must also satisfy

• With these equations we can find the stationary

distribution when it exists
– Note that (4.27) generates one redundant equation that
can be omitted
 Stationary Distribution Example

• We are given a Markov chain with the following transition probability matrix

• Using (4.27) and (4.28) we can form a set of equations to solve

• The solution to these equations is:

• This means that over a long time period a random variable with the given transition
matrix should spend about 24.14% of the time in state E1, 38.51% of the time in
state E2, etc.
 Stationary Distribution Example (cont)

• With matrix multiplication we can see how quickly the Markov

chain process would reach the stationary distribution

• From this it appears that the stationary distribution is

approximately reached after 16 time steps
 The Graphical Representation of a Markov Chain

• It can be convenient to represent a Markov chain by a directed graph, using

the states as nodes and the transition probabilities as edges

• Additionally, start and end states can be added as needed

• The graph structure without probabilities added is called the topology
• These definitions are used later in the book to discuss hidden Markov
models
 What can Markov Chains Do?

• Example: Gambler’s Ruin

– The probability of a particular sequence
• 3, 4, 3, 2, 3, 2, 1, 0
– The probability of success for the gambler
– The average number of bets the gambler will
make.
 Working Backwards

287.5A. Assistant 0.2 325

B. Associate
0.2
Prof.: 20 Prof.: 60
0.7
0.6 0.2
0.2 0.6
300 T. Tenured
Prof.: 90

50
S. Out on the
0.3
0.2
Street: 10 D. Dead: 0
0
0.8 1.0
 Ruin Chain

2/3 1
0 1 2 3 4 5
+1 1
1
1/3
 Gambling Time Chain

+1 2/3 1
0 1 2 3 4 5
1
1/3
Refs. :
1.J.S. Bendat and A.G. Piersol “Random data: analysis and
measurement procedures” J. Wiley, 3rd ed, 2000.
2.D.E. Newland “Introduction to Random Vibrations, Spectral and
Wavelet Analysis” Addison-Wesley 3rd ed. 1996
3.
[Link]/~boucherierj/.../[Link]
4. [Link]/Notes/Akinpelu/Markov%[Link]
5. [Link]/~lindek/650/Slides/[Link]