Graph-based product form
Аннотация
Product-form stationary distributions in Markov chains have been a foundational advance and driving force in our understanding of stochastic systems. In this paper, we introduce a new product-form relationship that we call “graph-based product form”. The key feature of graph-based product form is that it can be characterized by a simple graph-traversal algorithm, without solving the balance equations or guessing the form of the stationary distribution. As our first main contribution, we prove that two states of the Markov chain are in graph-based product form if and only if the following two equivalent conditions are satisfied: (i) a cut-based condition, reminiscent of classical results on product-form queueing systems, and (ii) a novel characterization that we call joint-ancestor freeness. The latter characterization allows us in particular to introduce a graph-traversal algorithm that checks product-form relationships for all pairs of states, with time complexity $$O(|V|^2 |E|)$$, if the Markov chain has a finite transition graph $$G = (V, E)$$. We then generalize graph-based product form to encompass more complex relationships, which we call “higher-level product form”, and we again show these can be identified via a graph-traversal algorithm when the Markov chain has a finite state space. Lastly, we identify several examples from queueing theory that satisfy this product-form relationship.