My continuous time Markov chain describes transitions between subsets of ${\{1,\dots, n\}}$. Only elementary transitions are considered (+1 element, -1 element), and the empty subset is absorbing. The corresponding rates matrix $Q$ is of size $2^n$ because it is indexed by these subsets, but it can be described with only $n^2$ values:
- $n$ "loss" values quantifying the rates of transitions loosing 1 element: $(E_1,\dots,E_n)$
- $n^2-n$ "gain" values quantifying the rates of transitions gaining 1 element from another element already in the set: $(D_{12}, D_{13},\dots,D_{1n},D_{21}, D_{23},\dots,D_{2n},\dots)$
For instance with $n=3$, only the following values are required.. (real, positive or zero)
$\left[\begin{matrix} E_1 & D_{12} & D_{13} \\ D_{21} & E_2 & D_{23} \\ D_{31} & D_{32} & E_3 \end{matrix}\right]$
.. to fully specify $Q$:
$ \begin{array}{c|cccccccc} Q & \varnothing & \{1\} & \{2\} & \{3\} & \{1,2\} & \{1,3\} & \{2,3\} & \{1,2,3\} \\\hline \varnothing & \cdot & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \{1\} & E_1 & \cdot & 0 & 0 & D_{12} & D_{13} & 0 & 0 \\ \{2\} & E_2 & 0 & \cdot & 0 & D_{21} & 0 & D_{23} & 0 \\ \{3\} & E_3 & 0 & 0 & \cdot & 0 & D_{31} & D_{32} & 0 \\ \{1,2\} & 0 & E_2 & E_1 & 0 & \cdot & 0 & 0 & D_{13} + D_{23} \\ \{1,3\} & 0 & E_3 & 0 & E_1 & 0 & \cdot & 0 & D_{12} + D_{32}\\ \{2,3\} & 0 & 0 & E_3 & E_2 & 0 & 0 & \cdot & D_{21} + D_{31}\\ \{1,2,3\} & 0 & 0 & 0 & 0 & E_3 & E_2 & E_1 & \cdot\\ \end{array} $
(diagonal elements are set so that every row sums to zero)
More generally, for every positive integer $n$ and for every two distinct subsets of $\{1,\dots,n\}$ $u$ and $v$ with $v$ non-empty, there is:
$\displaystyle\forall i \in \{1,\dots,n\},\quad v = u \setminus \{i\} \implies Q_{uv} = E_i\quad$ (elementary loss)
$\displaystyle\forall i \in \{1,\dots,n\},\quad v = u \cup \{i\} \implies Q_{uv} = \sum_{j\in u}{Dji}\quad$ (elementary gain)
$\displaystyle u = \varnothing \implies Q_{uv} = 0\quad$ (absorbing empty set)
$\displaystyle|v| \geqslant |u| + 2 \implies Q_{uv} = 0\quad$ (non-elementary gain)
$\displaystyle|v| \leqslant |u| - 2 \implies Q_{uv} = 0$ (non-elementary loss)
$\displaystyle Q_{uu} = -\sum_{v\neq u}{Q_{uv}}\quad$ (zero-sum rows)
Given that $Q$ is very sparse, very structured, and contains very few information with respect to its size, does it exhibit properties that would make
$e^{Qt}$
efficient to compute, for positive, real values of $t$?