Lumping of Markov Chains with Silent Steps

By: Jassen Markovski and Nikola Trcka

Abstract:
Markov chains are one of the most important and most widely used
    mathematical models for performance analysis. Recently developed
    Markovian process algebras introduced several extensions of Markov
    chains in order to capture both the functional and performance
    behavior of a process. These models came at the expensive price of
    (partially) losing the mathematical apparatus originally developed for
    handling Markov chains. In order to perform performance evaluation, a
    pure Markov chain is obtained from the extension, but it is not proved
    that this reduction preserves performance, particularly, in the case,
    when it consists of eliminating silent (tau) steps. By treating Markov
    chains with silent steps as normal Markov chains parameterized with a
    special (large) real number tau, we define a new notion of lumping
    (aggregation), called tau-lumping. In addition, we define the notion
    of lumping for the setting of discontinuous Markov chains and justify
    tau-lumping by providing a direct connection between the two settings
    in case tau is infinite.