6.1 Non-disjoint coupling

In this section, we further discuss stochastic complementation, introduced in Subsection 2.8.2. As defined in [61], to apply stochastic complementation in a Markov chain its state space ${\cal {S}}$ is partitioned into two disjoint subsets, ${\cal{A}}$ and $\overline{{\cal{A}}}$. Observe that, if the stationary probability vector, $\mbox{\boldmath {$\alpha$}}$, of the stochastic complement of states in ${\cal{A}}$ is known, we can compute the stationary distribution of states in a subset ${\cal{B}}$ of ${\cal{A}}$ conditioned on being in ${\cal{B}}$, as:

$$\mbox{\boldmath {$\beta$}}= \frac{\mbox{\boldmath {$\alpha$}... ...}{\mbox{\boldmath {$\alpha$}}[{\cal{B}}]\cdot{\mathbf{1}}^T} ,$$ (6.2)

and this allows us to extend the concept of stochastic complementation to cases where we use a covering, not a partitioning, of the state space, that is, ${\cal{S}}= {\cal{A}}_1 \cup {\cal{A}}_2$, but the subsets ${\cal{A}}_1$ and ${\cal{A}}_2$^6.1 are not necessarily disjoint. This is motivated by the fact that, in certain cases, it may be advantageous to compute the stochastic complement for subsets of states that are not disjoint (see Lemma 2.8.2).

Definition

 (Singular states)  Consider a covering of the state space ${\cal{S}}= {\cal{A}}_1 \cup {\cal{A}}_2$. Any state $h \in {\cal{S}}$ that belongs to more than one subset in the covering is said to be a singular state.

Lemma

 (Non-disjoint coupling)  Consider an ergodic CTMC with state space ${\cal {S}}$ covered by the subsets ${\cal{A}}_1$ and ${\cal{A}}_2$. Let $\mbox{\boldmath {$\alpha$}}_1$ and $\mbox{\boldmath {$\alpha$}}_2$ be their stationary probability vectors for the respective stochastic complement, also assumed to be ergodic. Let $s$ be the number of singular states in the covering, and assume, without loss of generality, that the sets ${\cal{B}}_{1}$ and ${\cal{B}}_{2}$ of non-singular states in ${\cal{A}}_1$ and ${\cal{A}}_2$ respectively are not empty. Compute $\mbox{\boldmath {$\beta$}}_1$ and $\mbox{\boldmath {$\beta$}}_2$, the stationary probabilities for the states in ${\cal{B}}_1$ and ${\cal{B}}_2$ conditioned on being in ${\cal{B}}_1$ and ${\cal{B}}_2$ for the stochastic complements of states in ${\cal{A}}_1$ and ${\cal{A}}_2$, respectively, as in Eq.(6.2). Define a new ``coupled'' CTMC with state space given by two macro states, for ${\cal{B}}_1$ and ${\cal{B}}_2$, plus the $s$ singular states. For ease of notation, let ${\cal{B}}_{2+i}$ denote the set containing the $i^{\rm th}$ singular state only and let its conditional stationary probability $\beta_{2+i} = 1$, for $i =1,\ldots,s$. Let the infinitesimal generator matrix ${\mathbf{C}}$ of this CTMC be:

$${\mathbf{C}}[i,j] = \mbox{\boldmath {$\beta$}}_i \cdot {\mathbf{Q}}[{\cal{B}}_i,{\cal{B}}_j] \cdot {\mathbf{1}}^T.$$ (6.3)

Then, the stationary probability vector ${\mathbf{a}}$ of this CTMC gives the correct coupling factors corresponding to this covering, that is (after an appropriate reordering of the entries in $\mbox{\boldmath {$\pi$}}$):

$${\mathbf{a}}[i] = \mbox{\boldmath {$\pi$}}[{\cal{B}}_i] \cdot {\mathbf{1}}^T, ~ i = 1,\ldots,2+s$$ (6.4)

which then implies

$$\mbox{\boldmath {$\pi$}}= [{\mathbf{a}}[1] \cdot \mbox{\bol... ... {$\beta$}}_{2}, {\mathbf{a}}[2],\ldots, {\mathbf{a}}[2+s]] .$$ (6.5)

Proof: From its definition, it follows that the off-diagonal elements of ${\mathbf{C}}$ are non-negative and its rows sum to zero because the diagonal elements are defined to be the negative of the row sums.

Matrix ${\mathbf{C}}$ is clearly irreducible, this follows directly from its probabilistic interpretation and the fact that the original process is irreducible. Assuming that ${\mathbf{C}}$ is also aperiodic, hence ergodic, we now need to show that the stationary probability vector ${\mathbf{a}}= [{\mathbf{a}}[1], \ldots, {\mathbf{a}}[s+2]]$ satisfies Eq.(6.4). Since the stationary probability vector $\mbox{\boldmath {$\alpha$}}_i$ of the stochastic complement of ${\cal{A}}_i$ satisfies $\mbox{\boldmath {$\alpha$}}_i = \mbox{\boldmath {$\pi$}}[{\cal{A}}]/(\mbox{\boldmath {$\pi$}}[{\cal{A}}] \cdot{\mathbf{1}}^T)~~i = 1,2$, we get that

$$\mbox{\boldmath {$\beta$}}_i = \frac{\mbox{\boldmath {$\al... ..._i]}{\mbox{\boldmath {$\pi$}}[{\cal{B}}_i] \cdot {\mathbf{e}}}$$ (6.6)

while $\beta_i = 1 = \mbox{\boldmath {$\pi$}}[{\cal{B}}_i]/(\mbox{\boldmath {$\pi$}}[{\cal{B}}_i] \cdot {\mathbf{e}})$ by definition for $i = 3,\ldots,2+s$. We want to prove that the stationary probability vector ${\mathbf{a}}$ of the CTMC with infinitesimal generator ${\mathbf{C}}$ is $[\mbox{\boldmath {$\pi$}}[{\cal{B}}_1]\cdot{\mathbf{e}},\ldots,\mbox{\boldmath {$\pi$}}[{\cal{B}}_{k+s}]\cdot{\mathbf{e}}]$ and so Eq.(6.5) holds. For $j = 1,\ldots,2+s$, recalling that $\mbox{\boldmath {$\pi$}}\cdot {\mathbf{Q}}= {\mathbf{0}}$, we have:

$$\begin{eqnarray*} ({\mathbf{a}}{\mathbf{C}})[i] & = &\sum_{j=1}^{2+s} {\mathbf{a... ...t {\mathbf{Q}}[{\cal{B}}_i,{\cal{B}}_j] \cdot {\mathbf{1}}^T = 0 \end{eqnarray*}$$

Thus, $[\mbox{\boldmath {$\pi$}}[{\cal{B}}_1]\cdot{\mathbf{e}},\ldots,\mbox{\boldmath {$\pi$}}[{\cal{B}}_{k+s}]\cdot{\mathbf{e}}]$ is a solution of ${\mathbf{a}}\cdot {\mathbf{C}}={\mathbf{0}}$, and, since its entries sum to one, it is the stationary probability vector of the coupled CTMC. $\Box$

It is important to note that the effectiveness of stochastic complementation is based on divide-and-conquer: computing the stationary distribution of each stochastic complement of the original CTMC must be easier than computing the stationary distribution of the original CTMC. Computing the product ${\mathbf{Q}}[{\cal{A}},\overline{{\cal{A}}}] (-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}])^{-1}{\mathbf{Q}}[\overline{{\cal{A}}},{\cal{A}}]$ in Eq.(2.28) can be costly since $(-{\mathbf{Q}}[\overline{{\cal{A}}},\overline{{\cal{A}}}])^{-1}$ is effectively an inverse, thus often full. However, there are cases where we can take advantage of the special structure of the CTMC and short-circuit this computation such as the ``single-entry'' case as defined and described in Lemma 2.8.2 of Subsection 2.8.2.