Acyclic discrete phase type distributions: properties and a parameter estimation algorithm

Andrea Bobbio, András Horváth, Marco Scarpa, Miklós TelekPerformance Evaluation 2003 · DOI

TL;DR

This paper introduces and formalizes "acyclic discrete phase type" (ADPH) distributions, a subclass of discrete phase type (DPH) distributions. It presents a novel parameter estimation algorithm for ADPHs and compares their properties, particularly their minimal coefficient of variation, to continuous phase type (CPH) distributions, showing that DPHs can offer better fits for distributions with low variability.

What Problem Does This Paper Address?

Stochastic modeling often relies on phase-type (PH) distributions to represent complex random times. While continuous phase-type (CPH) distributions have been extensively studied and applied, discrete phase-type (DPH) distributions have received less attention. This paper aims to bridge this gap by providing a deeper understanding of DPH distributions, particularly their acyclic subclass (ADPH), and developing practical tools for their application. Specifically, the authors address:

  • Lack of formalization and understanding: While DPHs were introduced, their properties and differences from CPHs were not fully explored.
  • Need for minimal representations: Like CPHs, DPH representations can be redundant. The paper seeks unique, minimal representations for ADPHs.
  • Comparison of variability: The minimal coefficient of variation (a measure of variability) is a key factor in choosing a distribution for fitting. The paper investigates how DPHs compare to CPHs in this regard, especially for distributions with low variability.
  • Lack of fitting algorithms: Existing fitting methods were primarily for CPHs. A new algorithm for estimating ADPH parameters from data was needed.
  • Approximating continuous distributions: Real-world problems often involve continuous distributions that need to be approximated by discrete models. The paper examines how to discretize continuous distributions and the impact of this process on fitting ADPHs.

Methods

The paper introduces several key methodological contributions:

  • Canonical Forms for ADPHs: The authors define acyclic-DPH (ADPH) distributions and show they admit a unique minimal representation called the "canonical form." This simplifies analysis and parameterization.
  • Minimal Coefficient of Variation Analysis: The paper derives and analyzes the minimal coefficient of variation for DPH distributions as a function of their order and mean. This allows for a direct comparison with CPH distributions.
  • Maximum Likelihood (ML) Estimation Algorithm: A novel ML estimation algorithm is developed for ADPH distributions in their canonical form. This algorithm is presented in both a z-transform domain and a more practical time-domain version. The time-domain approach is highlighted for its simplicity, stability, and efficiency.
  • Discretization of Continuous Distributions: The paper proposes a method for discretizing continuous distributions to prepare them for ADPH fitting. It also analyzes the crucial role of the discretization interval and its impact on the fitting accuracy and the required number of phases.

Datasets

The paper uses a benchmark of 10 different continuous distributions for evaluating the proposed ADPH fitting algorithm. These distributions, previously used for testing CPH fitting algorithms, include Weibull, Lognormal, Uniform, Shifted Exponential, Matrix Exponential, and Exponential distributions. The continuous distributions are discretized using a specified method before being fed into the fitting algorithm.

Key Insights and Ideas

  • DPHs offer unique advantages for low variability: The minimal coefficient of variation for DPHs can be lower than for CPHs of the same order, especially for distributions with low variability. This means DPHs can provide a better fit in such cases.
  • ADPHs have a unique "canonical form": Similar to CPHs, ADPHs can be represented uniquely in a minimal form, simplifying their analysis and parameter estimation.
  • Time-domain fitting is superior: The proposed time-domain ML estimation algorithm for ADPHs is found to be simpler to implement, more stable, and faster than z-transform domain methods, especially for high-order models.
  • Discretization is a critical step: Approximating continuous distributions with ADPHs requires discretization, and the choice of the discretization interval significantly impacts the fitting quality and the number of phases needed. A smaller interval generally leads to better accuracy but requires more phases.
  • DPHs can handle mixed durations: A key property of DPHs is their ability to represent distributions with both finite and infinite support, allowing for the modeling of systems with constant durations and random execution times within a single framework.

Key Results

  • The paper establishes that acyclic-DPH (ADPH) distributions admit a unique minimal representation called the canonical form.
  • The minimal coefficient of variation for DPHs can be lower than for CPHs of the same order, particularly when the mean is not too large compared to the order.
  • A new ML estimation algorithm for ADPHs is presented, with the time-domain version proving to be more practical.
  • The algorithm was tested on a benchmark of 10 continuous distributions, demonstrating its effectiveness, especially for distributions with low coefficient of variation and finite support.
  • The study quantifies the impact of the discretization interval on the fitting accuracy, showing that a smaller interval generally leads to better fits but requires more phases. For instance, for a Lognormal distribution (L3), a discretization step of $\delta = 0.025$ with $n=16$ phases provided a good fit.

Limitations and Future Work

  • Discretization errors: The paper acknowledges that discretizing continuous distributions introduces errors, and the quality of the fit is dependent on the discretization interval.
  • Limited applicability for sharp changes: ADPH distributions have limitations in modeling distributions with very sharp changes in their probability mass function (pmf) at high time instances, or with very heavy tails.
  • Moment constraints: ADPH distributions have bounds on their moments, meaning they cannot represent all possible positive distributions. The moments of the distribution to be fitted must be achievable by an ADPH of the chosen order.
  • Future work: The paper suggests that the developed fitting algorithm performs better than CPH fitting in specific scenarios (low coefficient of variation, finite support distributions), implying further comparative studies and applications are warranted. The authors also highlight the potential of DPHs for handling mixed durations (constant and random) within a unified framework.

Summary updated

BibTeX
@inproceedings{bobbio2003acyclic,
  author = {Andrea Bobbio and András Horváth and Marco Scarpa and Miklós Telek},
  title = {{Acyclic discrete phase type distributions: properties and a parameter estimation algorithm}},
  booktitle = {Performance Evaluation},
  year = {2003},
  doi = {10.1016/s0166-5316(03)00044-0},
}
Figure