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.

Reasoning About Proportional Lumpability

Piazza C.;
2021-01-01

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.
2021
978-3-030-85171-2
978-3-030-85172-9
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1211826
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact