Current results and open questions on PH and MAP characterization

Levente Bodrog, Armin Heindl, Gábor Horväth, Miklós Telek, András HorváthDROPS (Schloss Dagstuhl – Leibniz Center for Informatics) 2008 · DOI

TL;DR

This paper tackles the challenge of uniquely and efficiently representing complex stochastic processes known as Phase-Type (PH) distributions and Markov Arrival Processes (MAPs). By developing canonical forms and transformation methods, the authors pave the way for more robust fitting and analysis of these models, crucial for various applications in performance evaluation and reliability.

What Problem Does This Paper Address?

Many real-world systems, from telecommunications networks to manufacturing processes, can be modeled using stochastic processes. Phase-Type (PH) distributions and Markov Arrival Processes (MAPs) are powerful tools for this, offering a way to capture complex arrival patterns and system behaviors. However, a significant hurdle in using these models is their non-unique representation. A single PH distribution or MAP can often be described by multiple sets of parameters (e.g., different matrices), making it difficult to compare models, develop efficient fitting algorithms, and guarantee uniqueness in results. This lack of a standard, minimal representation hinders the practical application and theoretical understanding of these models. The paper aims to address this by proposing canonical forms and methods to transform various representations into these unique forms.

Methods

The core of the paper revolves around the concept of canonical representation. For PH distributions, the authors discuss existing canonical forms for acyclic PH distributions and present a new one for PH(3) distributions. They also introduce the idea of "moments representation" and "Laplace representation" as potential candidates for minimal representations. A key technique is the two-step numerical procedure to identify if a set of moments falls within the APH(n) or PH(n) classes. This involves converting moments to a matrix representation and then checking for transformability into an acyclic Markovian or order-n Markovian representation.

For MAPs, the paper highlights the lack of extensive canonical forms, with only MAP(2) having a well-defined canonical form. They propose a similar two-step procedure for MAPs, converting moments and joint moments into a matrix representation and then to a Markovian representation. The paper also discusses similarity transforms as a way to relate different matrix representations of the same process.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic procedures rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Non-uniqueness is a major bottleneck: The paper strongly emphasizes that the non-unique representation of PH and MAP models is a fundamental problem that impedes practical use and theoretical advancement.
  • Canonical forms are essential: The development of unique, minimal, and Markovian canonical forms is presented as the solution to overcome non-uniqueness, enabling efficient fitting and analysis.
  • Hierarchy of representations: The paper implicitly suggests a hierarchy of representations, from general matrix representations to Markovian representations, and finally to canonical forms, each offering increasing levels of structure and uniqueness.
  • Moments as a practical starting point: The "moments representation" is highlighted as a practical candidate for fitting purposes, as moments often carry more intuitive information about the distribution. However, the challenge lies in determining if a given set of moments actually defines a valid PH or MAP distribution.
  • Complexity increases with order: The paper suggests that finding canonical forms becomes significantly more complex as the order of the PH or MAP distribution increases.

Key Results

  • The paper summarizes existing results on canonical forms for acyclic PH distributions and presents a canonical form for PH(3) distributions.
  • A two-step numerical procedure is outlined for identifying whether a set of moments corresponds to an APH(n) or PH(n) distribution.
  • A similar two-step procedure is proposed for MAP(n) distributions, converting moments to a Markovian representation.
  • The paper confirms that for n=2, ME(2) = PH(2) = APH(2), and the canonical forms are well-established. For n=3, the APH-PH and PH-ME borders are also considered "known."
  • The paper identifies the "outer border of the ME class" (for PH distributions) and the PH-ME border (for PH distributions) as areas where explicit procedures are less developed or "less known."

Limitations and Future Work

  • Limited canonical forms for higher orders: The paper acknowledges that canonical forms are not yet available for all PH and MAP classes, especially for higher orders (n ≥ 4 for PH, n ≥ 3 for MAP).
  • Numerical challenges: Solving spectral equations for canonical forms can be numerically challenging, particularly around discriminant limits, and explicit solutions are only available for low orders (n < 4).
  • Fitting with field data: The presented methods are effective when moments define valid PH or MAP distributions. However, with real-world "field data," moments often do not perfectly match these distributions, necessitating the development of efficient fitting methods and partial moments matching procedures, which are currently lacking.
  • ME(n) class complexity: The analysis of the ME(n) class membership is noted as more complex, requiring checks for monotone increasing distribution functions.
  • Future work: The authors suggest that research into efficient fitting methods for cases where moments don't perfectly match distributions is a dominant challenge. They also anticipate that the number of different canonical structures will increase rapidly with the order of the distributions.

Summary updated

Abstract

Stochastic processes with matrix exponential kernels have a wide range of applications due to the availability of efficient matrix analytic methods. The characterization of these processes is in progress in recent years. Basic questions like the flexibility, the degree of freedom, the most efficient (canonical) representation of these models are under study. The presentation collects a set of available results and related open questions.
BibTeX
@inproceedings{bodrog2008current,
  author = {Levente Bodrog and Armin Heindl and Gábor Horväth and Miklós Telek and András Horváth},
  title = {{Current results and open questions on PH and MAP characterization}},
  booktitle = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2008},
  doi = {10.4230/dagsemproc.07461.5},
}

Loading related content...

Figure