Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Phase-type distribution
open-in-new
<h2 id="definition">Definition</h2> <p>Consider a <a href="/facts/Continuous-time_Markov_process/h7ytJ6p3">continuous-time Markov process</a> with <i>m</i> + 1 states, where <i>m</i> ≥ 1, such that the states 1,...,<i>m</i> are transient states and state 0 is an absorbing state. Further, let the process have an initial probability of starting in any of the <i>m</i> + 1 phases given by the probability vector (<i>α</i>0,α) where <i>α</i>0 is a scalar and α is a 1 × <i>m</i> vector. </p><p>The continuous phase-type distribution is the distribution of time from the above process's starting until absorption in the absorbing state. </p><p>This process can be written in the form of a <a href="/facts/Transition_rate_matrix/6m9Tjrby">transition rate matrix</a>, </p> Q = [ 0 0 S 0 S ] , {\displaystyle {Q}=\left[{\begin{matrix}0&\mathbf {0} \\\mathbf {S} ^{0}&{S}\\\end{matrix}}\right],} <p>where <i>S</i> is an <i>m</i> × <i>m</i> matrix and <i>S</i>0 = –S1. Here 1 represents an <i>m</i> × 1 column vector with every element being 1. </p> <h2 id="characterization">Characterization</h2> <p>The distribution of time <i>X</i> until the process reaches the absorbing state is said to be phase-type distributed and is denoted PH(α,<i>S</i>). </p><p>The distribution function of <i>X</i> is given by, </p> F ( x ) = 1 − α exp ( S x ) 1 , {\displaystyle F(x)=1-{\boldsymbol {\alpha }}\exp({S}x)\mathbf {1} ,} <p>and the density function, </p> f ( x ) = α exp ( S x ) S 0 , {\displaystyle f(x)={\boldsymbol {\alpha }}\exp({S}x)\mathbf {S^{0}} ,} <p>for all <i>x</i> > 0, where exp( · ) is the <a href="/facts/Matrix_exponential/WID5cG2g">matrix exponential</a>. It is usually assumed the probability of process starting in the absorbing state is zero (i.e. α0= 0). The moments of the distribution function are given by </p> E [ X n ] = ( − 1 ) n n ! α S − n 1 . {\displaystyle E[X^{n}]=(-1)^{n}n!{\boldsymbol {\alpha }}{S}^{-n}\mathbf {1} .} <p>The <a href="/facts/Laplace_transform/0Ge4MIc9">Laplace transform</a> of the phase type distribution is given by </p> M ( s ) = α 0 + α ( s I − S ) − 1 S 0 , {\displaystyle M(s)=\alpha _{0}+{\boldsymbol {\alpha }}(sI-S)^{-1}\mathbf {S^{0}} ,} <p>where I is the identity matrix. </p> <h2 id="special-cases">Special cases</h2> <p>The following probability distributions are all considered special cases of a continuous phase-type distribution: </p> <ul><li><a href="/facts/Degenerate_distribution/Tj5b5h2z">Degenerate distribution</a>, point mass at zero or the empty phase-type distribution – 0 phases.</li> <li><a href="/facts/Exponential_distribution/yY3EdV0u">Exponential distribution</a> – 1 phase.</li> <li><a href="/facts/Erlang_distribution/dqFqlxJg">Erlang distribution</a> – 2 or more identical phases in sequence.</li> <li>Deterministic distribution (or constant) – The limiting case of an Erlang distribution, as the number of phases become infinite, while the time in each state becomes zero.</li> <li>Coxian distribution – 2 or more (not necessarily identical) phases in sequence, with a probability of transitioning to the terminating/absorbing state after each phase.</li> <li><a href="/facts/Hyperexponential_distribution/vxa9JHSY">Hyperexponential distribution</a> (also called a mixture of exponential) – 2 or more non-identical phases, that each have a probability of occurring in a mutually exclusive, or parallel, manner. (Note: The exponential distribution is the degenerate situation when all the parallel phases are identical.)</li> <li><a href="/facts/Hypoexponential_distribution/hFDgbohC">Hypoexponential distribution</a> – 2 or more phases in sequence, can be non-identical or a mixture of identical and non-identical phases, generalises the Erlang.</li></ul> <p>As the phase-type distribution is dense in the field of all positive-valued distributions, we can represent any positive valued distribution. However, the phase-type is a light-tailed or platykurtic distribution. So the representation of heavy-tailed or leptokurtic distribution by phase type is an approximation, even if the precision of the approximation can be as good as we want. </p> <h2 id="examples">Examples</h2> <p>In all the following examples it is assumed that there is no probability mass at zero, that is α0 = 0. </p> <h3>Exponential distribution</h3> <p>The simplest non-trivial example of a phase-type distribution is the exponential distribution of parameter λ. The parameter of the phase-type distribution are : <i>S</i> = -λ and α = 1. </p> <h3>Hyperexponential or mixture of exponential distribution</h3> <p>The mixture of exponential or <a href="/facts/Hyperexponential_distribution/vxa9JHSY">hyperexponential distribution</a> with λ1,λ2,...,λn>0 can be represented as a phase type distribution with </p> α = ( α 1 , α 2 , α 3 , α 4 , . . . , α n ) {\displaystyle {\boldsymbol {\alpha }}=(\alpha _{1},\alpha _{2},\alpha _{3},\alpha _{4},...,\alpha _{n})} <p>with ∑ i = 1 n α i = 1 {\displaystyle \sum _{i=1}^{n}\alpha _{i}=1} and </p> S = [ − λ 1 0 0 0 0 0 − λ 2 0 0 0 0 0 − λ 3 0 0 0 0 0 − λ 4 0 0 0 0 0 − λ 5 ] . {\displaystyle {S}=\left[{\begin{matrix}-\lambda _{1}&0&0&0&0\\0&-\lambda _{2}&0&0&0\\0&0&-\lambda _{3}&0&0\\0&0&0&-\lambda _{4}&0\\0&0&0&0&-\lambda _{5}\\\end{matrix}}\right].} <p>This mixture of densities of exponential distributed random variables can be characterized through </p> f ( x ) = ∑ i = 1 n α i λ i e − λ i x = ∑ i = 1 n α i f X i ( x ) , {\displaystyle f(x)=\sum _{i=1}^{n}\alpha _{i}\lambda _{i}e^{-\lambda _{i}x}=\sum _{i=1}^{n}\alpha _{i}f_{X_{i}}(x),} <p>or its cumulative distribution function </p> F ( x ) = 1 − ∑ i = 1 n α i e − λ i x = ∑ i = 1 n α i F X i ( x ) . {\displaystyle F(x)=1-\sum _{i=1}^{n}\alpha _{i}e^{-\lambda _{i}x}=\sum _{i=1}^{n}\alpha _{i}F_{X_{i}}(x).} <p>with X i ∼ E x p ( λ i ) {\displaystyle X_{i}\sim Exp(\lambda _{i})} </p> <h3>Erlang distribution</h3> <p>The Erlang distribution has two parameters, the shape an integer <i>k</i> > 0 and the rate λ > 0. This is sometimes denoted <i>E</i>(<i>k</i>,λ). The Erlang distribution can be written in the form of a phase-type distribution by making <i>S</i> a <i>k</i>×<i>k</i> matrix with diagonal elements -λ and super-diagonal elements λ, with the probability of starting in state 1 equal to 1. For example, <i>E</i>(5,λ), </p> α = ( 1 , 0 , 0 , 0 , 0 ) , {\displaystyle {\boldsymbol {\alpha }}=(1,0,0,0,0),} <p>and </p> S = [ − λ λ 0 0 0 0 − λ λ 0 0 0 0 − λ λ 0 0 0 0 − λ λ 0 0 0 0 − λ ] . {\displaystyle {S}=\left[{\begin{matrix}-\lambda &\lambda &0&0&0\\0&-\lambda &\lambda &0&0\\0&0&-\lambda &\lambda &0\\0&0&0&-\lambda &\lambda \\0&0&0&0&-\lambda \\\end{matrix}}\right].} <p>For a given number of phases, the Erlang distribution is the phase type distribution with smallest coefficient of variation.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>The <a href="/facts/Hypoexponential_distribution/hFDgbohC">hypoexponential distribution</a> is a generalisation of the Erlang distribution by having different rates for each transition (the non-homogeneous case). </p> <h3>Mixture of Erlang distribution</h3> <p>The mixture of two Erlang distributions with parameter <i>E</i>(3,β1), <i>E</i>(3,β2) and (α1,α2) (such that α1 + α2 = 1 and for each <i>i</i>, α<i>i</i> ≥ 0) can be represented as a phase type distribution with </p> α = ( α 1 , 0 , 0 , α 2 , 0 , 0 ) , {\displaystyle {\boldsymbol {\alpha }}=(\alpha _{1},0,0,\alpha _{2},0,0),} <p>and </p> S = [ − β 1 β 1 0 0 0 0 0 − β 1 β 1 0 0 0 0 0 − β 1 0 0 0 0 0 0 − β 2 β 2 0 0 0 0 0 − β 2 β 2 0 0 0 0 0 − β 2 ] . {\displaystyle {S}=\left[{\begin{matrix}-\beta _{1}&\beta _{1}&0&0&0&0\\0&-\beta _{1}&\beta _{1}&0&0&0\\0&0&-\beta _{1}&0&0&0\\0&0&0&-\beta _{2}&\beta _{2}&0\\0&0&0&0&-\beta _{2}&\beta _{2}\\0&0&0&0&0&-\beta _{2}\\\end{matrix}}\right].} <h3>Coxian distribution</h3> <p>The Coxian distribution is a generalisation of the <a href="/facts/Erlang_distribution/dqFqlxJg">Erlang distribution</a>. Instead of only being able to enter the absorbing state from state <i>k</i> it can be reached from any phase. The phase-type representation is given by, </p> S = [ − λ 1 p 1 λ 1 0 … 0 0 0 − λ 2 p 2 λ 2 ⋱ 0 0 ⋮ ⋱ ⋱ ⋱ ⋱ ⋮ 0 0 ⋱ − λ k − 2 p k − 2 λ k − 2 0 0 0 … 0 − λ k − 1 p k − 1 λ k − 1 0 0 … 0 0 − λ k ] {\displaystyle S=\left[{\begin{matrix}-\lambda _{1}&p_{1}\lambda _{1}&0&\dots &0&0\\0&-\lambda _{2}&p_{2}\lambda _{2}&\ddots &0&0\\\vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\0&0&\ddots &-\lambda _{k-2}&p_{k-2}\lambda _{k-2}&0\\0&0&\dots &0&-\lambda _{k-1}&p_{k-1}\lambda _{k-1}\\0&0&\dots &0&0&-\lambda _{k}\end{matrix}}\right]} <p>and </p> α = ( 1 , 0 , … , 0 ) , {\displaystyle {\boldsymbol {\alpha }}=(1,0,\dots ,0),} <p>where 0 < <i>p</i>1,...,<i>p</i><i>k</i>-1 ≤ 1. In the case where all <i>p</i><i>i</i> = 1 we have the Erlang distribution. The Coxian distribution is extremely important as any acyclic phase-type distribution has an equivalent Coxian representation. </p><p>The generalised Coxian distribution relaxes the condition that requires starting in the first phase. </p> <h2 id="properties">Properties</h2> <h3>Minima of Independent PH Random Variables</h3> <p>Similarly to the <a href="/facts/Exponential_distribution/yY3EdV0u"> exponential distribution</a>, the class of PH distributions is closed under minima of independent random variables. A description of this is <a href="https://www.smp.uq.edu.au/people/YoniNazarathy/teaching_projects/studentWork/Min_Two_Phase_Types.pdf">here</a>. </p> <h2 id="generating-samples-from-phase-type-distributed-random-variables">Generating samples from phase-type distributed random variables</h2> <p><i><a href="http://webspn.hit.bme.hu/~telek/tools/butools/butools.html">BuTools</a></i> includes methods for generating samples from phase-type distributed random variables.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="approximating-other-distributions">Approximating other distributions</h2> <p>Any distribution can be arbitrarily well approximated by a phase type distribution.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> In practice, however, approximations can be poor when the size of the approximating process is fixed. Approximating a deterministic distribution of time 1 with 10 phases, each of average length 0.1 will have variance 0.1 (because the Erlang distribution has smallest variance<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>). </p> <ul><li><i><a href="http://webspn.hit.bme.hu/~telek/tools/butools/butools.html">BuTools</a></i> a <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> and <a href="/facts/Mathematica/dRwoGFG2">Mathematica</a> script for fitting phase-type distributions to 3 specified moments</li> <li><i><a href="https://www.cs.cmu.edu/~osogami/code/momentmatching/index.html">momentmatching</a></i> a <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> script to fit a minimal phase-type distribution to 3 specified moments<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li> <li><a href="https://github.com/kpctoolboxteam/kpc-toolbox"><i>KPC-toolbox</i></a> a library of <a href="/facts/MATLAB/qPjLISCk">MATLAB</a> scripts to fit empirical datasets to Markovian arrival processes and phase-type distributions.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li></ul> <h2 id="fitting-a-phase-type-distribution-to-data">Fitting a phase type distribution to data</h2> <p>Methods to fit a phase type distribution to data can be classified as maximum likelihood methods or moment matching methods.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> Fitting a phase type distribution to <a href="/facts/Heavy-tailed_distribution/BHLSHPku">heavy-tailed distributions</a> has been shown to be practical in some situations.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <ul><li><i><a href="http://webspn.hit.bme.hu/~telek/tools.htm">PhFit</a></i> a C script for fitting discrete and continuous phase type distributions to data<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li> <li><i><a href="http://home.imf.au.dk/asmus/pspapers.html">EMpht</a></i> is a C script for fitting phase-type distributions to data or parametric distributions using an <a href="/facts/Expectation%25E2%2580%2593maximization_algorithm/32P2bdBc">expectation–maximization algorithm</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></li> <li><i><a href="http://www.mi.fu-berlin.de/inf/groups/ag-tech/projects/HyperStar/index.html">HyperStar</a></i> was developed around the core idea of making phase-type fitting simple and user-friendly, in order to advance the use of phase-type distributions in a wide range of areas. It provides a graphical user interface and yields good fitting results with only little user interaction.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li><i><a href="http://copa.uniandes.edu.co/?p=141">jPhase</a></i> is a Java library which can also compute metrics for queues using the fitted phase type distribution<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Discrete_phase-type_distribution/s6Se3dPt">Discrete phase-type distribution</a></li> <li><a href="/facts/Continuous-time_Markov_process/h7ytJ6p3">Continuous-time Markov process</a></li> <li><a href="/facts/Exponential_distribution/yY3EdV0u">Exponential distribution</a></li> <li><a href="/facts/Hyper-exponential_distribution/vxa9JHSY">Hyper-exponential distribution</a></li> <li><a href="/facts/Queueing_theory/8NDl56EM">Queueing theory</a></li></ul> <ul><li><a href="/facts/Marcel_F._Neuts/gx3B3l7d">M. F. Neuts</a> (1975), Probability distributions of phase type, In Liber Amicorum Prof. Emeritus H. Florin, Pages 173-206, University of Louvain.</li> <li>M. F. Neuts. <a href="https://books.google.com/books?id=WPol7RVptz0C&q=%22Phase-type%22">Matrix-Geometric Solutions in Stochastic Models: an Algorithmic Approach</a>, Chapter 2: Probability Distributions of Phase Type; Dover Publications Inc., 1981.</li> <li>G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modelling, 1st edition. Chapter 2: PH Distributions; ASA SIAM, 1999.</li> <li>C. A. O'Cinneide (1990). <i>Characterization of phase-type distributions</i>. Communications in Statistics: Stochastic Models, 6(1), 1-57.</li> <li>C. A. O'Cinneide (1999). <i>Phase-type distribution: open problems and a few properties</i>, Communication in Statistic: Stochastic Models, 15(4), 731-757.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Harchol-Balter, M. (2012). "Real-World Workloads: High Variability and Heavy Tails". Performance Modeling and Design of Computer Systems. pp. 347–348. doi:10.1017/CBO9781139226424.026. ISBN 9781139226424. <a href="9781139226424" target="_blank">9781139226424</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Aldous, David; Shepp, Larry (1987). "The least variable phase type distribution is erlang" (PDF). Stochastic Models. 3 (3): 467. doi:10.1080/15326348708807067. <a href="/wiki/David_Aldous" target="_blank">/wiki/David_Aldous</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Horváth, G. B.; Reinecke, P.; Telek, M. S.; Wolter, K. (2012). "Efficient Generation of PH-Distributed Random Variates" (PDF). Analytical and Stochastic Modeling Techniques and Applications. Lecture Notes in Computer Science. Vol. 7314. p. 271. doi:10.1007/978-3-642-30782-9_19. ISBN 978-3-642-30781-2. <a href="978-3-642-30781-2" target="_blank">978-3-642-30781-2</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (1998). "Steady-State Solutions of Markov Chains". Queueing Networks and Markov Chains. pp. 103–151. doi:10.1002/0471200581.ch3. ISBN 0471193666. <a href="0471193666" target="_blank">0471193666</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Cox, D. R. (2008). "A use of complex probabilities in the theory of stochastic processes". Mathematical Proceedings of the Cambridge Philosophical Society. 51 (2): 313–319. doi:10.1017/S0305004100030231. S2CID 122768319. <a href="/wiki/David_Cox_(statistician)" target="_blank">/wiki/David_Cox_(statistician)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Aldous, David; Shepp, Larry (1987). "The least variable phase type distribution is erlang" (PDF). Stochastic Models. 3 (3): 467. doi:10.1080/15326348708807067. <a href="/wiki/David_Aldous" target="_blank">/wiki/David_Aldous</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Osogami, T.; Harchol-Balter, M. (2006). "Closed form solutions for mapping general distributions to quasi-minimal PH distributions". Performance Evaluation. 63 (6): 524. doi:10.1016/j.peva.2005.06.002. <a href="/wiki/Mor_Harchol-Balter" target="_blank">/wiki/Mor_Harchol-Balter</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Casale, G.; Zhang, E. Z.; Smirni, E. (2008). "KPC-Toolbox: Simple Yet Effective Trace Fitting Using Markovian Arrival Processes". 2008 Fifth International Conference on Quantitative Evaluation of Systems (PDF). p. 83. doi:10.1109/QEST.2008.33. ISBN 978-0-7695-3360-5. S2CID 252444. <a href="978-0-7695-3360-5" target="_blank">978-0-7695-3360-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Lang, Andreas; Arthur, Jeffrey L. (1996). "Parameter approximation for Phase-Type distributions". In Chakravarthy, S.; Alfa, Attahiru S. (eds.). Matrix Analytic methods in Stochastic Models. CRC Press. ISBN 0824797663. <a href="0824797663" target="_blank">0824797663</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Ramaswami, V.; Poole, D.; Ahn, S.; Byers, S.; Kaplan, A. (2005). "Ensuring Access to Emergency Services in the Presence of Long Internet Dial-Up Calls". Interfaces. 35 (5): 411. doi:10.1287/inte.1050.0155. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Horváth, András S.; Telek, Miklós S. (2002). "PhFit: A General Phase-Type Fitting Tool". Computer Performance Evaluation: Modelling Techniques and Tools. Lecture Notes in Computer Science. Vol. 2324. p. 82. doi:10.1007/3-540-46029-2_5. ISBN 978-3-540-43539-6. <a href="978-3-540-43539-6" target="_blank">978-3-540-43539-6</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Asmussen, Søren; Nerman, Olle; Olsson, Marita (1996). "Fitting Phase-Type Distributions via the EM Algorithm". Scandinavian Journal of Statistics. 23 (4): 419–441. JSTOR 4616418. <a href="/wiki/JSTOR_(identifier)" target="_blank">/wiki/JSTOR_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Reinecke, P.; Krauß, T.; Wolter, K. (2012). "Cluster-based fitting of phase-type distributions to empirical data". Computers & Mathematics with Applications. 64 (12): 3840. doi:10.1016/j.camwa.2012.03.016. <a href="https://doi.org/10.1016%2Fj.camwa.2012.03.016" target="_blank">https://doi.org/10.1016%2Fj.camwa.2012.03.016</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Pérez, J. F.; Riaño, G. N. (2006). "jPhase: an object-oriented tool for modeling phase-type distributions". Proceeding from the 2006 workshop on Tools for solving structured Markov chains (SMCtools '06) (PDF). doi:10.1145/1190366.1190370. ISBN 1595935061. S2CID 7863948. <a href="1595935061" target="_blank">1595935061</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> </ol>