Reasoning About Proportional Lumpability

Abstract

In this paper we reason about the notion of proportional lumpability, that generalizes the original definition of lumpability to cope with the state space explosion problem inherent to the computation of the performance indices of large stochastic models. Lumpability is based on a state aggregation technique and applies to Markov chains exhibiting some structural regularity.

Proportional lumpability formalizes the idea that the transition rates of a Markov chain can be altered by some factors in such a way that the new resulting Markov chain is lumpable. It allows one to derive exact performance indices for the original process.

We prove that the problem of computing the coarsest proportional lumpability which refines a given initial partition is well-defined, i.e., it has always a unique solution. Moreover, we introduce a polynomial time algorithm for solving the problem. This provides us further insights on both the notion of proportional lumpability and on generalizations of partition refinement techniques.

A Appendix

1.1 Proof of Lemma 1

First notice that each block $A\in \mathcal P$ can be written both as a union of blocks of $\mathcal P_1$ and as a union of blocks of $\mathcal P_2$, i.e.,

$$A=A_{11}\cup A_{12}\cup \dots \cup A_{1k_1}=A_{21}\cup A_{22}\cup \dots \cup A_{2k_2}$$

with $A_{ij}\in \mathcal P_i$.

Since $\mathcal P_1$ and $\mathcal P_2$ are proportional partitions, there exist two functions $\kappa _1,\kappa _2$ from $\mathcal S$ to $\mathbb R^+$ that witness this fact. This implies that if we take two states s and $s'$ which are not in A and are in a block $B_i$ of $\mathcal P_i$, it holds that:

$$ \frac{q(s,A)}{\kappa _i(s)} =\frac{\sum _{j=1}^{k_i} q(s,A_{ij})}{\kappa _i(s)}=\frac{\sum _{j=1}^{k_i} q(s',A_{ij})}{\kappa _i(s')}=\frac{q(s',A)}{\kappa _i(s')}$$

This last can be rewritten as:

$$q(s,A)=\frac{\kappa _i(s)}{\kappa _i(s')}q(s',A)$$

For each block $B\in \mathcal P$ we fix a representative element $b\in B$. For each $b'\in B$ there exists at least one finite sequence $b_0,b_1,\dots ,b_m$ such that $b_0=b$, $b_m=b'$ and for each $h=0,\dots ,m-1$ there exists $B_{h}$ such that $b_h,b_{h+1}\in B_h$ and either $B_{h}\in \mathcal P_1$ or $B_h\in \mathcal P_2$. For each $b'\in B$ we fix one of such sequences. For the sake of clarity, let us consider a simple case where $b,b_1\in B_0 \in \mathcal P_1$, $b_1,b_2\in B_1 \in \mathcal P_2$, and $b_2,b'\in B_2\in \mathcal P_1$. Let $A\in \mathcal P$ with $A\ne B$. In virtue of the last equation, we have:

$$q(b,A)=\frac{\kappa _1(b_1)}{\kappa _1(b)}q(b_1,A)=\frac{\kappa _1(b)}{\kappa _1(b_1)}\frac{\kappa _2(b_1)}{\kappa _2(b_2)}q(b_2,A)= \frac{\kappa _1(b)}{\kappa _1(b_1)}\frac{\kappa _2(b_1)}{\kappa _2(b_2)}\frac{\kappa _1(b_2)}{\kappa _1(b')}q(b',A) $$

In the general case we obtain:

$$q(b,A)=K(b,b') q(b',A)$$

where $K(b,b')$ is a product of fractions involving values of $\kappa _1$ and $\kappa _2$ that depends on the sequence that we have fixed from b to $b'$. Since both b and the sequence have been fixed we can define $\overline{K}(b')=K(b,b')$. As a consequence, if $b', b''\in B$ we obtain that for each $A\in \mathcal P$ with $A\ne B$ it holds

$$\overline{K}(b') q(b',A)=q(b,A)=\overline{K}(b'') q(b'',A)$$

This means that $\mathcal P$ is a proportional partition.    $\square$

1.2 Proof of Lemma 4

Let $S_j=A_1\cup \dots \cup A_n$ and $S_k=B_1\cup \dots B_m$ with $A_f,B_h\in \mathcal P_{\sim }$. Let $\kappa$ be a function witnessing that $\mathcal P_{\sim }$ is a proportional lumpability. If by contradiction there exists a block $C\in \mathcal P_{\sim }$ such that $s,s'\in C$, then we would have

$$\frac{q(s,A_f)}{\kappa (s)}=\frac{q(s',A_f)}{\kappa (s')}$$

for each $f=1,\dots , n$ and

$$\frac{q(s,B_h)}{\kappa (s)}=\frac{q(s',B_h)}{\kappa (s')}$$

for each $h=1,\dots , m$. As a consequence by summing for $f= 1,\dots , n$ and $h=1,\dots , m$ we have

$$\frac{q(s,S_j)}{\kappa (s)}=\frac{q(s',S_j)}{\kappa (s')} \text{ and } \frac{q(s, S_k)}{\kappa (s)}=\frac{q(s',S_k)}{\kappa (s')}$$

Since by hypothesis it holds $q(s,S_k)\ne 0$ and $q(s',S_k)\ne 0$ we get

$$\frac{q(s,S_j)}{q(s,S_k)}= \frac{q(s',S_j)}{q(s',S_k)}$$

which contradicts the hypothesis.    $\square$

1.3 Proof of Theorem 5

The existence of at least one solution is trivial, since the identity relation is a proportional lumpability.

As far as the uniqueness is concerned, let us consider the maximum proportional partition problem over X(t) and $\mathcal P$. Let us assume by contradiction that the set of proportional partitions that refines $\mathcal P$ has at least two different maximal elements. This means that there are two different partitions $\mathcal Q_1$ and $\mathcal Q_2$ such that:

• a. $\mathcal Q_i$ is a proportional partition;

• b. $\mathcal Q_i$ refines $\mathcal P$;

• c. each $\mathcal Q'$ coarser than $\mathcal Q_i$ and refining $\mathcal P$ is not a proportional partition.

By Lemma 1 the smallest partition $\mathcal Q$ that is coarser than both $\mathcal Q_1$ and $\mathcal Q_2$ is a proportional partition. Moreover, since both $\mathcal Q_1$ and $\mathcal Q_2$ refine $\mathcal P$, it holds that $\mathcal Q$ refines $\mathcal P$. This contradicts item c.    $\square$