Poisson and birth-and-death processes, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Continuous Time Markov Chains

In this lecture we will discuss Markov Chains in continuous time. Continuous time Markov Chains are used to represent population growth, epidemics, queueing models, reliability of mechanical systems, etc. In Continuous time Markov Process, the time is perturbed by exponentially distributed holding times in each state while the succession of states visited still follows a discrete time Markov chain. Given that the process is in state i, the holding time in that state will be exponentially distributed with some parameter λ_i, where i can represent the current population size, the number of alleles A₁ in the population, etc. These holding times basically control how rapidly the movements (changes of states) of the chain take place. Additionally, given the knowledge of visited states, the holding times are independent random variables. For a Continuous Markov Chain, the transition probability function for t > 0 can be described as 

P_ij(t) = P(X(t + u) = j|X(u) = i)

and is independent of u ≥ 0. In fact, P(X(t + u) = j|X(u) = i) is a function of t and describes a timehomogeneous transition law for this process.

To construct a Markov process in discrete time, it was enough to specify a one step transition matrix together with the initial distribution function. However, in continuous-parameter case the situation is more complex. The specification of a single transition matrix [p_ij(t₀)] together with the initial distribution is not adequate. This is due to the fact that events that depend on the process at time points that are not multiples of t₀ might be excluded. However, if one specifies all transition matrices p(t) in 0 < t ≤ t₀ for some t₀ > 0, all other transition probabilities may be constructed from these. These transition probability matrices should be chosen to satisfy the Chapman-Kolmogorov equation, which states that: 

Or we can state it in a matrix notation by the following so-called semigroup property:

P(t +s) = P(t)P(s)

The (i,j) element of the matrix P(t + s) is constructed by i row of P(t) multiplied by the j column of P(s). For some time points 0 < t₁ < t₂ < t₃ and arbitrary states a,b,c,d one has that:

P(X₀ = a,X_t1 = b,X_t2 = c,X_t3 = d) = p_ap_a,b(t₁)p_b,c(t₂ −t₁)p_c,d(t₃ −t₂)

as well as

P(X₀ = a,X_t1 = b,X_t3 = d) = p_ap_a,b(t₁)p_c,d(t₃ −t₁)

The consistency of the Chapman-Kolmogorov Equation would require the following: 

The above postulates give motivation for Kolmogorov forward and backward equations, which will be discussed in later sections in detail. Let us start with introduction of a Continious time Markov Chain called Birth-and-Death process.
 

2 Birth-and-Death process: An Introduction

The birth-death process is a special case of continuous time Markov process, where the states (for example) represent a current size of a population and the transitions are limited to birth and death. When a birth occurs, the process goes from state i to state i + 1. Similarly, when death occurs, the process goes from state i to state i−1. It is assumed that the birth and death events are independent of each other.

The birth-and-death process is characterized by the birth rate {λ_i}i=0,...,∞ and death rate {µ_i}i=0,...,∞, which vary according to state i of the system. We can define a Pure Birth Process as a birth-death process with µ_i = 0 for all i. Similarly, a Pure Death Process corresponds to a birth-death process with λ_i = 0 for all i.

The general description of the Birth-and-Death process can be as follows: after the process enters state i, it holds (sojourns) in the given state for some random length of time, exponentially distributed with parameter (λ_i +µ_i). When leaving i, the process enters either i+1 with probability 

or i−1 with probability 

If the next state chosen is i +1, then the process sojourns in this state according to the exponential distribution with parameter λ_i+1 + µ_i+1 and then chooses the next state etc. The number of visits back to the same state is ignored since in a continuous time process transitions from state i back to i would not be identifiable.

Imagine having two exponentially distributed random variables B(i) and D(i) with parameters λ_i and µ_i respectively. These random variables describe the holding time in the state i. We can think of B(i) as the time until a birth and D(i) is the time until a death (when a population size is i). The population increases by one if the birth occurs prior to death and decreases by one otherwise. If B(i),D(i) are independent exponentially distributed random variables, then their minimum is exponentially distributed with parameter (λi + µi).

A transition from i to i+1 is made if B(i) < D(i), which occurs with probability 

This motion is analogous to a random walk with the difference that here the transitions occur at random times (as opposed to fixed time periods in random walks).

It is of necessity to discuss the Poisson process, which is a cornerstone of stochastic modelling, prior to modelling birth-and-death process as a continuous Markov Chain in detail.
 

2.1 The law of Rare Events

The common occurrence of Poisson distribution in nature is explained by the law of rare events. Consider a large number N of independent Bernoulli trials where the probability p of success on each trial is small and constant from trial to trial. Let X_N,p be the total number of successes in N trials, where X_N,p follows the binomial distribution, for k = 0,1,...,N. 

If we assume that N −→ ∞ and p −→ 0, so that N_{p - µ}, then the distribution for X_N,p becomes the Poisson distribution: 

In Stochastic modelling, this law is used to suggest circumstances under which the poisson distribution might be expected to prevail, at least approximately.
 

2.2 Poisson Process 

A poisson distribution with parameter µ > 0 is given by 

and describes the probability of having k events over a time period embedded in µ. The random variable X having a Poisson distribution has the mean E[X] = µ and the variance V ar[X] = µ.

The Poisson process entails notions of Poisson distribution together with independence. A Poisson process of intensity λ > 0 (that describes the expected number of events per unit of time) is an integer-valued Stochastic process{X(t);t ≥0}for which: 

1. for any arbitrary time points t₀ < t₁ < t₂ < ··· < t_n, and t₀ = 0, the number of events happening in disjoint intervals (process increments) 

X(t₁)−X(t₀),X(t₂)−X(t₁),X(t₃)−X(t₂),...,X(t_n)−X(t_n−1)

are independent random variables. This means that the number of events in one time interval is independent from the number of events in an interval that is disjoint from the first interval. This is known as independent increments property of the Poisson process.

2. for s ≥0and t > 0, the random variable X(s+t)−X(s), which describes the number of events occurring between time s and s +t (independent increment), follows the Poisson distribution

3. We assume that at time zero the number of events that have happened already is zero.

In this case, the parameter of the Poisson distribution is λt, E[X(t)] = λt, and V ar[X(t)] = λt. Let us fix a short interval of time h. In Stochastic modelling, it is of a special interest to derive the probability of exactly one event over the time period h:

where o(h) denotes a general and unspecified remainder term of smaller order than h. We can view the rate λ in Poisson process X(t) as the proportionality constant in the probability of an event occurring during an arbitrary small interval h. 

In a Poisson Process, the waiting time between consecutive events is called a Sojourn time, S_i = W_i+1−W_i, where Wi is the time of occurrence of the i’th event. Basically, S_i measures the duration that the Poisson process sojourns in state i. 

The Sojourn times S₀,S₁,...,S_n−1 are independent random variables, each having the exponential probability density function  

2.3 Definition of Birth-and-Death process 

We let {X(t)}t≥0 be a Markov chain and define a very short interval of time  during which there exist observable changes in a chain. We would like to calculate a probability of seeing some particular changes occurring at time t + h, given that we started at time t. Over such a short interval of time  it is nearly impossible to observe more than one event; in fact, the probability to see more than one event is o(h). 

If we are to describe a pure birth process with the birth rate λ_i, we would name it a Poisson process with parameter λ_ih so that λ_i is the expected number of birth events that occur per unit time. In this case, the probability of a birth over a short interval h is λ_ih + o(h). 

Similarly, if in state X(t) = i a death rate is µ_i, then the probability that an individual dies in a very small time interval of length h is µ_ih + o(h). 

In the case of birth-and-death process, we have both birth and death events possible, with rates λ_i and µ_i accordingly. Since birth and death processes are independent and have poisson distribution with parameters λ_ih and µ_ih, their sum is a Poisson distribution with parameter h(λ_i + µ_i). 

Let us analyze changes which might occur in birth-and-death process over the time interval h. Given that there are currently i people in the population, as  the probability that there will be an change of size 1 is basically represented by the probability of one birth and no death (which is a main probabilitic component) or other combinations (two birth and one death, three birth and two death, etc) chances of which however are very small, o(h) :

In this case, o(h) term represents the fact that there are two birth and one death, 3 birth and 2 death, etc . As h gets really, the probability that o(h) possibilities occur vanishes. Similarly, the probability that there will be a decreasing change of size 1 is 

P_i,i−1(h) = P(X(t +h)−X(t) =−1|X(t) = i) = µ_ih + o(h) Basically, the above postulates assume that the probabilities of population increasing or decreasing by 1 are proportional to the length of the interval. In general, the process is called a birth-and-death process if:

(1) P(X(t + h)−X(t) = 1|X(t) = i) = λ_ih + o(h)
(2) P(X(t + h)−X(t) =−1|X(t) = i) = µ_ih +o(h)
(3) P(|X(t +h)−X(t)| > 1|X(t) = i) = o(h)
(4) µ₀ = 0,λ₀ > 0; µ_i,λ_i > 0,i = 1,2,3,...

These postulates support the notion that the events are rare and almost exclude the possibility of simultaneous occurrence of two or more events. Basically, only one event can occur in a very small interval of time h. And even though the probability for more than one event is non-zero, it is negligible. The above implies that

(5) P(X(t + h)−X(t) = 0|X(t) = i) = 1−(µ_i + λ_i)h + o(h)

We will postulate P_ij(h) for h small and then derive a system of differential equations satisfied by P_ij(t) for all t > 0.
 

3 Sojourn times

Let S_i be a random variable describing a sojourn time of X(t) in state i. That is, given that a process is in state i, what is the distribution of the time S_i the process first leaves state i. Let us define G_i(t): G_i(t) = P(S_i ≥ t) Then by the Markov property it follows that as

Subtracting G_i(t) from both sides and dividing by h gives 

We can solve the above by applying the fact that if y'(x) = Ay(x), then y(x) = e^{xA 1}. Using the condition G_i(0) = 1, the solution to the equations is

G_i(t) = e−t(λ_i+µ_i)

Using the facts that G_i(x) = 1− P(S_i ≤ x) and the cumulative distribution function of the exponential distribution is P(X ≤ x) = 1− e^−λx, we conclude that S_i follows exponential distribution with parameter (λ_i +µ_i) and mean (expectation) 1/λ_i +µ_i.

4 Infinitesimal Generator of the Birth-and-Death process

The birth-and-death process is defined as 

We can condense this notation by writing

p_ij(h) = δ_ij + h_qij +o(h)

where

The δ_ij is called a Kronecker’s delta, δ_ij = limt_↓0p_i,j(t). It is given by δ_ij = 1 if i = j and δ_ij = 0 if i ≠ j. This condition is reasonable in most circumstances: it requires that with probability one the process spends a possible (but variable) amount of time in the initial state i before moving to a different state j. This relation can also be expressed in matrix notation 

where I is the identity matrix (with 1’s along the diagonals and 0’s elsewhere). We shall also write

p(0) = I

The q_ij are called transition rates, and [q_ij] define the matrix Q, which is also called the infinitesimal generator of the process. This matrix has the properties of the continuous time (Markov) matrix: 

We can write δ_ij = p_ij(0) since we go from state i to state i in zero time steps with probability 1, and from i to j (different from i) in zero time steps with probability 0. Therefore, 

Here  is a derivative of p_ij(t) with respect to t evaluated at 0. Therefore,   

 Since p_ij(t) are transition probabilities we have:

Differentiating the above term by term and setting t = 0, will give us 

Note that

which characterizes the infinitesimal transition matrix Q described above.

5 Differential Equations of Birth and Death processes

Now, let us move to deriving P_ij(t) by using the knowledge about P_ij(h). In the case of pure birth and death process (or more generally Continuous time Markov process), the transition probabilities P_ij(t) satisfy a system of differential equations known as forward and backward Kolmogorov differential equations.

5.1 Backward Kolmogorov differential equation

The backward Kolmogorov differential equation describes the transition probabilities in their dependence on the initial point i. Basically, it analyzes the time interval (0,t+h) by the ”first step analysis”. It decomposes the (0,t+h) into two intervals (0,h) and (h, t+h), where the first interval h is short and positive. Formally speaking,

where the last summation is over k ≠ i−1,i,i+1. By using the facts that P_i,i+1(h) = λ_ih+o(h), P_i,i−1(h) = µ_ih +o(h), and P_i,i(h) = 1−h(λ_i +µ_i)+ o(h), we rewrite 

Let us solve fo 

Therefore

Let us transpose P_i,j(t) to the right and divide both sides by h, then 

Thus

We can now derive a system of differential equations (knowing that µ₀ = 0) 

and

with the initial condition P_ij(0) = δ_ij.

5.1.1 Using Infinitesimal generator

Similarly, we will now derive a backward Kolmogorov equation by using the matrix notation: since Q = [q_ij] = [p^'_ij(0)] = p^'(0) and by Chapman-Kolmogorov equation 

we can differentiate with respect to s so that

Setting s = 0 gives

This gives

P^'(t) = QP(t)

which defines a Kolmogorov backward equation.
 

5.2 Forward Kolmogorov differential equation

On the other hand, the forward Kolmogorov differential equation describes the probability distribution of a state in time t keeping the initial point fixed. It decomposes the time interval (0,t+s) into (0,t) and (t, t+h) by a so-called “last step analysis”. Similarly to the backward Kolmogorov differential equation:

The last summation is for k 6= j −1,j,j +1. Then, 

Similarly to the previous analysis, by translocation P_ij(t)and dividing both sides by h, we get two differential equations

with the same initial condition P_ij(0) = δ_ij

5.2.1 Using Infinitesimal generator

This time we differentiate with respect t, which gives 

Setting t = 0 gives

The right-hand side is the sum of the elements in the (i) row of P(s) multiplied by the the (j) column of Q. Thus

P^'(s) = P(s)Q

which defines a Kolmogorov forward equation. The left-hand side is the (ij) element of P^'(s).

5.3 Exponential method of solving the backward Kolmogorov equation

Let us try to solve the backward Kolmogorov equation (P^'(t) = QP(t)) to obtain the explicit expression for P(t).

Let us use the fact that if P^'(t) = qp(t)

then

p(t) = e^tq We can use this fact and the condition that p(0) = I to solve for P(t):

P(t) = e^Qt

where the matrix e^Qt is defined by the power series

6 Application to Poisson process

Let us apply the above equations to general Poisson process with rate λ. The infinitesimal transition rates for Poisson process then are 

Observe that such a Poisson process models a pure birth process. A transition from i to j in n steps resembles a Bernoulli trial performed n times with the probability of success λ (this is the probability of increase by one, which is essential in transition from i to j). By induction it follows that

We can re-write

Therefore the formula

gives

Observe, however, that n cannot start from 0 since we need at least j−i transitions to acquire j−i changes. Therefore, n should go from j −i instead. If we define k = j −i, then

Thus, the transition probabilities coincide with those defined by the Poisson process. In this case j −i represent the number of events (changes) over the interval of time of length t.
 

7 Correspondence to Moran process (short)

Moran process can be described as a death-and-birth process. The population size i in the general birth-anddeath process corresponds to the number of alleles A₁ in the populations. It follows that λ_i corresponds to the probability of increase in the number of A₁ alleles by one pi_,i+1, when the A₂ allele is chosen to die and A₁ allele is chosen to reproduce. Similarly, µ_i corresponds to p_i,i−1, the probability that A₁ is chosen to die while A₂ is chosen to reproduce.