Paper VI: Finite Markov transfer and lumping

E5 Finite Markov transfer and lumping

On this page · Permalink · Source line 2827

Probability vectors are columns. A column stochastic matrix \(K\) has nonnegative entries and column sums one. A continuous time generator \(Q\) has nonnegative off diagonal entries and column sums zero.

Permalink · Source line 2829

Theorem E5.1: Finite Markov semigroup

If \(Q\) is a finite Markov generator, then \({\mathrm e}^{tQ}\) is column stochastic for every \(t\geq0\).

Read proof · Read statement and proof side by side · Permalink · Source line 2831 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.1

Choose \(a\geq\max_i(-Q_{ii})\). The matrix \(Q+aI\) is nonnegative, so its exponential is nonnegative. Hence

\[ {\mathrm e}^{tQ}={\mathrm e}^{-at}{\mathrm e}^{t(Q+aI)} \]

is nonnegative. Since \({{\boldsymbol{1}}}^TQ=0\), differentiation gives

\[ {{\boldsymbol{1}}}^T{\mathrm e}^{tQ}={{\boldsymbol{1}}}^T. \]

Back to statement · Read statement and proof side by side · Permalink · Source line 2835 · Claim record · Lean coverage · Code · Worked examples

Let \(\{B_1,\ldots,B_m\}\) be a partition of the fine state set. Its aggregation matrix is

\[ C_{\alpha i}={{\boldsymbol{1}}}_{\{i\in B_\alpha\}}. \]

Permalink · Source line 2846

Definition E5.2: Canonical lumping obstruction

For a linear fine transition operator \(K\), define

\[ {\operatorname{Ob}}_C(K) = (CK)|_{{\operatorname{Ker}} C} \in \mathcal B({\operatorname{Ker}} C,{\mathbb R}^m). \]

Permalink · Source line 2851 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.3: Descent through an aggregation map

Let \(C:X_f\to X_c\) be a surjective linear map between finite dimensional spaces. A unique operator \(\overline K:X_c\to X_c\) satisfying

\[ CK=\overline KC \]

exists if and only if

\[ {\operatorname{Ob}}_C(K)=0. \]

For any right inverse \(R\) of \(C\), the only possible coarse operator is

\[ \overline K=CKR, \]

and

\[ CK-\overline KC = CK(I-RC). \]

Read proof · Visual guide: The obstruction lives in the forgotten directions · Read statement and proof side by side · Permalink · Source line 2862 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.3

If \(CK=\overline KC\), then \(CK\) vanishes on \({\operatorname{Ker}} C\). Conversely, suppose the obstruction vanishes and define

\[ \overline K(Cx)=CKx. \]

If \(Cx=Cy\), then \(x-y\in{\operatorname{Ker}} C\), so the value does not depend on the representative. Surjectivity defines \(\overline K\) on all of \(X_c\), and the intertwining relation follows from the definition. It also gives uniqueness. If \(R\) is a right inverse, then

\[ \overline K=\overline KCR=CKR. \]

Substitution gives the defect identity.

Back to statement · Read statement and proof side by side · Permalink · Source line 2883 · Claim record · Lean coverage · Code · Worked examples

Corollary E5.4: Coordinate form of the lumping obstruction

For the partition aggregation above, \({\operatorname{Ker}} C\) is spanned by differences \(e_i-e_j\) with \(i\) and \(j\) in one source block. Also,

\[ {\operatorname{Ob}}_C(K)(e_i-e_j) = \left( \sum_{r\in B_\alpha}(K_{ri}-K_{rj}) \right)_{\alpha=1}^m. \]

Read proof · Visual guide: The obstruction lives in the forgotten directions · Read statement and proof side by side · Permalink · Source line 2895 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.4

Inside each block, the vectors with coordinate sum zero are spanned by differences of coordinate vectors. Applying \(CK\) gives the displayed aggregated column differences.

Back to statement · Read statement and proof side by side · Permalink · Source line 2906 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.5: Characterization of exact discrete lumping

Let \(K\) be column stochastic. A coarse column stochastic matrix \(\overline K\) satisfying

\[ CK=\overline KC \]

exists if and only if, for every source block \(B_\beta\), every pair \(i,j\in B_\beta\), and every target block \(B_\alpha\),

\[ \sum_{r\in B_\alpha}K_{ri} = \sum_{r\in B_\alpha}K_{rj}. \]

When it exists, \(\overline K\) is unique and

\[ \overline K_{\alpha\beta} = \sum_{r\in B_\alpha}K_{ri} \]

for any \(i\in B_\beta\).

Read proof · Read statement and proof side by side · Permalink · Source line 2910 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.5

The \(j\)th column of \(CK\) records the transition mass from state \(j\) into every target block. The \(j\)th column of \(\overline KC\) is the column of \(\overline K\) indexed by the source block containing \(j\). Equality therefore holds exactly under the stated condition. The formula gives uniqueness. Summing over \(\alpha\) gives one, so the coarse matrix is column stochastic.

Back to statement · Read statement and proof side by side · Permalink · Source line 2930 · Claim record · Lean coverage · Code · Worked examples

Corollary E5.6: Continuous time lumping

A coarse Markov generator \(\overline Q\) satisfying

\[ CQ=\overline QC \]

exists if and only if the aggregated rates

\[ \sum_{r\in B_\alpha}Q_{ri} \]

depend only on the source block of \(i\). In that case

\[ C{\mathrm e}^{tQ}={\mathrm e}^{t\overline Q}C \]

for every \(t\geq0\).

Read proof · Read statement and proof side by side · Permalink · Source line 2934 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.6

The characterization is the same column argument as in Theorem E5.5. The off diagonal entries of \(\overline Q\) are nonnegative and its column sums are zero. Exact semigroup intertwining follows from Proposition E3.2.

Back to statement · Read statement and proof side by side · Permalink · Source line 2950 · Claim record · Lean coverage · Code · Worked examples

Theorem E5.7: Finite horizon lumping defect

For arbitrary fine and coarse operators \(K\) and \(\overline K\), with the fixed aggregation map \(C\), set

\[ \Delta_K=CK-\overline KC. \]

Then

\[ CK^n-\overline K^nC = \sum_{j=0}^{n-1} \overline K^{n-1-j}\Delta_KK^j. \]

If \(K\) and \(\overline K\) are column stochastic, then

\[ {\left\lVert CK^n-\overline K^nC\right\rVert}_{1\to1} \leq n{\left\lVert\Delta_K\right\rVert}_{1\to1}. \]

For every probability vector \(p\), the total variation discrepancy is at most

\[ \frac n2{\left\lVert\Delta_K\right\rVert}_{1\to1}. \]

Read proof · Read statement and proof side by side · Permalink · Source line 2954 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem E5.7

Sum the telescoping identities

\[ \overline K^{n-1-j}CK^{j+1} - \overline K^{n-j}CK^j = \overline K^{n-1-j}\Delta_KK^j. \]

Stochastic matrices are contractions in the \(\ell^1\) norm. The last statement uses total variation equal to one half of the \(\ell^1\) distance.

Back to statement · Read statement and proof side by side · Permalink · Source line 2978 · Claim record · Lean coverage · Code · Worked examples

Corollary E5.8: Stationary mass descends

If \(CK=\overline KC\) and \(Kp=p\), then

\[ \overline K(Cp)=Cp. \]

Read proof · Read statement and proof side by side · Permalink · Source line 2990 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary E5.8

Apply the intertwining identity to \(p\).

Back to statement · Read statement and proof side by side · Permalink · Source line 2997 · Claim record · Lean coverage · Code · Worked examples

Exact lumping agrees at every horizon. A small violation of the block transition condition produces a visible but controlled discrepancy.

Source and conversion record

Source SHA-256: 736e615131f57daf341b6cb0600761d58950450947c85d433206148cca228333

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Read and explore

Proofs and implementation

About this work

Other resources