## 3 Proportional Lumpability
### Three Alternative Characterizations of Proportional Lumpability
The maximum proportional lumpability problem over \(X(t)\) and \(\mathcal{R}\) consists of finding the largest equivalence relation \(\sim\) such that \(\sim\subseteq\mathcal{R}\) and \(\sim\) is a proportional lumpability for \(X(t)\)._  
In [25], we proved that the maximum proportional lumpability problem has always a unique solution that can be computed in time \(O(|\mathcal{S}|^{4})\). The following characterization allows us to improve such time complexity result. We recall that given an equivalence relation \(\mathcal{R}\), \(q_{\mathcal{R}}(s)\) denotes the sum of all transition rates from \(s\) to any state \(t\) such that \((s,t)\
ot\in\mathcal{R}\). Notice that in Theorem 3, we referred to a generic equivalence relation \(\sim\); hence, since we consider only ergodic CTMCs, the first item is only necessary to cover the case in which the relation \(\sim\) is the total relation \(\mathcal{S}\times\mathcal{S}\). In the following result, we do not have to explicitly deal with it, since we consider an equivalence relation \(\mathcal{R}\) which is not total. **Theorem 5** (Characterization 3 of proportional lumpability). : _Let \(X(t)\) be an ergodic CTMC with state space \(\mathcal{S}\) and \(\mathcal{R}\) be an equivalence relation over \(\mathcal{S}\) with \(\mathcal{R}\
eq 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 equivalence relation included in \(\mathcal{R}\) such that for any equivalence classes \(S_{i},S_{j}\in\mathcal{S}/\sim\) with \(S_{i}\
eq S_{j}\) and \(s,s^{\prime}\in S_{i}\),_  
\[\frac{q(s,S_{j})}{q_{\mathcal{R}}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\mathcal{ R}}(s^{\prime})}\]  
Proof. : \(\Rightarrow)\) Suppose that \(\sim\) is the maximum proportional lumpability over \(X(t)\) and \(\mathcal{R}\). This means that \(\sim\) is the largest equivalence relation included in \(\mathcal{R}\) for which there exists a function \(\kappa\) from \(\mathcal{S}\) to \(\mathbb{R}^{+}\) such that \(\sim\) is a \(\kappa\)-proportional lumpability. This means that \(\sim\) is such that for any equivalence classes \(S_{i},S_{j}\in\mathcal{S}/\sim\) with \(S_{i}\
eq S_{j}\) and \(s,s^{\prime}\in S_{i}\)  
\[\frac{q(s,S_{j})}{\kappa(s)}=\frac{q(s^{\prime},S_{j})}{\kappa(s^{\prime})}\]  
Let \(B\) be a union of equivalence classes of \(\sim\). It holds that \(q(s,B)\
eq  
Let \(B_{i}\) be the equivalence class of \(\mathcal{R}\) to which \(s\) and \(s^{\prime}\) belong. It holds that \(S_{i}\subseteq B_{i}\). Moreover, \(\mathcal{S}\setminus B_{i}\) is a union of equivalence classes of \(\sim\). Since \(X(t)\) is ergodic, \(\mathcal{R}\
eq\mathcal{S}\times\mathcal{S}\), and \(s\sim s^{\prime}\), it has to be \(q(s,\mathcal{S}\setminus B_{i})=q_{\mathcal{R}}(s)\
eq 0\) and \(q(s^{\prime},\mathcal{S}\setminus B_{i})=q_{\mathcal{R}}(s)\
eq 0\). Hence, \(\sim\) satisfies  
\[\frac{q(s,S_{j})}{q_{\mathcal{R}}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\mathcal{R }}(s^{\prime})}\]  
Finally, \(\sim\) has to be the largest equivalence relation included in \(\mathcal{R}\) that satisfies such equations, since any equivalence relation included in \(\mathcal{R}\) satisfying such equations is a proportional lumpability and \(\sim\) is by hypothesis the largest proportional lumpability included in \(\mathcal{R}\). \(\Leftarrow\)) Suppose that \(\sim\) is the largest equivalence relation included in \(\mathcal{R}\) that satisfies the equations  
\[\frac{q(s,S_{j})}{q_{\mathcal{R}}(s)}=\frac{q(s^{\prime},S_{j})}{q_{\mathcal{R }}(s^{\prime})}\]  
Since \(\mathcal{R}\
eq\mathcal{S}\times\mathcal{S}\) and \(X(t)\) is ergodic, it holds that \(q_{\mathcal{R}}(s)\) is greater than \(0\) for each \(s\in\mathcal{S}\). Hence, \(\sim\) is a proportional lumpability included in \(\mathcal{R}\). We still have to prove that it is the largest one. Let us assume by contradiction that there exists another proportional lumpability \(\approx\) included in \(\mathcal{R}\) and larger than \(\sim\).