## 3 Proportional Lumpability
### Three Alternative Characterizations of Proportional Lumpability
There exists a function \(\kappa\) from \(\mathcal{S}\) to \(\mathcal{R}^{+}\) such that \(\approx\) is a \(\kappa\)-proportional lumpability. This means that for any equivalence classes \(T_{i},T_{j}\in\mathcal{S}/\approx\) with \(T_{i}\
eq T_{j}\) and \(s,s^{\prime}\in T_{i}\),  
\[\frac{q(s,T_{j})}{\kappa(s)}=\frac{q(s^{\prime},T_{j})}{\kappa(s^{\prime})}\]  
As a consequence, if \(B\) is a union of equivalence classes of \(\approx\), it holds that  
\[\frac{q(s,S_{j})}{q_{\sim}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\sim}(s^{\prime} )}.\]0  
Hence, if \(q(s,B)\
eq 0\),  
\[\frac{q(s,S_{j})}{q_{\sim}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\sim}(s^{\prime} )}.\]1  
Let \(B_{i}\) be the equivalence class of \(\mathcal{R}\) to which \(s\) and \(s^{\prime}\) belong. The set \(\mathcal{S}\setminus B_{i}\) is a union of equivalence classes of \(\approx\). Therefore \(\approx\) also satisfies  
\[\frac{q(s,S_{j})}{q_{\sim}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\sim}(s^{\prime} )}.\]2  
which contradicts the fact that \(\sim\) was the largest satisfying such equations. As a consequence, the maximum proportional lumpability over a CTMC \(X(t)\) included in a given equivalence relation \(\mathcal{R}\) can be seen as a lumpability over the perturbed chain \(X^{\prime}(t)\) in which the rate \(q(s,s^{\prime})\) is divided by \(q_{\mathcal{R}}(s)\). Corollary 1: _Let \(X(t)\) be an ergodic CTMC with state space \(\mathcal{S}\) and let \(\mathcal{R}\) be an equivalence relation over \(\mathcal{S}\) with \(\mathcal{R}\
eq\mathcal{S}\times\mathcal{S}\). The relation \(\sim\) is the maximum proportional lumpability over \(X(t)\) and \(\mathcal{R}\) if and only if it is the largest lumpability included in \(\mathcal{R}\) over the CTMC \(X_{\mathcal{R}}(t)\) whose infinitesimal generator \(\mathbf{Q}_{\mathcal{R}}\) is defined as_  
\[\frac{q(s,S_{j})}{q_{\sim}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\sim}(s^{\prime} )}.\]3  
Hence, we can exploit any efficient algorithm for computing the maximum lumpability included in a given equivalence relation in order to compute the maximum proportional lumpability included in the same equivalence relation, as illustrated in Algorithm 1. The correctness of the described algorithm is immediately followed by Corollary 1, while its complexity depends on the complexity of the subroutine used for computing the maximum lumpability. **Corollary 2** (Correctness and Complexity). : _Let MaxLump be an algorithm that, given the infinitesimal generator \(\mathbf{Q}^{\prime}\) of a CTMC \(X^{\prime}(t)\) and an equivalence relation \(\mathcal{R}\) over the states of the chain, computes the largest lumpability of \(X^{\prime}(t)\) included in \(\mathcal{R}\). Let \(\mathbf{Q}\) be the infinitesimal generator of a CTMC \(X(t)\) over state space \(\mathcal{S}\) and \(\mathcal{R}\) be an equivalence relation over \(\mathcal{S}\). It holds that MaxProp\((\mathcal{S},\mathbf{Q},\mathcal{R})\) returns the largest proportional lumpability of \(X(t)\) included in \(\mathcal{R}\). Moreover MaxProp has the same time complexity as MaxLump._  
Currently, the fastest algorithm for computing the largest lumpability runs in time \(O(|\mathcal{S}|^{2}\log|\mathcal{S}|)\) if the infinitesimal generator of the chain is provided as a matrix [40; 41].