Matching Distributions Under Structural Constraints

Phase-type distributions, the probability distributions generated by the time to absorption in a continuous-time Markov chain, are a popular tool for modeling time-dependent system behaviour. They are well understood mathematically, and so is the problem of identifying a matching distribution if given information about its moments, as well as fitting to a given distribution or a set of distribution samples. This paper looks at the problem of finding distributions from a structural perspective, namely where system behaviour is known to have a specific structure comprising parallelism, sequencing, and first- to-finish races. We present a general method that, given the coarse system structure with annotations regarding the moments of some fragments, finds a concrete phase-type distribution that fulfils the specification, if one exists. We develop the foundational underpinning in terms of constraint solving with satisfiability modulo theories, spell out the algorithmic details of a divide-and-conquer solution approach, and provide empirical evidence of feasibility, presenting a prototypical solution engine for structural distribution matching.