http://www.math.nyu.edu/faculty/varadhan/spring06/spring06.1.pdf
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(t′
j) − N(tj) are mutually independent if the
intervals [tj , t′
j ] 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.
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(t′
j) − N(tj) are mutually independent if the
intervals [tj , t′
j ] 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
P{ j ≥ x} =
(
exp[− x] for x ≥ 0
1 for x ≤ 0
(1.1)
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
nP
N(
T
n
) ≥ 2
= n . o(
1
n
) = o(1) as 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( 1
n).
E
exp[−N(t)]
= lim
n→∞
E
exp[−N(
[nt]
n
)]
= lim
n→∞
E
exp[−N(
1
n
)]
[nt]
(1.2)
= exp[−tg()] (1.3)
where
g() = lim
n→∞
n
1 −
E
exp[−N(
1
n
)]
= lim
n→∞
n
E
1 − exp[−N(
1
n
)]
= lim
n→∞
n
(1 − e−)P[N(
1
n
) = 1] + o(
1
n
)
= (1 − e−) (1.4)
where
= lim
n→∞
n P[N(
1
n
) = 1]. (1.5)
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 ] = e−x
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) = [k 1]+1
k 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 Doob’s 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
with density k
k! e−xxk−1. 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
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
. 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 , t′
j ] the
increments X(t′
j)−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.
E{exp[i y X(t)]} =
X
j
e−t (t)j
j!
[ˆ
(y)]j = e−tet ˆ
(y) = et[ˆ
(y)−1]
(y)]j = e−tet ˆ
(y) = et[ˆ
(y)−1]
= exp[t
Z
(ei y x − 1) d
(x)]
(x)]
Inother words X(t) has an infinitely divisible distribution with a Levy mea-
sure given by t
. If we denote by M =
then
. If we denote by M =
then
E{exp[i yX(t)]} = exp[t
Z
(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
has two moments, show that are constants A and
B such that X(t)−At and [X(t)−At]2−Bt are martingales. Compute A and
B in terms of and
. [A =
. [A =
R
x dM =
R
x d
; B =
; B =
R
x2 dM =
R
x2 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.
k = Mk.
E{Xk(t)} = t
Z
x dMk(x)
and
V ar[Xk(t)] = t
Z
x2 dMk(x)
Let us take Xk(t) to be mutually independent processes with independent
increments and try to sum up
X(t) =
X
k
Xk(t)
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(t) =
X
k
[Xk(t) − akt]
to help in convergence. We shall assume that
X
k
Z
x2
1 + x2 dMk(x) < ∞
which amounts to two conditions
X
k
Mk[|x| ≥ 1] < ∞
6 CHAPTER 1. POISSON PROCESSES
and X
k
Z
|x|≤1
x2dMk(x) < ∞
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-
tively. It is better for us to decompose each Mk as M(1)
k +M(2)
k corresponding
to jumps of size |x| ≤ 1 and |x| > 1.
M =
X
k
M(2)
k
sums to a finite measure and offers no difficulty. The process
X(2)(t) =
X
k
X(2)
k (t)
exists very nicely because
P{X(2)
k (t) 6= 0} ≤ 1 − e−tM
(2)
k [ |x|>1 ] ≤ tM(2)
k [|x| > 1]
and X
k
P{X(2)
k (t) 6= 0} < ∞
Borel-Cantelli does it! As for a discussion of
P
k X(1)
k (t), it is now clear
that we can assume that M(1)
k [ |x| > 1 ] = 0 for every k. If we take ak =
E{Xk(1)} =
R
x dM(1)
k (x),
E{[X(1)
k (t) − akt]2} =
Z
x2dM(2)
k (x)
and by the two-series theorem
X
k
[X(1)
k (t) − akt]
converges almost surely. A simple application of Doob’s 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
E{ei yX(t)} = exp
t
Z
|x|≤1
(ei y x − 1 − i y x)dM(x) +
Z
|x|>1
(ei y x − 1)dM(x)
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)
=
X∞
k=1
e−t (t)k
k!
(k)(x ,A)
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(t−s) ∈ 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
p(t + s , x ,A) =
Z
X
p(s , y ,A) p(t , x , dy)
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 ]
Px{∩k
j=1[x(tj) ∈ Aj ]} =
Z
A1
・ ・ ・
Z
Ak
p(t1 , x , dy1) ・ ・ ・ p(tk − tk−1 , x , dyk)
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
X
(n)(x , dy)m(y ,A) = (n+m)(x ,A)
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)
(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
(Ttf)(x) =
Z
X
f(y) p(t , x , dy)
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 kTtk ≤ 1.
In fact, because Tt1 = 1, kTtk = 1. T0 = I, the identity operator and for any
t, s ≥ 0, Tt+s = TtTs = TsTt.
2. Tt maps non-negative functions into non-negative functions.
3. For any t ≥ 0,
Tt =
X∞
k=0
e−t (t)kk
k!
where is the operator
(f)(x) =
Z
X
f(y)(x , dy)
It is clear that we can write
Tt = e−t 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
L = lim
t↓0
Tt − I
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
k
Tt − I
t
− Lk → 0
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)
(Lf)(x) =
Z
R
[f(x + y) − f(x)]M(dy)
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
(Lf)(x) =
Z
X
[f(y) − f(x)](x , dy)
as potential candidates of generators of Markov Processes one can see that
operators of the form
(Lf)(x) = a(x)
Z
X
[f(y) − f(x)](x , dy)
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
ˆ (x ,
A) =
a(x)
(x ,A) + (1 −
a(x)
)A(x)
so that
(Lf)(x) = a(x)
Z
X
[f(y) − f(x)](x , dy) =
Z
X
[f(y) − f(x)]ˆ (x , dy)
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
ai,j = lim
t↓0
pi,j(t)
t
≥ 0 (2)
2.2. SEMIGROUPS OF OPERATORS. 13
and
ai,i = lim
t↓0
pi,i(t) − 1
t
≤ 0
Also
P
j pi,j(t) ≡ 1 leads to
X
j
ai,j = 0 ∀ i = 1, ・ ・ ・ , k. (3)
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 (Ttf)(x0) being an average of f is
atleast f(x0). The inequality (Ttf)(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
P(t) = exp[tL] =
X∞
k=0
e−t (tL)k
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( t
n)]n and now P(t) is seen to be a stochastic matrix for all t > 0.
The case when ai,j ≥ 0, ∀ i 6= j is handled by approximating it by {a(n)
i,j }
with a(n)
i,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
L = lim
t↓0
P(t) − I
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,n−1 = μ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
(Lf)(x) = a(x)
Z
X
[f(y) − f(x)](x , dy)
where a(x) is a bounded measurable function and is a transition probability
on X. Let T(t) = exp[t L] be the operators
(Ttf)(x) =
Z
X
f(y) p(t , x , dy)
where p(t , x , dy) are the transition probabilities corresponding to L. We swa
earlier by differentiating term by term in the expansion
Tt =
X∞
k=0
(t L)k
k!
of Tt in powers of L that
d Tt
dt
= Tt L = L Tt
2.3. MARKOV PROCESSES AND MARTINGALES. 15
In particular
Tt f − f =
Z t
0
Ts L f ds
or
Ex
f(x(t)) − f(x(0)) −
Z t
0
(Lf)(x(s)) ds
F0
= 0
If we use the homogeniety in time
Ex
f(x(t)) − f(x(s)) −
Z t
s
(Lf)(x()) d
Fs
= 0
Thus
Mf (t) = f(x(t)) − f(x(0)) −
Z t
0
(Lf)(x()) d
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 ,
e− tf(x(t)) − f(x(0)) −
Z t
0
e− [(Lf) − f](x()) d
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} =
[
st
s rational
{x(s) ∈ A}
[
{x(t) ∈ A}
Lemma 2.1. For > 0 the function
U(x) = Ex
e− Af(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{e− Af(x( ))}
and conditioning with respect to F where
= {inf t : x(t) 6= x(0)}
we get
U(x) = Ex{e− Ex( ){e− Af(x( A))}
= Ex{e− U(x( ))}
= Ex{e− }Ex{U(x( ))}
=
a(x)
+ a(x)
Z
X
U(y)(x , dy)
We can rewrite this as
( + a(x))U(x) = a(x)
Z
X
U(y)(x , dy)
or
(LU)(x) = a(x)
Z
X
[U(y) − U(x)](x , dy) = U(x).
Conversely if U solves LU = U on Ac with U = f on A, we know that
e−tU(x(t)) − U(x(0)) −
Z t
0
[LU − U](x(s)) ds
is a Px martingale. We apply Doob’s 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{e− Af(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
U(x) = Ex
e− Af(x( A)) +
Z A
0
e−sg(x(s)) ds
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
exponential time n at n with E{ n} = 1
(n+1)2 for n ≥ 0. A simple calculation
shows that
X∞
n=0
E{ n} =
X∞
n=0
1
(n + 1)2 < ∞
and by Fubini’s theorem
X∞
n=0
n = < ∞
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
(Lf)(x) = a(x)
Z
X
[f(y) − f(x)](x , dy)
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
U(x) = Ex
e− 1U(x( 1))
=
a(x)
a(x) +
Z
X
U(y)(x , dy)
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( ))
= Ex
e− 1Ex( 1)
e− 1U(x( 1))
= Ex
e− 2U(x( 2))
・ ・ ・ ・ ・ ・ ・ ・ ・
= Ex
e− nU(x( n))
where n is the time of the n-th jump. Therefore
U(x) ≥ Ex{e− n}
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
U(x) ≤ Ex
e− nU(x( n))
≤ Ex
e− n
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
U(x) ≥ Ex
e− nU(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
Tt =
X∞
j=0
(tL)j
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) = iU(i + 1) + μiU(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,
0U(1) = (0 + )U(0)
or
U(1) =
0 +
0
U(0) (4)
From what we proved in the last section the solution U,n of (2) and (3)
satisfies
U,n(0) = E0{e− n}
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,n(i) =
U(i)
U(n)
and U,n(n) = 1. Hence
U,n(i) = Ei{e− n} for 0 ≤ i ≤ n
Clearly U,n(i) is ↓ in n for n ≥ i and nonexplosion is equivalent to
lim
n→∞
U,n(i) = 0
for each fixed i. Equivalently if we solve (2) and (3) for all i ≥ 0, to get U(・)
we need
lim
n→∞
U(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
U(i + 1) =
(i + μi + )U(i) − μiU(i − 1)
i
(5)
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
n→∞
U(n) < ∞
We can rewrite equation (4) in the form
U(i + 1) − U(i) =
μi
i
[U(i) − U(i − 1)] +
i
U(i) (6)
for i ≥ 1 and
U(1) =
0 +
0
U(0) =
0 +
0
= 1 +
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
V(i + 1) − V(i) =
μi
i
[V(i) − V(i − 1)] +
i
(7)
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.
U(i + 1) − U(i) =
μi
i
[U(i) − U(i − 1)] +
1
i
(8)
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,
V (i + 1) − V (i) ≥
μi
i
[V (i) − V (i − 1)] +
1
i
V (i)
C + 1
(9)
22 CHAPTER 2. CONTINUOUS TIME MARKOV PROCESSES
with V (0) = 1 and V (1) = 2. By comparison we conclude that if 0 =
min(0 , 1
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 Jensen’s inequality.
For any convex function -
(L-(u))(x) ≥ -′(u(x))(Lu)(x)
In particular if
V (i + 1) − V (i) ≥
μi
i
[V (i) − V (i − 1)] +
i
V (i)
then for
> 1, V
(i) = [V (i)]
satisfies
> 1, V
(i) = [V (i)]
satisfies
V
(i + 1) − V
(i) ≥
(i + 1) − V
(i) ≥
μi
i
[V
(i) − V
(i − 1)] +
(i) − V
(i − 1)] +
i
V (i)
establishing for
> 1, and > 0
> 1, and > 0
U(i) ≤ U
(i) ≤ [U(i)]
(i) ≤ [U(i)]
Now one can write down necessary and sufficient conditions for the exis-
tence of a bounded solution to (8) as
X∞
n=1
μ1μ2 ・ ・ ・ μn
12 ・ ・ ・ n
Xn
j=1
12 ・ ・ ・ j−1
μ1μ2 ・ ・ ・ μj−1
1
μj
< ∞
and
X∞
n=1
μ1μ2 ・ ・ ・ μn
12 ・ ・ ・ 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
Pi{ < ∞} ≥Ei{e−} = lim
n→∞
Ei{e− n} = lim
n→∞
U(i)
U(n)
=
U(i)
U(∞)
2.4. EXPLOSION, RECURRENCE AND TRANSIENCE. 23
since limn→∞ U(n) = U(∞) exists. Now we see that
lim
i→∞
V (i) = 1
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
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
(n + 1)(n + 1)
−1
= C
U(n)
U(n)
Recurrence and Transience.
For a birth and death process we have essentially investigated the solutions
of the equation
μnU(n − 1) − (n + μn)U(n) + nU(n + 1) = 0
for n ≥ 1. If we normalize U(1) − U(0) = 1, we obtain
U(n + 1) − U(n) = n
j=1
μj
j
and with U(0) = 0
U(n + 1) = 1 +
Xn
k=1
k
j=1
μj
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∞
k=1
k
j=1
μj
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 Doob’s theorem,
Pi{ n < 0} =
U(i)
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∞
n=1
μ1 ・ ・ ・μn
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
q(A) =
Z
X
p(t , x ,A) q(dy)
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
X
(Lf)(x)q(dx) = 0
for all f ∈ B. To see this we only have to observe that
d
dt
< Ttf , q >=< LTtf , q >= 0.
Or equivalently it is enough to verify that
(L∗q)(A) =
Z
X
[(y ,A) − A(y)]a(y)q(dy) = 0
In general the invariant distribution is not unique. In the case of a birth and
death process this reduces to
q(i − 1)i−1 + q(i + 1)μi+1 = q(i)(i + μi)
for i ≥ 1, with
q(1)μ1 = q(0)0 or
q(1)
q(0)
=
0
μ1
We can assume for the momemt that q(0) = 1. Then
q(i) =
01 ・ ・ ・ i−1
μ1μ2 ・ ・ ・ μi
satisfies
q(i − 1)i−1 + q(i + 1)μi+1 = q(i − 1)[i−1 +
i−1i
μi
]
= q(i − 1)
i−1
μi
(i + μi)
= q(i)(i + μi)
or
q(i) =
i−1
μi
q(i − 1)
The convergence of the series
Z =
X∞
i=0
q(i) = 1 +
X∞
i=1
01 ・ ・ ・ i−1
μ1μ2 ・ ・ ・ μi
< ∞ (10)
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 1
Z 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
qn(i) =
1
Zn
01 ・ ・ ・ i−1
μ1μ2 ・ ・ ・ μi
with
Zn = 1 +
Xn
j=1
01 ・ ・ ・ i−1
μ1μ2 ・ ・ ・ μi
If we let n → ∞ the absence of explotion yields
p(n)
i,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
i→∞
U(i) = U(0)
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.
No comments:
Post a Comment