3
$\begingroup$

Let $Q=(q_{ij})$ be the transition rate matrix of a continuous time Markov chain $\{ X_t \}$ with countable state space $M$. Let $q_i = -q_{ii}=\sum_{j \neq i}q_{ij}$, and let $\Gamma_{ij}$ be defined as: \begin{align*} \Gamma_{12} &= [\vphantom{\sum_{i=1}^{n-1}} 0,q_{12}), ~\Gamma_{13} = [q_{12},q_{12}+q_{13}), \cdots\\ \Gamma_{21} &= [\vphantom{\sum_{i=1}^{n-1}} q_1, q_1+q_{21}), ~\Gamma_{23} = [q_1+q_{21}, q_1+q_{21}+q_{23}),\cdots \\ &~\vdots \vphantom{\sum_{i=1}^{n-1}} \\ \Gamma_{n1} &= [\sum_{i=1}^{n-1}q_i, \sum_{i=1}^{n-1}q_i+q_{n1}), \cdots \\ &~\vdots \vphantom{\sum_{i=1}^{n-1}} \end{align*} Note that these intervals are disjoint and their union gives $\mathbb{R}$, i.e., $$ \Gamma_{ij} \bigcap \Gamma_{k \ell} = \emptyset \quad \text{if $(i,j) \ne (k,\ell)$} \quad \text{and} \quad \bigcup_{\substack{i,j \in M \\ i \ne j}} \Gamma_{ij} = \mathbb{R} $$

Also, define a function $h: M \times \mathbb{R} \to \mathbb{R}$ as $h(i,y)= \sum_{j \in M} (j-i)1_{\Gamma_{ij}}(y) $.

Then the continuous time Markov chain $X_t$ satisfies the SDE: $$ dX_t = \int_{\mathbb{R}}h(X_{t-},y) \nu(dt,dy) \tag{1} $$ where $\nu$ is a Poisson random measure with intensity measure $dt\times m(dy)$ and $m$ is Lebesgue measure on $\mathbb{R}$.

This result can be found on page 104 of:

  • Skorokhod, A. V. Asymptotic methods in the theory of stochastic differential equations. Vol. 78. American Mathematical Soc., 2009.

Unfortunately, for a proof the author cites a reference which I cannot find. So my question is: what is the proof of this result?

$\endgroup$
2
  • $\begingroup$ Is there a typo in Eq. (1)? If $X_t$ is taking values in the set $M$, which has no other structure in particular, then $dX_t$ doesn't really seem to make sense, and in particular shouldn't equal something real-valued. $\endgroup$ Dec 21, 2016 at 23:13
  • $\begingroup$ I don't think so, since (1) is just a shorthand for its integral form. $\endgroup$ Dec 21, 2016 at 23:14

1 Answer 1

2
$\begingroup$

Simple Poisson Process.

To gain a bit of intuition on why this result is true, it helps to consider a simple transition rate matrix: $$ Q = \begin{bmatrix} -1 & 1 & & \\ & \ddots & \ddots & \\ & & & \end{bmatrix} $$ where all of the suppressed entries are equal to zero. This $Q$ is the transition rate matrix of a simple Poisson process with rate $1$.

In this case, $$ m(\Gamma_{ij}) = \begin{cases} 1 & \text{if $j=i+1$} \\ 0 & \text{otherwise} \end{cases} $$ and for any $t \ge s \ge 0$, integrating (1) over $[s,t]$ yields, \begin{align*} X_t - X_s &= \int_s^t \int_{\mathbb{R}} 1_{\Gamma_{X_{s-} X_{s-}+1}}(y) \nu(dt,dy) \\ &= \nu((s,t),(0,1)) \end{align*} By definition of a Poisson random measure, the random variable $\nu((s,t),(0,1))$ has a Poisson distribution with rate $t-s$. Since $X_t$ also has independent increments, the process $\{ X_t \}$ started at the origin is a simple Poisson process with rate $1$, as we expected.

Proof of (1).

We will take for granted that the SDE (1) is well-posed, in the sense there exists a pathwise unique solution to (1) over any time interval.

Set $t_0=0$ and let $i_0 \in M$. The continuous time Markov chain $\{ X_t \}$ can be represented by a sequence of random jump times $\{ t_k \}$ and a Markov chain $\{ i_k \}$ called the embedded chain associated to $\{ X_t \}$. In particular, for any $t \ge 0$, $$ X_t = i_k \quad \text{if $t_k \le t < t_{k+1}$} $$ Moreover, the distributions of the jump times and embedded chain are given by $$ \mathbb{P}( t_{k+1} -t_k \mid X_{t_k} = i ) = \operatorname{Exp}(q_{i}) \;, \quad \text{and} \quad \mathbb{P}( i_{k+1}=j \mid X_{t_k} = i) = \frac{q_{ij}}{q_i} \;. $$ This representation is quite standard and shows that the process $\{X_t\}$ is a càdlàg Markov jump process. The proof given below shows that this representation is equivalent to (1) in a weak or distributional sense. BTW, this representation is used in the Doob-Gillespie algorithm for simulating continuous-time Markov chains.

Back to the proof, integrate (1) over the interval $[0,t]$ to obtain, \begin{align*} X_t - X_0 &= \sum_{i,j \in M} \int_0^t \int_{\mathbb{R}} (j-i) 1_{\Gamma_{ij}}(y) 1_{\{X_{s-}=i\}} \nu(ds,dy) \\ &= \int_0^t \sum_{i,j \in M} (j-i) 1_{\{ X_{s-}=i \}} \nu(ds, (0,q_{ij}) ) \\ &= \sum_{\substack{0 \le k \le N(t) \\ j \in M}} \int_{t_k}^{t_{k+1}} (j-i_k) \nu(ds, (0,q_{i_k j} ) \end{align*} where we have introduced the sequence of stopping times $$ t_{k+1} = \inf\left\{ t>t_k : \sum_{j \in M} \int_{t_k}^t \nu(ds, (0,q_{i_k j})) = 1 \right\} $$ with $t_0=0$ and the Markov chain $\{ i_k \}$ for $0 \le k \le N(t)$ where $N(t)$ is the total number of jumps that occur in $X_t$ over $[0,t]$. Define $t_{k,j} = \inf\{ t>t_k : \int_{t_k}^t \nu(ds, (0,q_{i_k j})) \}$ and set $\delta t_{k,j} = t_{k,j}-t_k$.

Conditional on $X_{t_k}=i_k=i$, the random variables $\delta t_{k,j}$ are mutually independent exponential random variables with $\mathbb{P}(\delta t_{k,j} \mid i_k=i) = \operatorname{Exp}(q_{ij})$ and $t_{k+1} - t_k = \min_{j \in M} \{ \delta t_{k,j} \}$, it directly follows that \begin{align*} \mathbb{P}(t_{k+1}-t_k \mid i_k=i) = \operatorname{Exp}( q_i) \quad \text{and} \quad \mathbb{P}(i_{k+1} = j \mid i_k=i) = \frac{q_{ij}}{q_i} \end{align*} which shows that the transition rate matrix of $X_t$ satisfying (1) is $Q$.

Application of (1)

While more involved than the simpler representation given in the proof, the representation (1) is particularly useful in approximation methods for continuous-time Markov chains like tau-leaping. For more info about this application, check out

$\endgroup$
1
  • $\begingroup$ I would like to know if the proof presented still works in the case of a time-inhomogeneous transition rate matrix? For example in mean-field models where the rates depend on the empirical measure of the system? Otherwise, I would like to know how to represent a Markov chain by an SDE in the case of mean-field interaction? $\endgroup$
    – SID A
    Jul 20, 2020 at 15:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .