Estimating the parameters of mixed shifted negative binomial distributions via an EM algorithm

Document Type : Article

Authors

1 Department of Industrial Engineering, Sharif University of Technology, Tehran, P.O. Box 11155-8639, Iran

2 School of Management, Sabanci University, Istanbul, Turkey

Abstract

Discrete phase-type (DPH) distributions have one property that is not shared by continuous phase-type (CPH) distributions, i.e., representing a deterministic value as a DPH random variable. This property distinguishes the application of DPH in stochastic modeling of real-life problems such as stochastic scheduling where service time random variables should be compared with a deadline that is usually a constant value. In this paper, we consider a restricted class of DPH distributions, called Mixed Shifted Negative Binomial (MSNB) and show its flexibility in producing a wide range of variances as well as its adequacy in fitting fat-tailed distributions. These properties render MSNB applicable to represent data on certain types of service time. Therefore, we adapt an expectation-maximization (EM) algorithm to estimate the parameters of MSNB distributions that accurately fit trace data. To present the applicability of the proposed algorithm, we use it to fit real operating room times as well as a set of benchmark traces generated from continuous distributions as case studies. Finally, we illustrate the efficiency of the proposed algorithm by comparing its results to that of two existing algorithms in the literature. We conclude that our proposed algorithm outperforms other DPH algorithms in fitting trace data and distributions.

Keywords

Main Subjects

References

References:
1. Neuts, M.F. "Computational uses of the method of phases in the theory of queues", Computers & Mathematics with Applications, 1(2), pp. 151-166 (1975).
2. Neuts, M.F., Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, Johns Hopkins University, Baltimore (1981).
3. Fackrell, M. "Modelling healthcare systems with phase-type distributions", Health Care Management Science, 12, pp. 11-26 (2009).
4. Thummler, A., Buchholz, P., and Telek, M. "A novel approach for phase-type fitting with the EM algorithm", IEEE Transactions on Dependable and Secure Computing, 3(3), pp. 245-258 (2006).
5. Hu, L., Jiang, Y., Zhu, J., and Chen, Y. "Hybrid of the scatter search, improved adaptive genetic, and expectation maximization algorithms for phase-type distribution fitting", Applied Mathematics and Computation, 219(10), pp. 5495-5515 (2013).
6. Anbazhagan, N., Stochastic Processes and Models in Operations Research, Hershey, Pennsylvania 701 E. Chocolate Avenue, Hershey, PA 17033, USA: IGI Global (2016).
7. Horvath, A. and Telek, M. "Phfit: A general phasetype fitting tool", Computer Performance Evaluation: Modelling Techniques and Tools, pp. 82-91 (2002).
8. Bobbio, A., Horvath, A., Scarpa, M., and Telek, M. "Acyclic discrete phase type distributions: properties and a parameter estimation algorithm", Performance Evaluation, 54(1), pp. 1-32 (2003).
9. Callut, J. and Dupont, P. "Sequence discrimination using phase-type distributions", Machine Learning: ECML 2006, pp. 78-89 (2006).
10. Asmussen, S., Nerman, O., and Olsson, M. "Fitting phase-type distributions via the EM algorithm", Scandinavian Journal of Statistics, 23(4), pp. 419-441 (1996).
11. Bladt, M., Esparza, L.J.R., Nielsen, B.F., et al. "Fisher information and statistical inference for phase-type distributions", Journal of Applied Probability, 48, pp. 277-293 (2011).
12. Meszaros, A., Papp, J., and Telek, M. "Fitting traffic traces with discrete canonical phase type distributions and Markov arrival processes", International Journal of Applied Mathematics and Computer Science, 24(3), pp. 453-470 (2014).
13. Horvath, I., Papp, J., and Telek, M. "On the canonical representation of order 3 discrete phase type distributions", Electronic Notes in Theoretical Computer Science, 318, pp. 143-158 (2015).
14. Springer, T. and Urban, K. "Comparison of the EM algorithm and alternatives", Numerical Algorithms, 67(2), pp. 335-364 (2014).
15. Verbelen, R., Phase-Type Distributions & Mixtures of Erlangs, University of Leuven (2013).
16. O'Hagan, A., Murphy, T.B., and Gormley, I.C. "Computational aspects of fitting mixture models via the expectation-maximization algorithm", Computational Statistics & Data Analysis, 56(12), pp. 3843-3864 (2012).
17. Xu, J. and Ma, J. "Fitting finite mixture models using iterative Monte Carlo classification", Communications in Statistics-Theory and Methods, 46(13), pp. 6684- 6693 (2017).
18. Bilmes, J.A. "A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models", International Computer Science Institute, 4(510), p. 126 (1998).
19. McLachlan, G. and Krishnan, T., The EM Algorithm and Extensions, 382, John Wiley & Sons (2007).
20. Dougherty, J., Kohavi, R., and Sahami, M. "Supervised and unsupervised discretization of continuous feature", In Proceedings of 12th International Conference of Machine Learning, pp. 194-202 (1995). 
21. MATLAB Release 2014a, MathWorks, Inc. (2015).
22. Bowers, J. and Mould, G. "Managing uncertainty in orthopaedic trauma theatres", European Journal of Operational Research, 154(3), pp. 599-608 (2004).
23. Perez, J. and Riano, G. "Benchmarking of fitting algorithms for continuous phase-type distributions", Working Paper, COPA Universidad de los Andes, pp. 1-20 (2007).
24. Chiarandini, M., Basso, D., and Stutzle, T. "Statistical methods for the comparison of stochastic optimizers", In MIC2005: The Sixth Metaheuristics International Conference, pp. 189-196 (2005).
25. SAS Release, 9.1, SAS Institute Inc. (2003).
26. Bobbio, A. and Telek, M. "A benchmark for PH estimation algorithms: results for Acyclic-PH", Stochastic Models, 10(3), pp. 661-677 (1994).
27. Latouche, G. and Ramaswami, V., Introduction to Matrix Analytic Methods in Stochastic Modeling, 5, Siam (1999).
28. Alfa, A., Applied Discrete-time Queues, Springer- Verlag New York (2016). 
29. Varmazyar, M., Akhavan-Tabatabaei, R., Salmasi, N., and Modarres, M. "Classification and properties of acyclic discrete phase-type distributions based on geometric and shifted geometric distributions", Journal of Industrial Engineering International (Nov 2018).
Scientia Iranica
Volume 26, Issue 1
Transactions on Industrial Engineering (E)
January and February 2019
Pages 571-588

Files

History

  • Receive Date: 24 September 2017
  • Revise Date: 12 November 2017
  • Accept Date: 02 January 2018

Share

How to cite

Statistics