Chapter 1

Poisson Processes

1.1 The Basic Poisson Process

The Poisson Process is basically a counting processs. A Poisson Process on
the interval [0 , ) counts the number of times some primitive event has
occurred during the time interval [0 , t]. The following assumptions are made
about the Process N(t).

(i). The distribution of N(t + h) N(t) is the same for each h > 0, i.e. is
independent of t.

(ii). The random variables N(tj ) N(tj ) are mutually independent if the
intervals [tj , tj ] are nonoverlapping.

(iii). N(0) = 0, N(t) is integer valued, right continuous and nondecreasing

in t, with Probability 1.

(iv). P [N(t + h) N(t) 2 ] = P [N(h) 2 ] = o(h) as h 0.

Theorem 1.1. Under the above assumptions, the process N() has the fol-
lowing additional properties.

(1). With probability 1, N(t) is a step function that increases in steps of

size 1.

(2). There exists a number 0 such that the distribution of N(t+s)N(s)

has a Poisson distribution with parameter t.

1
2 CHAPTER 1. POISSON PROCESSES

(3). The gaps 1 , 2 , between successive jumps are independent identically

distributed random variables with the exponential distribution
(
exp[ x] for x 0
P {j x} = (1.1)
1 for x 0

Proof. Let us divide the interval [0 , T ] into n equal parts and compute the
expected number of intervals with N( (k+1)T n
) N( kT
n
) 2. This expected
value is equal to
 T  1
nP N( ) 2 = n . o( ) = o(1) as n
n n
there by proving property (1).
Because of right continuity we have
P [N(t) 1] 0 as t 0
proving that the distribution of N(t) is infinitesimal as t 0. By the
independence of the increments over disjoint intervals, N(t) is approximately
the sum of [nt] independent copies of N( n1 ).
  [nt]
E exp[N(t)] = lim E exp[N( )]
n n
  1 [nt]
= lim E exp[N( )] (1.2)
n n
= exp[tg()] (1.3)
where
 
  1 
g() = lim n 1 E exp[N( )]
n n
  1 
= lim n E 1 exp[N( )]
n n
 1 1 
= lim n (1 e )P [N( ) = 1] + o( )
n n n
= (1 e ) (1.4)
where
1
= lim n P [N( ) = 1]. (1.5)
n n
1.1. THE BASIC POISSON PROCESS 3

The limit in (1.5) must necessarily

 exist because the limit in (1.3) clearly
exists. The positivity of E exp[N(t)] and the identity (1.4) guarantees
the finiteness of the limit in (1.5). The formulas (1.4) and (1.5) together
identify the distribution of N(t) as the Poisson distribution with parameter
t, thereby proving property (2).
Finally, we turn to the proof of prpoerty (3). First let us prove that 1
has the right distribution.
P [1 > x] = P [N(x) = 0 ] = ex
because of the Poisson distribution. We will prove 1 is a regenerative time
in the sense that N(1 + t) N(1 ) = N(1 + t) 1 is again a Poisson Process
independent of 1 . This will prove that 2 will have the same distribution as
1 and will be independent of it. Repeating the step and induction on n will
complete the proof. Let be a stopping time that takes a countable set of
values {vj }. Since the set = vj is measurable with respect to {N(t) : t
vj }, the process N(t + vj ) N(vj ) is independent of the set = vj , and is
conditionally again a Poisson Process. Therefore for such a , N( +t)N( )
is again a Poisson process independent of . Finally, 1 is a stopping time
and for any k, (k) = [k1k]+1 is a stopping time that takes only a countable
number of values. Therefore N( (k) + t) N( (k) ) is a Poisson Process with
parameter that is independent of (k) . We let k . Because (k) 1 ,
and the process is right continuous we are done.
Remark 1.1. What we have proved is that if P is a measure on the space of
nondecreasing right continuous functions on [0, ) satisfying the properties
listed in the assumptions of Theorem 1.1, then P = P is determined by a
single parameter and the additional properties (1)-(3) of Theorem 1.1 will
be valid for it. The process P is referred to as the Poisson process with
parameter or rate .
Exercise 1.1. Alternate proof of property (3) of Theorem 1.1. Let 0 be
arbitrary. The processes
M (t) = exp[N(t) t(e 1)]
are martingales with repect to ( , Ft , P ) and Doobs stopping theorem pro-
vides the relation
E{M ( + t)|F } = M ( ) a.e.
Turn it into a proof that 1 is regenerative.
4 CHAPTER 1. POISSON PROCESSES

Exercise 1.2. Verify that for any Poisson process with parameter

N(t) and [N(t) t]2 t

are martingales with respect to ( , Ft , P ), where

Ft = {N(s) : 0 s t}

Exercise 1.3. The distribution of 1 + + k+1 is a Gamma distribution

k
with density k! ex xk1 . Why does it look like the Poissson probability for
k jumps?

1.2 Compound Poisson Processes.

Suppose that X1 , X2 , Xn is a sequence of independent identically dis-
tributed random variables with a common distribution having partial sums
Sn = X1 + X2 + + Xn . We define a proces X(t) by

X(t) = SN (t) .

Each time the Poisson Process N(t) jumps by 1, the process X(t) jumps by
a random amount which has distribution . The jumps at different instances
are independent. Such a process X(t) inherits the independent increments
property from N(t). For any collection of nonoverlapping intervals [tj , tj ] the
increments X(tj )X(tj ) are independent random variables. The distribution
of any increment X(t + s) X(s) is that of XN (t) , and is calculated to be
the distribution of Sn where n is random and has a Poisson distribution with
parameter t.
X (t)j
E{exp[i y X(t)]} = et (y)]j = et et (y)
[
= et[(y)1]
j
j!
Z
= exp[t (ei y x 1) d(x)]

Inother words X(t) has an infinitely divisible distribution with a Levy mea-
sure given by t . If we denote by M = then
Z
E{exp[i y X(t)]} = exp[t (ei y x 1) dM(x)]
1.3. INFINITE NUMBER OF SMALL JUMPS. 5

Exercise: Assuming that has two moments, show that are constants A and
2
B such that X(t)At and [X(t)At]
R Bt
R are martingales.
R 2 Compute R A2 and
B in terms of and . [A = x dM = x d ; B = x dM = x d ]

1.3 Infinite number of small jumps.

Where as a Poisson process cannot have an infinite number of jumps in a
finite interval, once we start considering compound Poisson processes we can
in principle sum an infinite number of small jumps so that we still have a
finite answer. For example suppose Xk (t) is a compound Poisson Process
that corresponds to k k = Mk .
Z
E{Xk (t)} = t x dMk (x)

and Z
V ar[Xk (t)] = t x2 dMk (x)

Let us take Xk (t) to be mutually independent processes with independent

increments and try to sum up
X
X(t) = Xk (t)
k

for each t. If the sum exists then it is a process with independent increments.
In fact we can do a little better. We may center these processes with suitable
constants {ak }, and write
X
X(t) = [Xk (t) ak t]
k

to help in convergence. We shall assume that

XZ x2
2
dMk (x) <
k
1 + x

which amounts to two conditions

X
Mk [|x| 1] <
k
6 CHAPTER 1. POISSON PROCESSES

and
XZ
x2 dMk (x) <
k |x|1

We can always decompose any M as M1 + M2 and this will result in a de-

composition of the process X(t) = X1 (t) + X2 (t), two mutually independent
processes with independent increments corresponding to M1 and M2 respec-
(1) (2)
tively. It is better for us to decompose each Mk as Mk + Mk corresponding
to jumps of size |x| 1 and |x| > 1.
X (2)
M= Mk
k

sums to a finite measure and offers no difficulty. The process

X (2)
X (2) (t) = Xk (t)
k

exists very nicely because

(2)
(2) (2)
P {Xk (t) 6= 0} 1 etMk [ |x|>1 ]
tMk [|x| > 1]

and
(2)
X
P {Xk (t) 6= 0} <
k
P (1)
Borel-Cantelli does it! As for a discussion of k Xk (t), it is now clear
(1)
that we can assume that Mk [ |x| > 1 ] = 0 for every k. If we take ak =
R (1)
E{Xk (1)} = x dMk (x),
Z
(1) (2)
E{[Xk (t) ak t] } = x2 dMk (x)
2

and by the two-series theorem

(1)
X
[Xk (t) ak t]
k

converges almost surely. A simple application of Doobs inequality yields

in fact almost sure uniform convergence in finite time intervals. If we now
reassemble the pieces we see that
1.3. INFINITE NUMBER OF SMALL JUMPS. 7

 Z Z 
i y X(t) iy x iyx
E{e } = exp t (e 1 i y x)dM(x) + (e 1)dM(x)
|x|1 |x|>1

which is essentially the same as Levy-Khintchine representation for infinitely

divisible distributions except for the Gaussian term that is missing. That is
the continuous part, that cannot be built from jumps and needs the Brownian
Motion or Wiener Process.
8 CHAPTER 1. POISSON PROCESSES
Chapter 2

Continuous time Markov

Processes

2.1 Jump Markov Processes.

If we have a Markov Chain {Xn } on a state space X, with transition probabil-
ities (x , dy), and a Poisson Process N(t) with intensity , we can combine
the two to define a continuous time Markov process x(t) with X as state
space by the formula
x(t) = XN (t)
The transition probabilities of this Markov process are given by

Px {x(t) A} = P {x(t) A|x(0) = x} = p(t , x , A)

k
t (t)
X
= e (k) (x , A)
k!
k=1

Because of the Markov property of {Xn } and the independence of the

increments of N(t) it is not difficult to see that

P {x(t) A|Fs } = P {XN (t)N (s) A|X0 = XN (s) }

= P {XN (ts) A|X0 = x(s)}
= p(t s , x(s) , A)

thereby proving the Markov property of x(t).

9
10 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

In general, if we want to define a Markov process on a state space X, we

need the transition probabilities p(t , x , A) defined for t > 0, x X and A
B, a - field of measurable subsets of X. It is natural to define p(0 , x , A) =
A (x). For each t > 0, p(t , , ) will be a transition probability from X X
and the collection will have to satisfy the Chapman-Kolmogorov equations
Z
p(t + s , x , A) = p(s , y , A) p(t , x , dy)
X

Given such a collection, for each starting point x X, we can define a con-
sistent family of finite dimensional distributions on the space of trjectories
{x() : [0 , ) X}. On the -field F (t1 , tk ) corersponding to the times
t1 < < tk we first define it for rectangles [x() : x(tj ) Aj , j = 1 k ]
Z Z
Px {kj=1 [x(tj ) Aj ]} = p(t1 , x , dy1) p(tk tk1 , x , dyk )
A1 Ak

The measure is then extended from rectangles to arbitrary sets in the product
-fileld F (t1 , tk ). The consistency of these finite dimnsional distributions
is a consequence of the Chapman-Kolmogorov property. Once we have con-
sistency, a Theorem of A.Tulcea and I.Tulcea guarantees the existence of a
measure Px on the -field F generated by all the F (t1 , tk ). In our case
using the fact that for any n, m 0
Z
(n) (x , dy)m(y , A) = (n+m) (x , A)
X

we can deduce tha Chapman-Kolmogorov equations. The process itself lives

on the space of step functions with values in X. The trajectories wait for an
exponential waiting time with parameter and, if they are at x, jump to y
with probability (x , dy).

Remark 1. If the Markov chain is a random walk on R with transition

probability
(x , A) = (A x)

then the Markov Process is a compound Poisson process with a Levy measure
.
2.2. SEMIGROUPS OF OPERATORS. 11

2.2 Semigroups of Operators.

Any Markov transition function p(t , x , dy) defines an operator
Z
(Tt f )(x) = f (y) p(t , x , dy)
X

from the space B of bounded measurable functions on X into itself. {Tt } has
the following properties.
1. For each t 0, Tt is a bounded linear operator from B B and kTt k 1.
In fact, because Tt 1 = 1, kTt k = 1. T0 = I, the identity operator and for any
t, s 0, Tt+s = Tt Ts = Ts Tt .
2. Tt maps non-negative functions into non-negative functions.
3. For any t 0,

X (t)k k
Tt = et
k=0
k!

where is the operator

Z
(f )(x) = f (y)(x , dy)
X

It is clear that we can write

Tt = et exp[t] = exp[ t[ I] = exp[tL]

 

where L = [ I].
Such families are called semigroups of operators and L is called the in-
finitesimal generator of the semigroup. In our case we can recover L from Tt
by the formula
Tt I
L = lim
t0 t
From the expansion of Tt in powers of this relationship is easy to derive.
It is valid in the strongest sense. As operators one can check that

Tt I
k Lk 0
t
12 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

as t 0. The operator L contains all the relevent information regarding the

Markov Process. In the case of Processes with independent increments with
lots of small jumps (but with out centering)
Z
(Lf )(x) = [f (x + y) f (x)]M(dy)
R

where M(dy) is an infinite measure that intgrates |x| near 0. For L to be well
defined for f we need some thing like a Lipshitz condition on f . Otherwise
Lf may not be defined. In this case L is not a bounded operator and the
expansion in powers of L is very suspect.
Although we have only looked at operators of the form
Z
(Lf )(x) = [f (y) f (x)](x , dy)
X

as potential candidates of generators of Markov Processes one can see that

operators of the form
Z
(Lf )(x) = a(x) [f (y) f (x)](x , dy)
X

where a(x) is a bounded non-negative function work just as well. It is not

all that different. We pick > 0 such that a(x) for all x. Redefine

, A) = a(x) (x , A) + (1 a(x) )A (x)

(x

so that
Z Z
(Lf )(x) = a(x) [f (y) f (x)](x , dy) = , dy)
[f (y) f (x)](x
X X

We have allowed for the possibility of not jumping at the exponential time
with some probability and waiting for the next chance therby effectively
reducing the jump rate, to different levels at different points.
If X is a finite set {1, , k} then L has a matrix reperesentation
L = {ai,j } (1)
and if pi,j (t) are the transition probabilities at time t, one can check that for
i 6= j
pi,j (t)
ai,j = lim 0 (2)
t0 t
2.2. SEMIGROUPS OF OPERATORS. 13

and
pi,i (t) 1
ai,i = lim 0
t0 t
P
Also j pi,j (t) 1 leads to
X
ai,j = 0 i = 1, , k. (3)
j

Such matrices have an interpretation that is important. The last property is

simply the fact that (L1)(x) 0. If f is a function on the state space and
f (x0 ) is the minimum of the function then (Tt f )(x0 ) being an average of f is
atleast f (x0 ). The inequality (Tt f )(x0 ) f (x0 ) leads, upon differentiation at
t = 0, to (Lf )(x0 ) 0. This is called the maximum principle (although we
have stated it for the minimum). One can verify that for matrices L = {ai,j }
the maximum principle is valid if and only if properties (1), (2), and (3) are
valid.
The converse is valid as well. If L is a matrix satsfying properties (1), (2)
and (3) then we can define P (t) = {pi,j (t)}, by

X (tL)k
P (t) = exp[tL] = et
k=0
k!

and verify that P (t) can infact serve as the transition probabilities of a
Markov Process on the state space X = {1, , k.}. If ai,j > 0 i 6= j,
it is easy to see that P (t) is a transition matrix provided t is small. But
P (t) = [P ( nt )]n and now P (t) is seen to be a stochastic matrix for all t > 0.
(n)
The case when ai,j 0, i 6= j is handled by approximating it by {ai,j }
(n)
with ai,j > 0, i 6= j.
Exercise: If P (t) are stochatic matrices that satisfy P (t + s) = P (t)P (s) =
P (s)P (t) for all t, s > 0 and P (t) I as t 0, then show that

P (t) I
L = lim
t0 t

exists and satisfies (1), (2) and (3).

Example: Birth and Death Processes. Imagine a population with a size that
can be any nonnegative integer. The state space X = Z + = {n : n 0}. If
14 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

the current size of the population is n, either a birth or death can take place
and change the population to n 1. Let us denote the birth rate by n and
the death rate by n . This is interpreted as

an,n+1 = n for n 0

an,n1 = n for n 1
and of course 0 = 0 and

an,n = (n + n ) for n 0.

If each individual gives birth at rate independently of others, then n = n.

Similarly if the death rate is for each individual we have n = n. For a
queue with a single server where the arrival time and the service time are
exponetial n = for n 0 and n = for n 1.

2.3 Markov Processes and Martingales.

Suppose L is the bounded operator
Z
(Lf )(x) = a(x) [f (y) f (x)](x , dy)
X

where a(x) is a bounded measurable function and is a transition probability

on X. Let T (t) = exp[t L] be the operators
Z
(Tt f )(x) = f (y) p(t , x , dy)
X

where p(t , x , dy) are the transition probabilities corresponding to L. We swa

earlier by differentiating term by term in the expansion

X (t L)k
Tt =
k=0
k!

of Tt in powers of L that
d Tt
= Tt L = L Tt
dt
2.3. MARKOV PROCESSES AND MARTINGALES. 15

In particular Z t
Tt f f = Ts L f ds
0
or  Z t
 

Ex f (x(t)) f (x(0)) (Lf )(x(s)) dsF0 = 0
0

If we use the homogeniety in time

 Z t  

Ex f (x(t)) f (x(s)) (Lf )(x()) d Fs = 0
s

Thus Z t
Mf (t) = f (x(t)) f (x(0)) (Lf )(x()) d
0
is a Martingale with respect to any Markov process Px with generator L
starting from an arbitrary point x X. By a similar argument one can show
that for any ,
Z t
t
e f (x(t)) f (x(0)) e [(Lf ) f ](x()) d
0

is again a martingale. If A is ameasurable set then

A = {inf t : x(t) A}

is seen to be a stopping time and if () is finite then x( ) A. Note

[ [
{A t} = {x(s) A} {x(t) A}
st
s rational

Lemma 2.1. For > 0 the function

U(x) = Ex e A f (x(A ))}



is the unique solution of

(LU)(x) = U(x) for x Ac

with U(x) = f (x) on A.

16 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

Proof. Clearly for x A, A = 0 a.e. Px and U(x) = f (x). For x

/ A,
starting from
U(x) = Ex {eA f (x( ))}
and conditioning with respect to F where

= {inf t : x(t) 6= x(0)}

we get

U(x) = Ex {e Ex( ) {eA f (x(A ))}

= Ex {e U(x( ))}
= Ex {e }Ex {U(x( ))}
a(x)
Z
= U(y)(x , dy)
+ a(x) X

We can rewrite this as

Z
( + a(x))U(x) = a(x) U(y)(x , dy)
X

or Z
(LU)(x) = a(x) [U(y) U(x)](x , dy) = U(x).
X
Conversely if U solves LU = U on Ac with U = f on A, we know that
Z t
t
e U(x(t)) U(x(0)) [LU U](x(s)) ds
0

is a Px martingale. We apply Doobs stopping theorem with the stopping

time A . Because (LU)(x(s) U(x(s)) = 0 for 0 s A and U(x(A )) =
f (x(A )), we conclude that

U(x) = Ex {eA f (x(A ))}

proving uniqueness.
There are some other related equations which have unuique solutions
expressible in terms of the process. For instance

U LU = g for x A
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 17

with U = f for x Ac can be solved uniquely and the solution is given by

 Z A 
A s
U(x) = Ex e f (x(A )) + e g(x(s)) ds
0

To solve the equation

LU = 0 for x A

uniquely with U = f for x Ac we require the assumption

Px {A < } = 1

for x A and to solve

LU = g for x A
uniquely with U = f for x Ac we need the assumption

Ex {A } <

for x A.

2.4 Explosion, Recurrence and Transience.

Let us consider a simple birth process where n = (n + 1)2 and n = 0. If the
process starts at 0, it moves successively through 1, 2, 3, waiting for an
1
exponential time n at n with E{n } = (n+1) 2 for n 0. A simple calculation

shows that
X X 1
E{n } = 2
<
n=0 n=0
(n + 1)
and by Fubinis theorem

X
n = <
n=0

a.e. The process will reach at time which is finite a.e. We say that
explosion takes place in finite time with probability 1. This can happen with
any Markov Process that we want to construct with
Z
(Lf )(x) = a(x) [f (y) f (x)] (x , dy)
X
18 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

if the function a() is unbounded. If is the explosion time i.e. the first time
when we have an infinite number of jumps, the process is well defined upto
that time by the canonical construction. If > 0 is any constant, we define

U (x) = Ex {e }

Then 0 U(x) < 1 for each x X and there is no explosion if and only if
U(x) 0 on X. If 1 is the time of the first jump then U () satisfies

 
1
U (x) = Ex e U(x(1 ))

a(x)
Z
= U (y) (x , dy)
a(x) + X

This can be rewritten as

(LU )(x) = U (x) (1)

which is valid for every x X. Conversely if U() is any solution of (1) with
0 U(x) 1 then
 

U(x) = Ex e U(x( ))
  
1 1
= Ex e Ex(1 ) e U(x(1 ))
 
2
= Ex e U(x(2 ))

 
n
= Ex e U(x(n ))

where n is the time of the n-th jump. Therefore

U(x) Ex {en }

for every n and letting n

U(x) Ex {e }
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 19

Explosion is equivalent to the existence of a nonnegative bounded solution of

(1). We can always normalize to get a function that satisfies 0 U(x) 1.
We do not really need a solution.
 

U(x) Ex e U(x( ))

will suffice instead of

 

U(x) = Ex e U(x( ))

because this will lead to the inequlity

 
n
U(x(n )) Ex en

U(x) Ex e

which is just as good. So a necessary and sufficient condition for explosion

is the existence of a nonzero function U() with 0 U(x) 1 for all x X
that satisfies
(LU)(x) U(x)
for some > 0. The conditions are equivalent for different values of > 0.
The nonexistence of a function U is harder to check. If there is a nonnegative
function U() on X, that satisfies

(LU)(x) U(x)

for some > 0 and U(x) whenever a(x) then we do not have
explosion. To see this we note that
 
n
U(x) Ex e U(x(n ))

We know that when n either n or a(x(n )) almost surely.

By our assumption U(x(n )) whenever a(x(n )) . But the bound
does not allow U(x(n )) while n remains bounded.
In any case if L is unbounded we canot use the expansion

X (tL)j
Tt =
j=0
j!
20 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

and if there is explosion Tt is not well determined by L i.e by a() and

, (x dy).

We will concentrate on the class of birth death processes to illustrate

these ideas.
For any birth and death process we can solve the equation

(LU )(i) = i U (i + 1) + i U (i 1) (i + i )U (i) = U (i) (3)

for i = 0, 1, 2, , n 1 with boundary condition U (n) = 1. Notice that

because we must have 0 = 0,

0 U (1) = (0 + )U (0)

or
0 +
U (1) = U (0) (4)
0
From what we proved in the last section the solution U,n of (2) and (3)
satisfies
U,n (0) = E0 {en }
For the validity of this formula we need only the values of {j , j } for 0
j n 1. We can define them arbitraily for j n and so it does not matter
if the sequence {j , j } is unbounded. On the other hand if U () is any
solution of (2) and (3), so is

U (i)
U,n (i) =
U (n)

and U,n (n) = 1. Hence

U,n (i) = Ei {en } for 0 i n

Clearly U,n (i) is in n for n i and nonexplosion is equivalent to

lim U,n (i) = 0

n

for each fixed i. Equivalently if we solve (2) and (3) for all i 0, to get U()
we need
lim U (n) =
n
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 21

For determinig U (n) we can assume with out loss of generality that U (0) =
1. Then U (1) = 0+1
0
and the recurrence relation

(i + i + )U (i) i U (i 1)
U (i + 1) = (5)
i
determines U (n) successively for all n 2. The U (n) that we get is neces-
sairily increasing and explosion occurs if and only if

lim U (n) <

n

We can rewrite equation (4) in the form

i
U (i + 1) U (i) = [U (i) U (i 1)] + U (i) (6)
i i
for i 1 and
0 + 0 +
U (1) = U (0) = =1+
0 0 0
with a normalization of U (0) = 1 Clearly U (i) is increasing as a function
of i and U (i) 1 for all i. For U (i) to remain bounded it is therefore
necessary that the solution of
i
V (i + 1) V (i) = [V (i) V (i 1)] + (7)
i i
for i 2 with V (1) = 1 + 0 and V (0) = 1 should be bounded. Since
constants are solutions of the homogeneous equation and the solutions are
linear in the coefficient of the inhomogeneous term , there is basically one
equation that needs to have a bounded solution.
i 1
U(i + 1) U(i) = [U(i) U (i 1)] + (8)
i i
for i 2 with U(0) = 0 and U(1) = 1. The converse is true as well. If
equation (8) has a solution bounded by C we find that, replacing U() by
V () = U() + 1 which is bounded by C + 1,
i 1 V (i)
V (i + 1) V (i) [V (i) V (i 1)] + (9)
i i C + 1
22 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

with V (0) = 1 and V (1) = 2. By comparison we conclude that if 0 =

1
min(0 , C+1 )
U0 (i) V (i)
Although we know that boundedness of U () for some value of > 0 implies
the same for all other positive values of , we can see it directly by the
following simple inequality, which is a consequence of Jensens inequality.
For any convex function

(L(u))(x) (u(x))(Lu)(x)

In particular if
i
V (i + 1) V (i) [V (i) V (i 1)] + V (i)
i i

then for > 1, V (i) = [V (i)] satisfies
i
V (i + 1) V (i) [V (i) V (i 1)] + V (i)
i i
establishing for > 1, and > 0

U (i) U (i) [U (i)]

Now one can write down necessary and sufficient conditions for the exis-
tence of a bounded solution to (8) as
n
X 1 2 n X 1 2 j1 1
<
n=1
1 2 n j=1
1 2 j1 j

and
X 1 2 n
<
n=1
1 2 n

Remark 2. In fact the probability of explosion in a finite time is either

identically 1 for all initial states or identically equal to 0 for all states.
To see this
U(i) U(i)
Pi { < } Ei {e } = lim Ei {en } = lim =
n n U(n) U()
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 23

since limn U(n) = U() exists. Now we see that

lim V (i) = 1
i

where
V (i) = Pi { < }
On the other hand one can verify easily that

(LV )(i) = 0

for all i (including 0), and the only solution to this are the constants. There-
fore V (i) c and of course c = 1, if U() < . Otherwise V (i) 0.

Example: For a birth and death process with n n C(n + 1) for all n,
there is no explosion. Let us try U(n) = (n + 1) with < 1. Since U() is
concave

(LU)(n) = n (U(n + 1) U(n)) + n (U(n 1) U(n))

(n n )(U(n) U(n 1))
C(n + 1)(n + 1)1
= CU(n)

Recurrence and Transience.

For a birth and death process we have essentially investigated the solutions
of the equation

n U(n 1) (n + n )U(n) + n U(n + 1) = 0

for n 1. If we normalize U(1) U(0) = 1, we obtain

j
U(n + 1) U(n) = nj=1
j

and with U(0) = 0

n
X j
U(n + 1) = 1 + kj=1
k=1
j
24 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

It is easy to see that U(n) becomes unbounded as n if and only if

X j
kj=1 =
k=1
j

Now we return to the question of recurrence. Given three states 0 < i < n
we try to calculate the probaility
Pi {n < 0 }
of visiting n before visiting 0 when the process starts from i. Here j is
the first visiting time of the state j. This probability is defined well before
explosion and we can alter k , k for k n with out changing the probability.
In fact we can assume without any loss of generality that L is a bounded
operator. If LU(i) = 0 for 0 i n, then U(x(n t)) is seen to be a
martingale because we can always modify L, U and g beyond n. In particular
if U(0) = 0, by Doobs theorem,
U(i)
Pi {n < 0 } =
U(n)
and there is recurrence if and only if U(n) . Actually we do not have
to solve the equation LU = 0. If we can find a supersolution LU 0 which
goes to as n that works just as well to prove recurrence and the
existence of a positive subsolution that remains bounded as n will
establish transience. In particular the necessary and sufficient condition for
recurrence, with nonexplosion, is

X 1 n
=
n=1
1 n

The question of recurrence with explosion raises the philosophical question

of life after death.
Exercise: For a birth and death process, if n n 0 for n n0 , then
the process is recurrent.
Invariant distributions and positive recurrence.
An invariant distribution q(dy) on (X , B) is a pobability distribution such
that Z
q(A) = p(t , x , A) q(dy)
X
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 25

for all A B and t > 0. If L is bounded this can be verified by verifying the
infinitesimal relation Z
(Lf )(x)q(dx) = 0
X
for all f B. To see this we only have to observe that
d
< Tt f , q > = < LTt f , q >= 0.
dt
Or equivalently it is enough to verify that
Z

(L q)(A) = [ (y , A) A (y)]a(y)q(dy) = 0
X

In general the invariant distribution is not unique. In the case of a birth and
death process this reduces to

q(i 1)i1 + q(i + 1)i+1 = q(i)(i + i )

for i 1, with
q(1) 0
q(1)1 = q(0)0 or =
q(0) 1
We can assume for the momemt that q(0) = 1. Then
0 1 i1
q(i) =
1 2 i
satisfies
i1 i
q(i 1)i1 + q(i + 1)i+1 = q(i 1)[i1 + ]
i
i1
= q(i 1) (i + i )
i
= q(i)(i + i )

or
i1
q(i) = q(i 1)
i
The convergence of the series

X X 0 1 i1
Z= q(i) = 1 + < (10)
i=0 i=1
1 2 i
26 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES

is necessary and sufficient for the existence of a finite invariant measure and
we can normalize it so that Z1 q(i) is the invariant probability distribution.
While it is clear that when L is bounded or when {n , n } is bounded q(),
constructed under the assumption (10), is really an invariant probability for
the process. This is not obvious in the unbounded case. It is however true
in the absence of explosion.
The proof is not very hard. We can truncate the system at size n by
redefining n = 0 and then the finite system has an invariant measure
1 0 1 i1
qn (i) =
Zn 1 2 i
with n
X 0 1 i1
Zn = 1 +
j=1
1 2 i
If we let n the absence of explotion yields
(n)
pi,j (t) pi,j (t)
as n for all i, j and t > 0. The invariance of qn () for the truncated
process carries over to the limit.
Beyond Explosion:
The question of how to define the process is upto us. Anything reasonable
will give us a process. For instance at the explosion time we can reinitiate at
the state 0. Start afresh with a clean slate. Now the process is well defined
for all times. One may see several explosions and each time we restart from
0. By the time we run out of luck again, i.e. when we see an infinite number
of explosions, real time would have become infinite. In terms of analysis this
corresponds to boundary conditions that U has to satisfy for the formal
relation
(LU)(i) = f (i)
to be really valid. In the case we just discussed, it is
lim U(i) = U(0)
i

It is as if we are really on a circle and as i it approaches 0 from the

other side. For each rule of how to continue after explosion there will be a
different boundary condition.
The proofs are left as exercises.