Truncated Time Reversible CTMC

Theorem

A time reversible CTMC that is truncated to a subset of states $A\subset S$ (by setting $q_{ij}=0$ for $i\in A,j\notin A$) and remains irreducible is also time reversible.

The limiting probabilities of the truncated chain are:

$P_j^A=\frac{P_j}{{\sum }_{i\in A}{P}_i},j\in A$

where $P_j$ are the limiting probabilities of the original (untruncated) chain.

Interpretation

Truncation simply renormalizes the probabilities over the remaining states $A$. The time reversibility property is preserved because all transitions within $A$ continue at the same rates as before.

Example: M/M/1 with Finite Capacity $N$

An M/M/1 queue where arrivals finding $N$ in the system do not enter is a truncation of the M/M/1 queue to $A=\{0,1,\dots ,N\}$.

Original M/M/1 limit probabilities: $P_j=(1-\rho ){\rho }^j$, where $\rho =\lambda /\mu$

Truncated to $A=\{0,\dots ,N\}$:

$P_j^A=\frac{(1-\rho ){\rho }^j}{{\sum }_{i=0}^N(1-\rho ){\rho }^i}=\frac{{\rho }^j}{{\sum }_{i=0}^N{\rho }^i},j=0,1,\dots ,N$

This is the well-known M/M/1/$N$ queue result.

Related

• Time Reversible CTMC
• Ergodic Birth and Death Process is Time Reversible
• 1 Queueing System