Postscript version of this file

STAT 380 Section 8

Continuous Time Markov Chains

Consider a population of single celled organisms in a stable environment.

Fix short time interval, length $h$.

Each organism has some probability of dividing to produce two organisms and some other probability of dying.

We might suppose:

• Different organisms behave independently.

• Probability of division is $\lambda h$ plus $o(h)$.

• Probability of death is $\mu h$ plus $o(h)$.

• Probability that an organism divides twice (or divides once and dies) in the interval of length $h$ is $o(h)$.

Tacit assumptions:

Constants of proportionality do not depend on time: ``stable environment''.

Constants do not depend on organism: organisms are all similar and live in similar environments.

$Y(t)$: total population at time $t$.

${\cal H}_t$: history of process up to time $t$.

Condition on event $Y(t) =n$.

Probability of two or more divisions (more than one division by a single organism or two or more organisms dividing) is $o(h)$.

Probability of both a division and a death or of two or more deaths is $o(h)$.

So probability of exactly 1 division by any one of the $n$ organisms is $n\lambda h+o(h)$.

Similarly probability of 1 death is $n\mu h+o(h)$.

We deduce:

$$P(Y(t+h) =n+1\vert Y(t)=n, {\cal H}_t)$$

$$= n \lambda h+o(h)$$

$$P(Y(t+h) =n-1\vert Y(t)=n, {\cal H}_t)$$

$$= n \mu h+o(h)$$

$$P(Y(t+h) =n\vert Y(t)=n, {\cal H}_t)$$

$$= 1-n( \lambda+\mu) h+o(h)$$

$$P(Y(t+h) \not\in \{n-1,n,n+1\}\vert Y(t)=n, {\cal H}_t)$$

$$= o(h)$$

These equations lead to:

$$P(Y(t+s) = j\vert Y(s)=i,{\cal H}_s)$$

$$= P(Y(t+s) = j\vert Y(s)=i)$$

$$= P(Y(t)=j\vert Y(0)=i)$$

This is the Markov Property.

Definition:A process $\{Y(t); t \ge 0\}$ taking values in $S$, a finite or countable state space is a Markov Chain if

$$P(Y(t+s) = j\vert Y(s)=i,{\cal H}_s)$$

$$= P(Y(t+s) = j\vert Y(s)=i)$$

$$\equiv {\bf P}_{ij}(s,s+t)$$

Definition:A Markov chain $Y$ has stationary transitions if

$${\bf P}_{ij}(s,s+t) = {\bf P}_{ij}(0,t) \equiv {\bf P}_{ij}(t)$$

From now on: our chains have stationary transitions.

Summary of Markov Process Results

• Chapman-Kolmogorov equations:
  $${\bf P}_{ik}(t+s) = \sum_j {\bf P}_{ij}(t){\bf P}_{jk}(s)$$

• Exponential holding times: starting from state $i$ time, $T_i$, until process leaves $i$ has exponential distribution, rate denoted $v_i$.

• Sequence of states visited, $Y_0,Y_1,Y_2,\ldots$ is Markov chain - transition matrix has ${\bf P}_{ii}=0$. $Y$ sometimes called skeleton.

• Communicating classes defined for skeleton chain. Usually assume chain has 1 communicating class.

• Periodicity irrelevant because of continuity of exponential distribution.

• Instantaneous transition rates from $i$ to $j$:
  $$q_{ij} = v_i {\bf P}_{ij}$$

• Kolmogorov backward equations:
  $${\bf P}_{ij}^\prime(t) = \sum_{k\neq i} q_{ik} {\bf P}_{kj}(t) - v_i {\bf P}_{ij}(t)$$

• Kolmogorov forward equations:
  $${\bf P}_{ij}^\prime(t) = \sum_{k\neq j} q_{kj} {\bf P}_{ik}(t) - v_i {\bf P}_{ij}(t)$$

• For strongly recurrent chains with a single communicating class:
  $${\bf P}_{ij}(t) \to \pi_j$$

• Stationary initial probabilities $\pi_i$ satisfy:
  $$v_j \pi_j = \sum_{k \neq j} q_{kj} \pi_k$$

• Transition probabilities given by
  $${\bf P}(t)= e^{{\bf R}t}$$
  where $\bf R$ has entries
  $${\bf R}_{ij} = \begin{cases}q_{ij} & i \neq j \\ -v_i & i=j \end{cases}$$

• Process is a Birth and Death process if
  $${\bf P}_{ij} = 0$$    if $$\vert i-j\vert > 1$$
  In this case we write $\lambda_i$ for the instantaneous ``birth'' rate:
  $$P(X(t+h)=i+1\vert X_t=i) = \lambda_i h + o(h)$$
  and $\mu_i$ for the instantaneous ``death'' rate:
  $$P(X(t+h)=i-1\vert X_t=i) = \mu_i h + o(h)$$
  We have
  $$q_{ij} = \begin{cases}0 & \vert i-j\vert > 1 \\ \lambda_i & j=i+1 \\ \mu_i & j=i-1 \end{cases}$$

• If all $\mu_i=0$ then process is a pure birth process. If all $\lambda_i=0$ a pure death process.

• Birth and Death process have stationary distribution
  $$\pi_n = \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_n ... ...=1}^\infty \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_{n}}\right)}$$
  Necessary condition for existence of $\pi$ is
  $$\sum_{n=1}^\infty \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_{n}}<\infty$$

• Linear birth and death processes have
  $$\lambda_n = (n+1) \lambda \qquad \mu_n = n \mu$$
  In this case (note immigration)
  $$\pi_n = \frac{(\lambda/\mu)^n}{1-(\lambda/\mu)}$$
  provided $\lambda < \mu$.

Detailed development

Suppose $X$ a Markov Chain with stationary transitions. Then

$$P( X(t+s)=k \vert X(0)=i)$$

$$= \sum_j P(X(t+s)=k,X(t)=j\vert X(0)=i)$$

$$= \sum_j P(X(t+s)=k\vert X(t)=j,X(0)=i)$$

$$\qquad \times P(X(t)=j\vert X(0)=i)$$

$$= \sum_j P(X(t+s)=k\vert X(t)=j)$$

$$\qquad \times P(X(t)=j\vert X(0)=i)$$

$$= \sum_j P(X(s)=k\vert X(0)=j)$$

$$\qquad \times P(X(t)=j\vert X(0)=i)$$

This shows

$${\bf P}(t+s) = {\bf P}(t){\bf P}(s)$$

which is the Chapman-Kolmogorov equation.

Now consider the chain starting from $i$ and let $T_i$ be the first $t$ for which $X(t) \neq i$. Then $T_i$ is a stopping time.

[Technically:

$$\{T_i \le t\} \in {\cal H}_t$$

for each $t$.] Then

$$P(T_i >t+s\vert T_i>s,X(0)=i)$$

$$= P(T_i>t+s\vert X(u)=i; 0 \le u \le s)$$

$$= P(T_i > t\vert X(0)=i)$$

by the Markov property.

Conclusion: given $X(0)=i$, $T_i$ has memoryless property so $T_i$ has an exponential distribution. Let $v_i$ be the rate parameter.

Embedded Chain: Skeleton

Let $T_1 < T_2 < \cdots$ be the stopping times at which transitions occur. Then $X_n = X(T_n)$. The sequence $X_n$ is a Markov chain by the Markov property. That ${\bf P}_{ii}=0$ reflects the fact that $P(X(T_{n+1})=X(T_n))=0$ by design.

As before we say $i \leadsto j$ if ${\bf P}_{ij}(t)>0$ for some $t$. It is fairly clear that $i \leadsto j$ for the $X(t)$ if and only if $i \leadsto j$ for the embedded chain $X_n$.

We say $i{\leftrightarrow}j$ ($i$ and $j$ communicate) if $i \leadsto j$ and $j\leadsto i$.

Now consider

$$P(X(t+h)=j\vert X(t)=i,{\cal H}_t)$$

Suppose the chain has made $n$ transitions so far so that $T_n < t < T_{n+1}$. Then the event $X(t+h)=j$ is, except for possibilities of probability $o(h)$ the event that

$$t < T_{n+1} \le t+h$$    and $$X_{n+1} = j$$

The probability of this is

$$(v_i h +o(h)) {\bf P}_{ij} = v_i {\bf P}_{ij} h +o(h)$$

Kolmogorov's Equations

The Chapman-Kolmogorov equations are

$${\bf P}(t+h) = {\bf P}(t){\bf P}(h)$$

Subtract ${\bf P}(t)$ from both sides, divide by $h$ and let $h\to 0$. Remember that ${\bf P}(0)$ is the identity. We find

$$\frac{{\bf P}(t+h)-{\bf P}(t)}{h} = \frac{{\bf P}(t)({\bf P}(h) - {\bf P}(0))}{h}$$

which gives

$${\bf P}^\prime(t) = {\bf P}(t) {\bf P}^\prime(0)$$

The Chapman-Kolmogorov equations can also be written

$${\bf P}(t+h) = {\bf P}(h) {\bf P}(t)$$

Now subtracting ${\bf P}(t)$ from both sides, dividing by $h$ and letting $h\to 0$ gives

$${\bf P}^\prime(t) ={\bf P}^\prime(0) {\bf P}(t)$$

Look at these equations in component form:

$${\bf P}^\prime(t) ={\bf P}^\prime(0) {\bf P}(t)$$

becomes

$${\bf P}^\prime_{ij}(t) = \sum_k {\bf P}^\prime_{ik}(0) {\bf P}_{kj}(t)$$

For $i \neq k$ our calculations of instantaneous transition rates gives

$${\bf P}^\prime_{ik}(0) = v_i {\bf P}_{ik}$$

For $i = k$ we have

$$P(X(h)=i\vert X(0)=i) = e^{-v_i h} +o(h)$$

($X(h)=i$ either means $T_i > h$ which has probability $e^{-v_i h}$ or there have been two or more transitions in $[0,h]$, a possibility of probability $o(h)$.) Thus

$${\bf P}^\prime_{ii}(0) = -v_i$$

Let ${\bf R}$ be the matrix with entries

$${\bf R}_{ij} = \begin{cases} q_{ij} \equiv v_i {\bf P}_{ij} & i \neq j \\ -v_i & i = j \end{cases}$$

That is

$${\bf R}={\bf P}^\prime(0).$$

${\bf R}$ is the infinitesimal generator of the chain.

Thus

$${\bf P}^\prime(t) ={\bf P}^\prime(0) {\bf P}(t)$$

becomes

$${\bf P}^\prime_{ij}(t) = \sum_k {\bf R}_{ik}{\bf P}_{kj}(t)$$

$$= \sum_{k \neq i } q_{ik} {\bf P}_{kj}(t) -v_i {\bf P}_{ij}(t)$$

Called Kolmogorov's backward equations.

On the other hand

$${\bf P}^\prime(t) = {\bf P}(t) {\bf P}^\prime(0)$$

becomes

$${\bf P}^\prime_{ij}(t) = \sum_k {\bf P}_{ik}(t) {\bf R}_{kj}$$

$$= \sum_{k \neq j } q_{kj} {\bf P}_{ik}(t) -v_j {\bf P}_{ij}(t)$$

These are Kolmogorov's forward equations.

Remark: When the state space is infinite the forward equations may not be justified. In deriving them we interchanged a limit with an infinite sum; the interchange is always justified for the backward equations but not for forward.

Example: $S=\{0,1\}$. Then

$${\bf P}= \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right]$$

and the chain is otherwise specified by $v_0$ and $v_1$. The matrix ${\bf R}$ is

$${\bf R}= \left[\begin{array}{cc}-v_0 & v_0 \\ v_1 & -v_1 \end{array}\right]$$

The backward equations become

$${\bf P}_{00}^\prime(t) = v_0 {\bf P}_{10}(t) - v_0 {\bf P}_{00}(t)$$

$${\bf P}_{01}^\prime(t) = v_0 {\bf P}_{11}(t) - v_0 {\bf P}_{01}(t)$$

$${\bf P}_{10}^\prime(t) = v_1 {\bf P}_{00}(t) - v_1 {\bf P}_{10}(t)$$

$${\bf P}_{11}^\prime(t) = v_1 {\bf P}_{01}(t) - v_1 {\bf P}_{11}(t)$$

while the forward equations are

$${\bf P}_{00}^\prime(t) = v_1 {\bf P}_{01}(t) - v_0 {\bf P}_{00}(t)$$

$${\bf P}_{01}^\prime(t) = v_0 {\bf P}_{00}(t) - v_1 {\bf P}_{01}(t)$$

$${\bf P}_{10}^\prime(t) = v_1 {\bf P}_{11}(t) - v_0 {\bf P}_{10}(t)$$

$${\bf P}_{11}^\prime(t) = v_0 {\bf P}_{10}(t) - v_1 {\bf P}_{11}(t)$$

Add $v_1\times$first plus $v_0\times$third backward equations to get

$$v_1{\bf P}_{00}^\prime(t) + v_0{\bf P}_{10}^\prime(t) = 0$$

so

$$v_1{\bf P}_{00}(t) + v_0{\bf P}_{10}(t) = c$$

Put $t=0$ to get $c=v_1$. This gives

$${\bf P}_{10}(t) = \frac{v_1}{v_0}\left\{1-{\bf P}_{00}(t)\right\}$$

Plug this back in to the first equation and get

$${\bf P}_{00}^\prime(t) = v_1 -(v_1+ v_0) {\bf P}_{00}(t)$$

Multiply by $e^{(v_1+v_0)t}$ and get

$$\left\{e^{(v_1+v_0)t}{\bf P}_{00}(t)\right\}^\prime = v_1e^{(v_1+v_0)t}$$

which can be integrated to get

$${\bf P}_{00}(t)=\frac{v_1}{v_0+v_1} + \frac{v_0}{v_0+v_1}e^{-(v_1+v_0)t}$$

Alternative calculation:

$${\bf R}= \left[\begin{array}{cc}-v_0 & v_0 \\ v_1 & -v_1 \end{array}\right]$$

can be written as

$${\bf M} {\bf\Lambda} {\bf M}^{-1}$$

where

$${\bf M} = \left[\begin{array}{cc} 1 & v_0\\ \\ 1 & -v_1\end{array}\right]$$

$${\bf M}^{-1} = \left[\begin{array}{cc} \frac{v_1}{v_0+v_1} & \frac{v_0}{v_0+v_1} \\ \\ \frac{1}{v_0+v_1} & \frac{-1}{v_0+v_1}\end{array}\right]$$

and

$${\bf\Lambda} = \left[\begin{array}{cc} 0 & 0\\ \\ 0 & -(v_0+v_1)\end{array}\right]$$

Then

$$e^{{\bf R}t} = \sum_0^\infty {\bf R}^n t^n/n!$$

$$= \sum_0^\infty \left({\bf M} {\bf\Lambda} {\bf M}^{-1}\right)^n \frac{t^n}{n!}$$

$$= {\bf M} \left(\sum_0^\infty{\bf\Lambda}^n\frac{t^n}{n!}\right){\bf M}^{-1}$$

Now

$$\sum_0^\infty{\bf\Lambda}^n\frac{t^n}{n!} = \left[\begin{array}{cc}1 & 0 \\ 0& e^{-(v_0+v_1)t}\end{array}\right]$$

so we get

$${\bf P}(t) = e^{{\bf R}t}$$

$$= {\bf M} \left[\begin{array}{cc}1 & 0 \\ 0& e^{-(v_0+v_1)t}\end{array}\right]{\bf M}^{-1}$$

$$= {\bf P}^\infty - \frac{e^{-(v_0+v_1)t}}{v_0+v_1} {\bf R}$$

where

$${\bf P}^\infty=\left[\begin{array}{cc} \frac{v_1}{v_0+v_1} & \fra... ..._0+v_1} \\ \\ \frac{v_1}{v_0+v_1} & \frac{v_0}{v_0+v_1} \end{array}\right]$$

Notice: rows of ${\bf P}^\infty$ are a stationary initial distribution. If rows are $\pi$ then

$${\bf P}^\infty = \left[\begin{array}{c}1 \\ 1 \end{array}\right] \pi \equiv {\bf 1}\pi$$

so

$$\pi {\bf P}^\infty = (\pi {\bf 1})\pi = \pi$$

Moreover

$$\pi {\bf R}= {\bf0}$$

Fact: $\pi_0=v_1/(v_0+v_1)$ is long run fraction of time in state 0.

Fact:

$$\frac{1}{T}\int_0^T f(X(t))dt \to \sum_j \pi_j f(j)$$

Ergodic Theorem in continuous time.

Birth and Death Processes

Consider a population of $X(t)$ individuals. Suppose in next time interval $(t,t+h)$ probability of population increase of 1 (called a birth) is $\lambda_i h+o(h)$ and probability of decrease of 1 (death) is $\mu_i h +o(h)$.

Jargon: $X$ is a birth and death process.

Special cases:

All $\mu_i=0$; called a pure birth process.

All $\lambda_i=0$ (0 is absorbing): pure death process.

$\lambda_n = n\lambda$ and $\mu_n=n\mu$ is a linear birth and death process.

$\lambda_n \equiv 1$, $\mu_n \equiv 0$: Poisson Process.

$\lambda_n = n\lambda + \theta$ and $\mu_n=n\mu$ is a linear birth and death process with immigration.

Queuing Theory

Ingredients of Queuing Problem:

1: Queue input process.

2: Number of servers

3: Queue discipline: first come first serve? last in first out? pre-emptive priorities?

4: Service time distribution.

Example: Imagine customers arriving at a facility at times of a Poisson Process $N$ with rate $\lambda$. This is the input process, denoted $M$ (for Markov) in queuing literature.

Single server case:

Service distribution: exponential service times, rate $\mu$.

Queue discipline: first come first serve.

$X(t)$ = number of customers in line at time $t$.

$X$ is a Markov process called $M/M/1$ queue:

$$v_i= \lambda+\mu$$

$${\bf P}_{ij} = \begin{cases}\frac{\mu}{\mu+\lambda} & j=i-1 \ge 0 \\ \frac{\lambda}{\mu+\lambda} & j=i+1 \\ 0 & \text{otherwise} \end{cases}$$

Example: $M/M/\infty$ queue:

Customers arrive according to PP rate $\lambda$. Each customer begins service immediately. $X(t)$ is number being served at time $t$. $X$ is a birth and death process with

$$v_n= \lambda+ n \mu$$

and

$${\bf P}_{ij} = \begin{cases}\frac{i\mu}{i\mu+\lambda} & j=i-1 \ge... ...\ \frac{\lambda}{i \mu+\lambda} & j=i+1 \\ 0 & \text{otherwise} \end{cases}$$

Stationary Initial Distributions

We have seen that a stationary initial distribution $\pi$ is a probability vector solving

$$\pi {\bf R}= {\bf0}$$

Rewrite this as

$$v_j \pi_j = \sum_{i \neq j} q_{ij} \pi_i$$

Interpretation: LHS is rate at which process leaves state $j$; process is in state $j$ a fraction $\pi_j$ of time and then makes transition at rate $v_j$. RHS is total rate of arrival in state $j$. For each state $i \neq j$ $\pi_i$ is fraction of time spent in state $i$ and then $q_{ij}$ the instantaneous rate of transition from $i$ to $j$.

So equation says:

Rate of departure from $j$ balances rate of arrival to $j$. This is called balance.

Application to birth and death processes:

Equation is

$$(\lambda_j+\mu_j) \pi_j = \lambda_{j-1} \pi_{j-1} +\mu_{j+1} \pi_{j+1}$$

for $j \ge 1$ and

$$\lambda_0 \pi_0 = \mu_1 \pi_1$$

Notice that this permits the recursion

$$\pi_1 = \frac{\lambda_0}{\mu_1} \pi_0$$

$$\pi_2 = \frac{\lambda_1+\mu_1}{\mu_2}\pi_1 -\frac{\lambda_0}{\mu_2} \pi_0$$

$$= \frac{\lambda_0\lambda_1}{\mu_1\mu_2} \pi_0$$

which extends by induction to

$$\pi_k = \frac{\lambda_0\cdots \lambda_{k-1}}{\mu_1\cdots \mu_k}\pi_0$$

Apply $\sum \pi_k = 1$ to get

$$\pi_0 \left(1+\sum_{n=1}^\infty \frac{\lambda_0\cdots\lambda_{n-1}}{\mu_1\cdots\mu_n}\right) = 1$$

This gives the formula announced:

$$\pi_n = \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_n ... ...=1}^\infty \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_{n}}\right)}$$

If

$$\sum_{n=1}^\infty \frac{ \lambda_0 \cdots \lambda_{n-1}}{ \mu_1\cdots\mu_{n}}<\infty$$

then we have defined a probability vector which solves

$$\pi {\bf R}= {\bf0}$$

Since

$${\bf P}^\prime = {\bf R}{\bf P}$$

we see that

$$\left\{\pi {\bf P}(t)\right\}^\prime = 0$$

so that $\pi{\bf P}(t)$ is constant. Put $t=0$ to discover that the constant is $\pi$.