16.20: Chains Subordinate to the Poisson Process

\(\newcommand{\P}{\mathbb{P}}\) \(\newcommand{\E}{\mathbb{E}}\) \(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\Z}{\mathbb{Z}}\) \(\newcommand{\bs}{\boldsymbol}\)

Basic Theory

Introduction

Recall that the standard Poisson process with rate parameter \( r \in (0, \infty) \) involves three interrelated stochastic processes. First the sequence of interarrival times \(\bs{T} = (T_1, T_2, \ldots) \) is independent, and each variable has the exponential distribution with parameter \( r \). Next, the sequence of arrival times \( \bs{\tau} = (\tau_0, \tau_1, \ldots) \) is the partial sum sequence associated with the interrival sequence \( \bs{T} \): \[ \tau_n = \sum_{i=1}^n T_i, \quad n \in \N \] For \( n \in \N_+ \), the arrival time \( \tau_n \) has the gamma distribution with parameters \( n \) and \( r \). Finally, the Poisson counting process \( \bs{N} = \{N_t: t \in [0, \infty)\} \) is defined by \[ N_t = \max\{n \in \N: \tau_n \le t\}, \quad t \in [0, \infty) \] so that \( N_t \) is the number of arrivals in \( (0, t] \) for \( t \in [0, \infty) \). The counting variable \( N_t \) has the Poisson distribution with parameter \( r t \) for \( t \in [0, \infty) \). The counting process \( \bs{N} \) and the arrival time process \( \bs{\tau} \) are inverses in the sense that \( \tau_n \le t \) if and only if \( N_t \ge n \) for \( t \in [0, \infty) \) and \( n \in \N \). The Poisson counting process can be viewed as a continuous-time Markov chain.

Suppose that \( X_0 \) takes values in \( \N \) and is independent of \( \bs{N} \). Define \( X_t = X_0 + N_t \) for \( t \in [0, \infty) \). Then \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( \N \) with exponential parameter function given by \( \lambda(x) = r \) for \( x \in \N \) and jump transition matrix \( Q \) given by \( Q(x, x + 1) = 1 \) for \( x \in S \).

Proof

This follows directly from the basic structure of a continuous-time Markov chain. Given \( X_t = x \), the holding time in state \( x \in \N \) is exponential with parameter \( r \), and the next state is deterministically \( x + 1 \). Note that the addition of the variable \( X_0 \) is just to allow us the freedom of arbitrary initial distributions on the state space, as is routine with Markov processes.

Note that the Poisson process, viewed as a Markov chain is a pure birth chain. Clearly we can generalize this continuous-time Markov chain in a simple way by allowing a general embedded jump chain.

Suppose that \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a Markov chain with (countable) state space \( S \), and with constant exponential parameter \( \lambda(x) = r \in (0, \infty) \) for \( x \in S \), and jump transition matrix \( Q \). Then \( \bs{X} \) is said to be subordinate to the Poisson process with rate parameter \( r \).

1. The transition times \( (\tau_1, \tau_2, \ldots) \) are the arrival times of the Poisson process with rate \( r \).
2. The inter-transition times \( (\tau_1, \tau_2 - \tau_1, \ldots) \) are the inter-arrival times of the Poisson process with rate \( r \) (independent, and each with the exponential distribution with rate \( r \)).
3. \( \bs{N} = \{N_t: t \in [0, \infty)\} \) is the Poisson counting process, where \( N_t \) is the number of transitions in (0, t] for \( t \in [0, \infty) \).
4. The Poisson process and the jump chain \( \bs{Y} = (Y_0, Y_1, \ldots) \) are independent, and \( X_t = Y_{N_t} \) for \( t \in [0, \infty) \).

Proof

These results all follow from the basic structure of a continuous-time Markov chain.

Since all states are stable, note that we must have \( Q(x, x) = 0 \) for \( x \in S \). Note also that for \( x, \, y \in S \) with \( x \ne y \), the exponential rate parameter for the transition from \( x \) to \( y \) is \( \mu(x, y) = r Q(x, y) \). Conversely suppose that \( \mu: S^2 \to (0, \infty) \) satisfies \( \mu(x, x) = 0 \) and \( \sum_{y \in S} \mu(x, y) = r \) for every \( x \in S \). Then the Markov chain with transition rates given by \( \mu \) is subordinate to the Poisson process with rate \( r \). It's easy to construct a Markov chain subordinate to the Poisson process.

Suppose that \( \bs N = \{N_t: t \in [0, \infty)\} \) is a Poisson counting process with rate \( r \in (0, \infty) \) and that \( \bs Y = \{Y_n: n \in \N\} \) is a discrete-time Markov chain on \( S \), independent of \( \bs N \), whose transition matrix satisfies \( Q(x, x) = 0 \) for every \( x \in S \). Let \( X_t = Y_{N_t} \) for \( t \in [0, \infty) \). Then \( \bs X = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain subordinate to the Poisson process.

Generator and Transition Matrices

Next let's find the generator matrix and the transition semigroup. Suppose again that \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( S \) subordinate to the Poisson process with rate \( r \in (0, \infty) \) and with jump transition matrix \( Q \). As usual, let \( \bs P = \{P_t: t \in [0, \infty)\} \) denote the transition semigroup and \( G \) the infinitesimal generator.

The generator matrix \( G \) of \( \bs{X} \) is \( G = r (Q - I) \). Hence for \( t \in [0, \infty) \)

1. The Kolmogorov backward equation is \( P^\prime_t = r (Q - I) P_t \)
2. The Kolmogorov forward equation is \( P^\prime_t = r P_t (Q - I) \)

Proof

This follows directly from the general theory since \( G(x, x) = -\lambda(x) = -r \) for \( x \in S \) and \( G(x, y) = \lambda(x) Q(x, y) = r Q(x, y) \) for distinct \( x, \, y \in S \).

There are several ways to find the transition semigroup \( \bs{P} = \{P_t: t \in [0, \infty)\} \). The best way is a probabilistic argument using the underlying Poisson process.

For \( t \in [0, \infty) \), the transition matrix \( P_t \) is given by \[ P_t = \sum_{n=0}^\infty e^{-r t} \frac{(r t)^n}{n!} Q^n \]

Proof from the underlying Poisson process

Let \( N_t \) denote the number of transitions in \( (0, t] \) for \( t \in [0, \infty) \), so that \( \bs{N} = \{N_t: t \in [0, \infty)\} \) is the Poisson counting process. Let \( \bs{Y} = (Y_0, Y_1, \ldots) \) denote the jump chain, with transition matrix \( Q \). Then \( \bs{N} \) and \( \bs{Y} \) are independent, and \( X_t = Y_{N_t} \) for \( t \in [0, \infty) \). Conditioning we have \begin{align*} P_t(x, y) & = \P(X_t = y \mid X_0 = x) = \P\left(Y_{N_t} = y \mid Y_0 = x\right) \\ & = \sum_{n=0}^\infty \P\left(Y_{N_t} = y \mid N_t = n, Y_0 = y\right) \P(N_t = n \mid Y_0 = y) \\ & = \sum_{n=0}^\infty \P(Y_n = y \mid Y_0 = x) \P(N_t = n) = \sum_{n=0}^\infty e^{-r t} \frac{(r t)^n}{n!} Q^n(x, y) \end{align*}

Proof using the generator matrix

Note first that for \( n \in \N \), \[ G^n = [r (Q - I)]^n = r^n \sum_{k = 0}^n \binom{n}{k}(-1)^{n-k} Q^k \] Hence \begin{align*} P_t & = e^{t G} = \sum_{n=0}^\infty \frac{t^n}{n!} G^n = \sum_{n=0}^\infty \frac{t^n}{n!} r^n \sum_{k=0}^\infty \binom{n}{k} (-1)^{n-k}Q^k \\ & = \sum_{n=0}^\infty \sum_{k=0}^n \frac{(r t)^n}{k! (n - k)!} (-1)^{n-k} Q^k = \sum_{k=0}^\infty \sum_{n=k}^\infty \frac{(r t)^n}{k! (n - k)!} (-1)^{n-k} Q^k \\ & = \sum_{k=0}^\infty \frac{(r t)^k}{k!} Q^k \sum_{n=k}^\infty \frac{1}{(n - k)!}(- r t)^{n-k} = \sum_{k=0}^\infty e^{-r t} \frac{(r t)^k}{k!} Q^k \end{align*}

Potential Matrices

Next let's find the potential matrices. As with the transition matrices, we can do this in (at least) two different ways.

Suppose again that \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( S \) subordinate to the Poisson process with rate \( r \in (0, \infty) \) and with jump transition matrix \( Q \). For \( \alpha \in (0, \infty) \), the potential matrix \( U_\alpha \) of \( \bs{X} \) is \[ U_\alpha = \frac{1}{\alpha + r} \sum_{n=0}^\infty \left(\frac{r}{\alpha + r}\right)^n Q^n \]

Proof from the definition

Using the previous result, \begin{align*} U_\alpha(x, y) & = \int_0^\infty e^{-\alpha t} P_t(x, y) \, dt = \int_0^\infty e^{-\alpha t} \sum_{n=0}^\infty e^{-r t} \frac{(r t)^n}{n!} Q^n(x, y) \, dt \\ & = \sum_{n=0}^\infty Q^n(x, y) \frac{r^n}{n!} \int_0^\infty e^{-(r + \alpha) t} t^n dt \end{align*} The interchange of sum and integral is justified since the terms are nonnegative. Using the change of variables \( s = (r + \alpha) t \) gives \[ U_\alpha(x, y) = \frac{1}{\alpha + r} \sum_{n=0}^\infty \left(\frac{r}{\alpha + r}\right)^n \frac{1}{n!} Q^n(x, y) \int_0^\infty e^{-s t} s^n \, ds \] The last integral is \( n! \).

Proof using the generator

From the result above, \[ \alpha I - G = \alpha I - r (Q - I) = (\alpha + r) I - r Q = (\alpha + r)\left(I - \frac{r}{\alpha + r} Q\right) \] Since \( \left\| \frac{r}{\alpha + r} Q \right\| = \frac{r}{\alpha + r} \lt 1 \) we have \[ (\alpha I - G)^{-1} = \frac{1}{\alpha + r}\left(I - \frac{r}{\alpha + r} Q\right)^{-1} = \frac{1}{\alpha + r} \sum_{n=0}^\infty \left(\frac{r}{\alpha + r}\right)^n Q^n \]

Recall that for \( p \in (0, 1) \), the \( p \)-potential matrix of the jump chain \( \bs{Y} \) is \( R_p = \sum_{n=0}^\infty p^n Q^n \). Hence we have the following nice relationship between the potential matrix of \( \bs{X} \) and the potential matrix of \( \bs{Y} \): \[ U_\alpha = \frac{1}{\alpha + r} R_{r / (\alpha + r)} \] Next recall that \( \alpha U_\alpha(x, \cdot) \) is the probability density function of \( X_T \) given \( X_0 = x \), where \( T \) has the exponential distribution with parameter \( \alpha \) and is independent of \( \bs{X} \). On the other hand, \( \alpha U_\alpha(x, \cdot) = (1 - p) R_p(x, \cdot) \) where \( p = r \big/ (\alpha + r) \). We know from our study of discrete potentials that \( (1 - p) R_p(x, \cdot) \) is the probability density function of \( Y_M \) where \( M \) has the geometric distribution on \( \N \) with parameter \( 1 - p \) and is independent of \( \bs{Y} \). But also \( X_T = Y_{N_T} \). So it follows that if \( T \) has the exponential distribution with parameter \( \alpha \), \( \bs{N} = \{N_t: t \in [0, \infty)\} \) is a Poisson process with rate \( r \), and is independent of \( T \), then \( N_T \) has the geometric distribution on \( \N \) with parameter \( \alpha \big/ (\alpha + r) \). Of course, we could easily verify this directly, but it's still fun to see such connections.

Limiting Behavior and Stationary Distributions

Once again, suppose that \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( S \) subordinate to the Poisson process with rate \( r \in (0, \infty) \) and with jump transition matrix \( Q \). Let \( \bs{Y} = \{Y_n: n \in \N\} \) denote the jump process. The limiting behavior and stationary distributions of \( \bs{X} \) are closely related to those of \( \bs{Y} \).

Suppose that \( \bs{X} \) (and hence \( \bs{Y} \)) are irreducible and positive recurrent

1. \( g: S \to (0, \infty) \) is invariant for \( \bs{X} \) if and only if \( g \) is invariant for \( \bs{Y} \).
2. \( f \) is an invariant probability density function for \( \bs{X} \) if and only if \( f \) is an invariant probability density function for \( \bs{Y} \).
3. \( \bs{X} \) is null recurrent if and only if \( \bs{Y} \) is null recurrent, and in this case, \( \lim_{n \to \infty} Q^n(x, y) = \lim_{t \to \infty} P_t(x, y) = 0 \) for \( (x, y) \in S^2 \).
4. \( \bs{X} \) is positive recurrent if and only if \( \bs{Y} \) is positive recurrent. If \( \bs{Y} \) is aperiodic, then \( \lim_{n \to \infty} Q^n(x, y) = \lim_{t \to \infty} P_t(x, y) = f(y) \) for \( (x, y) \in S^2 \), where \( f \) is the invariant probability density function.

Proof

All of these results follow from the basic theory of stationary and limiting distributions for continuous-time chains, and the fact that the exponential parameter function \( \lambda \) is constant.

Time Reversal

Once again, suppose that \( \bs{X} = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( S \) subordinate to the Poisson process with rate \( r \in (0, \infty) \) and with jump transition matrix \( Q \). Let \( \bs{Y} = \{Y_n: n \in \N\} \) denote the jump process. We assume that \( \bs X \) (and hence \( \bs Y \)) are irreducible. The time reversal of \( \bs X \) is closely related to that of \( \bs Y \).

Suppose that \( g: S \to (0, \infty) \) is invariant for \( \bs X \). The time reversal \( \hat{\bs X} \) with respect to \( g \) is also subordinate to the Poisson process with rate \( r \). The jump chain \( \hat{\bs Y} \) of \( \hat{\bs X} \) is the (discrete) time reversal of \( \bs Y \) with respect to \( g \).

Proof

From the previous result, \( g \) is also invariant for \( \bs Y \). From the general theory of time reversal, \( \hat{\bs X} \) has the same exponential parameter function as \( \bs X \) (namely the constant function \( r \)) and so is also subordinate to the Poisson process with rate \( r \). Finally, the jump chain \( \hat{\bs Y} \) of \( \hat{\bs X} \) is the reversal of \( \bs Y \) with respect to \( r g \) and hence also with respect to \( g \).

In particular, \( \bs X \) is reversible with respect to \( g \) if and only if \( \bs Y \) is reversible with respect to \( g \). As noted earlier, \( \bs X \) and \( \bs Y \) are of the same type: both transient or both null recurrent or both positive recurrent. In the recurrent case, there exists a positive invariant function that is unique up to multiplication by constants. In this case, the reversal of \( \bs X \) is unique, and is the chain subordinate to the Poisson process with rate \( r \) whose jump chain is the reversal of \( \bs Y \).

Uniform Chains

In the construction above for a Markov chain \( \bs X = \{X_t: t \in [0, \infty)\} \) that is subordinate to the Poisson process with rate \( r \) and jump transition kernel \( Q \), we assumed of course that \( Q(x, x) = 0 \) for every \( x \in S \). So there are no absorbing states and the sequence \( (\tau_1, \tau_2, \ldots) \) of arrival times of the Poisson process are the jump times of the chain \( \bs X \). However in our introduction to continuous-time chains, we saw that the general construction of a chain starting with the function \( \lambda \) and the transition matrix \( Q \) works without this assumption on \( Q \), although the exponential parameters and transition probabilities change. The same idea works here.

Suppose that \( \bs N = \{N_t: t \in [0, \infty)\} \) is a counting Poisson process with rate \( r \in (0, \infty) \) and that \( \bs Y = \{Y_n: n \in \N\} \) is a discrete-time Markov chain with transition matrix \( Q \) on \( S \times S \) satisfying \( Q(x, x) \lt 1 \) for \( x \in S \). Assume also that \( \bs N \) and \( \bs Y \) are independent. Define \( X_t = Y_{N_t} \) for \( t \in [0, \infty) \). Then \( \bs X = \{X_t: t \in [0, \infty)\} \) is a continuous-Markov chain with exponential parameter function \( \lambda(x) = r [1 - Q(x, x)] \) for \( x \in S \) and jump transition matrix \( \tilde Q \) given by \[ \tilde Q(x, y) = \frac{Q(x, y)}{1 - Q(x, x)}, \quad (x, y) \in S^2, \, x \ne y \]

Proof

This follows from the result in the introduction.

The Markov chain constructed above is no longer a chain subordinate to the Poisson process by our definition above, since the exponential parameter function is not constant, and the transition times of \( \bs X \) are no longer the arrival times of the Poisson process. Nonetheless, many of the basic results above still apply.

Let \( \bs X = \{X_t: t \in [0, \infty)\} \) be the Markov chain constructed in the previous theorem. Then

1. For \( t \in [0, \infty) \), the transition matrix \( P_t \) is given by \[ P_t = \sum_{n=0}^\infty e^{- r t} \frac{(r t)^n}{n!} Q^n \]
2. For \( \alpha \in (0, \infty) \), the \( \alpha \) potential matrix is given by \[ U_\alpha = \frac{1}{\alpha + r} \sum_{n=0}^\infty \left(\frac{r}{\alpha + r}\right)^n Q^n \]
3. The generator matrix is \( G = r (Q - I) \)
4. \( g: S \to (0, \infty) \) is invariant for \( \bs X \) if and only if \( g \) is invariant for \( \bs Y \).

Proof

The proofs are just as before.

It's a remarkable fact that every continuous-time Markov chain with bounded exponential parameters can be constructed as in the last theorem, a process known as uniformization. The name comes from the fact that in the construction, the exponential parameters become constant, but at the expense of allowing the embedded discrete-time chain to jump from a state back to that state. To review the definition, suppose that \( \bs X = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain on \( S \) with transition semigroup \( \bs P = \{P_t: t \in [0, \infty)\} \), exponential parameter function \( \lambda \) and jump transition matrix \( Q \). Then \( \bs P \) is uniform if \( P_t(x, x) \to 1 \) as \( t \downarrow 0 \) uniformly in \( x \), or equivalently if \( \lambda \) is bounded.

Suppose that \( \lambda: S \to (0, \infty) \) is bounded and that \( Q \) is a transition matrix on \( S \) with \( Q(x, x) = 0 \) for every \( x \in S \). Let \( r \in (0, \infty) \) be an upper bound on \( \lambda \) and \( \bs N = \{N_t: t \in [0, \infty)\} \) a Poisson counting process with rate \( r \). Define the transition matrix \( \hat Q \) on \( S \) by \begin{align*} \hat Q(x, x) & = 1 - \frac{\lambda(x)}{r} \quad x \in S \\ \hat Q(x, y) & = \frac{\lambda(x)}{r} Q(x, y) \quad (x, y) \in S^2, \, x \ne y \end{align*} and let \( \bs Y = \{Y_n: n \in \N\} \) be a discrete-time Markov chain with transition matrix \( \hat Q \), independent of \( \bs N \). Define \( X_t = Y_{N_t} \) for \( t \in [0, \infty) \). Then \( \bs X = \{X_t: t \in [0, \infty)\} \) is a continuous-time Markov chain with exponential parameter function \( \lambda \) and jump transition matrix \( Q \).

Proof

Note that \( \hat Q(x, y) \ge 0 \) for every \( (x, y) \in S^2 \) and \( \sum_{y \in S} \hat Q(x, y) = 1 \) for every \( x \in S \). Thus \( \hat Q \) is a transition matrix on \( S \). Note also that \( \hat Q(x, x) \lt 1 \) for every \( x \in S \). By construction, \( \lambda(x) = r[1 - \hat Q(x, x)] \) for \( x \in S \) and \[ Q(x, y) = \frac{\hat Q(x, y)}{1 - \hat Q(x, x)}, \quad (x, y) \in S^2, \, x \ne y \] So the result now follows from the theorem above.

Note in particular that if the state space \( S \) is finite then of course \( \lambda \) is bounded so the previous theorem applies. The theorem is useful for simulating a continuous-time Markov chain, since the Poisson process and discrete-time chains are simple to simulate. In addition, we have nice representations for the transition matrices, potential matrices, and the generator matrix.

Suppose that \( \bs X = \{X_t: t \in [0, \infty\} \) is a continuous-time Markov chain on \( S \) with bounded exponential parameter function \( \lambda: S \to (0, \infty) \) and jump transition matrix \( Q \). Define \( r \) and \( \hat Q \) as in the last theorem. Then

1. For \( t \in [0, \infty) \), the transition matrix \( P_t \) is given by \[ P_t = \sum_{n=0}^\infty e^{- r t} \frac{(r t)^n}{n!} \hat Q^n \]
2. For \( \alpha \in (0, \infty) \), the \( \alpha \) potential matrix is given by \[ U_\alpha = \frac{1}{\alpha + r} \sum_{n=0}^\infty \left(\frac{r}{\alpha + r}\right)^n \hat Q^n \]
3. The generator matrix is \( G = r (\hat Q - I) \)
4. \( g: S \to (0, \infty) \) is invariant for \( \bs X \) if and only if \( g \) is invariant for \( \hat Q \).

Proof

These results follow from the theorem above.

Examples

The Two-State Chain

The following exercise applies the uniformization method to the two-state chain.

Consider the continuous-time Markov chain \( \bs X = \{X_t: t \in [0, \infty)\} \) on \( S = \{0, 1\} \) with exponential parameter function \( \lambda = (a, b) \), where \( a, \, b \in (0, \infty) \). Thus, states 0 and 1 are stable and the jump chain has transition matrix \[ Q = \left[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right] \] Let \( r = a + b \), an upper bound on \( \lambda \). Show that

1. \( \hat Q = \frac{1}{a + b} \left[\begin{matrix} b & a \\ b & a \end{matrix} \right] \)
2. \( G = \left[\begin{matrix} -a & a \\ b & - b \end{matrix}\right] \)
3. \( P_t = \hat Q - \frac{1}{a + b} e^{-(a + b) t} G \) for \( t \in [0, \infty) \)
4. \( U_\alpha = \frac{1}{\alpha} \hat Q - \frac{1}{(\alpha + a + b)(a + b)} G \) for \( \alpha \in (0, \infty) \)

Proof

The form of \( \hat Q \) follows easily from the definition above. Note that the rows of \( \hat Q \) are the invariant PDF. It then follows that \( \hat Q^n = \hat Q \) for \( n \in \N_+ \). The results for the transition matrix \( P_t \) and the potential \( U_\alpha \) then follow easily from the theorem above.

Although we have obtained all of these results for the two-state chain before, the derivation based on uniformization is the easiest.