Dealing with Zero Density Using Piecewise Phase-Type Approximation

KORENČIAK, Ľuboš, Jan KRČÁL and Vojtěch ŘEHÁK. Dealing with Zero Density Using Piecewise Phase-Type Approximation. In András Horváth, Katinka Wolter. Computer Performance Engineering. Switzerland: Springer International Publishing, 2014, p. 119-134. ISBN 978-3-319-10884-1. Available from: https://dx.doi.org/10.1007/978-3-319-10885-8_9.

Basic information

• Original name: Dealing with Zero Density Using Piecewise Phase-Type Approximation
• Authors: KORENČIAK, Ľuboš (703 Slovakia, guarantor, belonging to the institution), Jan KRČÁL (203 Czech Republic) and Vojtěch ŘEHÁK (203 Czech Republic, belonging to the institution).
• Edition: Switzerland, Computer Performance Engineering, p. 119-134, 16 pp. 2014.
• Publisher: Springer International Publishing

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Switzerland
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/14:00074094
• Organization unit: Faculty of Informatics
• ISBN: 978-3-319-10884-1
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-319-10885-8_9
• Keywords in English: phase-type; CTMC; discrete-time transition
• Tags: formela-conference
• Tags: International impact, Reviewed

Abstract

Every probability distribution can be approximated up to a given precision by a phase-type distribution, i.e. a distribution encoded by a continuous time Markov chain (CTMC). However, an excessive number of states in the corresponding CTMC is needed for some standard distributions, in particular most distributions with regions of zero density such as uniform or shifted distributions. Addressing this class of distributions, we suggest an alternative representation by CTMC extended with discrete-time transitions. Using discrete-time transitions we split the density function into multiple intervals. Within each interval, we then approximate the density with standard phase-type fitting. We provide an experimental evidence that our method requires only a moderate number of states to approximate such distributions with regions of zero density. Furthermore, the usage of CTMC with discrete-time transitions is supported by a number of techniques for their analysis. Thus, our results promise an efficient approach to the transient analysis of a class of non-Markovian models.

Links

• GPP202/12/P612, research and development project: Name: Formální verifikace stochastických systémů s reálným časem (Acronym: Formální verifikace stochastických systémů s reáln)

Investor: Czech Science Foundation

• MUNI/A/0855/2013, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace III. (Acronym: FI MAV III.)

Investor: Masaryk University, Category A