The scale factor: a new degree of freedom in phase-type approximation

Andrea Bobbio, András Horváth, Miklós TelekPerformance Evaluation 2004 · DOI

TL;DR

This paper introduces a unified framework for approximating probability distributions using both discrete (DPH) and continuous (CPH) phase-type models. By incorporating a "scale factor" into DPH distributions, the authors demonstrate that DPH and CPH models can be seen as part of a single, flexible class, allowing for a more nuanced choice between discrete and continuous approximations based on the specific application.

What Problem Does This Paper Address?

In applied stochastic modeling, accurately approximating complex probability distributions is crucial for analyzing systems. Phase-type (PH) distributions, both discrete (DPH) and continuous (CPH), are powerful tools for this purpose. However, DPH and CPH distributions have traditionally been treated as distinct classes with different properties and fitting challenges. This paper addresses the gap in understanding the relationship between these two classes and how to best leverage them for approximation. Specifically, it tackles the question of when to choose a discrete (DPH) versus a continuous (CPH) approximation, and how to optimize this choice. The authors highlight that while DPH distributions can approximate CPH distributions as a scale factor approaches zero, there are unique properties of DPH distributions (like finite support and deterministic delays) that CPH distributions cannot capture.

Methods

The core contribution of this paper is the introduction of a scale factor ($\delta$) for DPH distributions. This parameter effectively bridges the gap between discrete steps in a DPH model and continuous time. By defining a scaled DPH variable $\tau = \delta u$, where $u$ is an unscaled DPH variable, the authors show that the properties of DPH distributions can be continuously transformed towards those of CPH distributions as $\delta \to 0$.

Key methodological aspects include:

  • Unified Framework: Treating DPH and CPH distributions as members of a single class parameterized by the scale factor $\delta$.
  • Canonical Forms: Utilizing canonical representations for acyclic DPH and CPH distributions to simplify parameter estimation and analysis.
  • Distance Measure: Employing a squared area difference between cumulative distribution functions (CDFs) as a unified metric to evaluate the goodness of fit for both discrete and continuous approximations. This allows for direct comparison of DPH and CPH fits.
  • Theoretical Analysis: Deriving theorems regarding the minimum coefficient of variation for both unscaled and scaled DPH distributions, and showing its convergence to the CPH minimum as $\delta \to 0$.
  • Experimental Evaluation: Conducting extensive numerical experiments to demonstrate how the choice of the scale factor $\delta$ influences the approximation quality for various distributions (e.g., Lognormal, Uniform) with different coefficients of variation and support properties.

Datasets

The paper does not introduce new datasets. Instead, it uses well-established benchmark distributions from previous research for evaluating approximation methods. These include:

  • Lognormal distributions: Specifically, L3 (with low coefficient of variation) and L1 (with high coefficient of variation).
  • Uniform distributions: U1 ([0,1]) and U2 ([1,2]).

These distributions are chosen to represent a range of characteristics, including different coefficients of variation and support properties (finite vs. infinite).

Key Insights and Ideas

  • Scale Factor as a Unifier: The scale factor $\delta$ is the central concept, allowing DPH and CPH distributions to be viewed as a continuum. This provides a principled way to choose between them.
  • DPH Uniqueness: DPH distributions offer unique advantages over CPH distributions, particularly in their ability to model finite support and deterministic delays, which are crucial for capturing certain real-world phenomena like periodic behaviors or precise time intervals.
  • Optimal $\delta$ for Fitting: For any given distribution and order $n$, there exists an optimal scale factor $\delta_{opt}$ that minimizes the approximation error. If $\delta_{opt} = 0$, a CPH distribution is the best fit; if $\delta_{opt} > 0$, a DPH distribution provides a better approximation.
  • Low CV Distributions: For distributions with low coefficients of variation, the optimal $\delta$ tends to be small, suggesting that CPH approximations are often sufficient. However, DPH can still offer a closer fit.
  • High CV and Finite Support: For distributions with high coefficients of variation or finite support, the optimal $\delta$ can be larger, and DPH distributions can offer significantly better approximations, especially when the original distribution exhibits discontinuities.
  • Transient Behavior: The scale factor $\delta$ also plays a critical role in approximating the transient behavior of stochastic systems, with optimal $\delta$ values often aligning with those found for fitting individual distributions.

Key Results

  • Convergence: The paper demonstrates theoretically that as the scale factor $\delta$ approaches zero, the properties of scaled DPH distributions (like the minimum coefficient of variation) converge to those of CPH distributions of the same order.
  • Optimal $\delta$ Identification: Extensive experiments show that for various distributions and orders, an optimal $\delta$ exists that minimizes a chosen distance measure. This optimal $\delta$ is often within a specific range determined by the distribution's properties (CV, support).
  • DPH Advantage for Discontinuities: Numerical results indicate that DPH approximations can better capture distributions with abrupt changes in their CDF or PDF compared to CPH approximations.
  • Performance Measure Impact: When approximating non-Markovian models, the choice of $\delta$ for individual component distributions significantly impacts the accuracy of performance measures (e.g., steady-state probabilities, transient probabilities). The optimal $\delta$ for fitting a single distribution often leads to the best overall system approximation.

Limitations and Future Work

  • Numerical Stability: The paper notes that for very small scale factors ($\delta$), the diagonal elements of the transition probability matrix become close to 1, potentially leading to numerical instability in DPH fitting procedures.
  • Distance Measure Appropriateness: For distributions with finite support, the chosen squared area difference distance measure might not be entirely appropriate as it doesn't explicitly enforce the confinement of mass within the finite support.
  • Generalization of Optimal $\delta$: While experimental results suggest patterns for optimal $\delta$, a deep analytical and numerical sensitivity analysis is required to draw more general conclusions about the model-level "optimal $\delta$ value" and its dependence on performance measures. This is identified as a field for further research.
  • Mixed DPH/CPH Models: The paper primarily considers scenarios where all distributions are either DPH (with the same $\delta$) or CPH. Exploring models with mixed DPH (different $\delta$) and CPH distributions is mentioned as a direction for future work, though it is outside the scope of the current paper.

Summary updated

BibTeX
@inproceedings{bobbio2004scale,
  author = {Andrea Bobbio and András Horváth and Miklós Telek},
  title = {{The scale factor: a new degree of freedom in phase-type approximation}},
  booktitle = {Performance Evaluation},
  year = {2004},
  doi = {10.1016/j.peva.2003.07.003},
}

Loading related content...

Figure