MARKOV CHAINS AGGREGATION USING DISCRETE EVENT OPTIMIZATION VIA SIMULATION

Markov chains are an important form of stochastic system representation. Recent modeling techniques supporting discrete-event Markov model composition make it easy to build large Markov chains that are difficult to analyze due to state space explosion. Lumpability is a well known condition that allows reduction in state space but its strict requirements inhibit potential use. In this paper, we introduce a discrete-event based framework to construct and aggregate Markov chains using a relaxed form of lumpability (quasi-lumpability) with an associated metric. Based on state partitions we describe a search methodology to select an optimum partition according to a metric that allows comparing Markov chains based on their respective steady states. Such optima are computed using a discrete-event optimization via simulation approach. The framework enables us to enhance our understanding of the space of finite Markov chains and the search complexity of the space.