Handling the state space explosion of Markov chains : how lumping introduces imprecision (almost) inevitably
Alexander Erreygers, Jasper De Bock · Ghent University Academic Bibliography (Ghent University) · 2017
Markov Chains (MCs) are used ubiquitously to model dynamical systems with uncertain dynamics. In many cases, the number of states that is required to accurately describe the dynamics of such a system grows exponentially with respect to the dimensions of the system, a well-known phenomenon that is called *state space explosion*. This limits the applicability of MC models to systems with relatively small dimensions. One way to reduce the number of states of a MC is to *lump* together states, for instance because they correspond to the same higher-order description. This lumping yields a reduced stochastic process, which, at least for a given initial distribution, is an inhomogeneous MC. However, in general, determining its (time-dependent) dynamics---and hence also the temporal evolution of the probability distribution over the lumps---is impossible without first determining the temporal evolution of the distribution of the states of the original MC. Therefore, so far, this approach was limited to the special case where the reduced MC is homogeneous, because its constant dynamics are then easily determined (Tian and Kannan, 2006). We here extend this approach by showing that, in general, the unknown dynamics of the reduced MC can be characterised by a so-called imprecise MC, in the sense that it provides a guaranteed outer approximation of the reduced MC. Using this imprecise MC, it becomes possible to draw approximate inferences about the original MC, without suffering from the state space explosion problem. We focus here on inferences about its steady-state probability distribution. First, we study how the ergodic properties of the original MC translate to the reduced imprecise MC, and then use the methods outlined in (Erreygers and De Bock, 2017) to provide bounds on the expectation operator that corresponds to the steady-state distribution of the former. Second, we also propose an alternative method to determine (possibly different) bounds on those same expectations, the strength of which is the subject of ongoing research.