Graph-Based Product Form
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911241762504704 |
|---|---|
| author | Comte, Céline Grosof, Isaac |
| author_facet | Comte, Céline Grosof, Isaac |
| contents | 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". 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13890 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph-Based Product Form Comte, Céline Grosof, Isaac Probability Performance 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". 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. |
| title | Graph-Based Product Form |
| topic | Probability Performance |
| url | https://arxiv.org/abs/2502.13890 |