Continuous-time Markov Chains

Say the process enters state i at time 0. Let T_i be the time the process stays in state i. Then P(T_i>s+t|T_i>s) =P(T_i>t) by the Markov property. But this means that T_i is memoryless! Of course T_i is also non-negative and continuous, and therefore T_i has to have an exponential distribution.
With this we have the following characterization of a continous-time Markov chain:
1) the amount of time spent in state i is an exponential distribution with mean v_i.
2) when the process leaves state i it next enters state j with some probability, say P_ij.

So a continous-time Markov chain is a process that moves from state to state in accordance with a discrete-space Markov chain, but also spends an exponentially distributed amount of time in each state.

Let's start by considering a finite-statespace continuous-time Markov chain,, that is X(t){0,..,N}, say. Let P_ij(t) = P(X(t)=j|X(0)=i), Then the the Markov property asserts that {X(t),t≥0} satisifes

where c) follows fromt the Chapman-Kolmogorov equations. d*) is not strictly a consequence of the Markov property but is usually a sensible additional condition.

Let P(t)=(p_ij) denote the matrix of transition probabilities at time t, so P is a matrix whose entries are functions of t.
Now c) can be written as P(s+t)=P(s)P(t), ts≥0. and d*) as lim_h→0P(h)=I
d) means that P(t) is (right)-continuous at time 0, meaning each entry is continuous at t=0. Now

and so P(t) is continuous for all t≥0. Actually, we have even more:

which shows that P(t) is even differentiable

The rates q_i and q_ij give as a second way to describe a Markov chain, called the infinitesimal description

Let

Example (Two-state Chain)
say {X(t),t≥0} is a Markov chain with X(t){0,1} and

We need Aⁿ, so

it is easy to find the stationary distribution of a continuous-time discrete-space markov chain in terms of the infinitesimal matrix. If all states communicate, that is if P_ij(t)>0 for all i,j and some t>0, then lim_t→∞P_ij(t) =π_j>0 exists, and

otherwise the chain would never leave i, and so we have πA=0 or

π_jq_j=∑_i≠jπ_iq_ij, .. j=0,..,N

Example Redundancy
A company has a computer for its website. If the computer is down they can't sell anything, so they have a backup, which takes over if the first computer is down. The operating computer fails after an exponentially distributed time (with rate μ). Repair times are also exponentially distributed (with rate λ). Let's assume that μ is fixed but we have a choice of λ (by hiring more technitians). We want to make sure that in the long run at most1% of the time both computers are down. How should we choose λ?
Let X(t) be the number of computers in operating condition at time t, so X(t){0,1,2}. Then X(t) is a Markov chain with infinitesimal matrix

What is the average "total downtime", that is the time when neither computer is working? The system of equations for the stationary distribution is

and we see that the probability only depends on the ratio λ/μ. Set x=λ/μ, then

Continuous-time Markov chains with infinite Statespace

Example : Birth and Death Processes:
Consider a system whose state at any time is the number of "people" in the system. Suppose if there are n people in the system then
(i) new arrivals enter the system at an exponential rate λ_n ("births") and
(ii) people leave the system at and exponential rate μ_n ("deaths")
(ii) births and deaths occur independently of each other

Thus a birth and death process is a Markov chain with state-space {0,1,..} and
1) v₀ = λ₀
2) v_i = λ_i + μ_i
3) P₀₁ = 1
4) P_i,i+1 = λ_i/(λ_i + μ_i)
5) P_i,i-1 = μ_i/(λ_i + μ_i)

where 4) is because we go from i to i+1 if there is a birth before a death. Let X~Exp(λ), Y~Exp(μ) and XY. Now

Example : A simple epidemic model:
Consider a population of m individuals that at time 0 consists of 1 "infected" and m-1 "susceptibles" (individuals that might get infected, maybe because they have not been immunized. Once infected an individual remains so forever and we suppose that in any time interval h any given infected person will cause, with probability αh+o(h) any given susceptible to become infected. If we let X(t) denote the number of infected people in the population at time t, {X(t),t≥0} is a pure birth process with

λ_n=(m-n)nα, n=1,..,m-1

because if there are n infected people the m-n uninfected ones get infected at a rate of nα

Let T_i be the time to go from i to i+1 infected, and let T be the time until the total population is infected, then