Computing discrete Poisson probabilities for uniformization algorithm

• Autorzy: Burak M. R.

Identyfikatory

DOI

10.21936/si2017_v38.n1B.795

Warianty tytułu

PL

Obliczanie prawdopodobieństw dyskretnego rozkładu Poissona dla algotrytmu uniformizacji

• Języki publikacji: EN

Abstrakty

EN

This paper deals with the computation of discrete Poisson probabilities and their precise tail bounds for the use in solving of transient Markov models with the uniformization with steady-state detection algorithm. The algorithm calculates the weights corresponding to the probabilities, maintaining the beneficial properties for the use in uniformization algorithm of the popular Fox-Glynn method, while improving the estimation of truncation points with significant effect on the overall performance.

PL

W artykule przedstawiany jest algorytm wyliczający wartości prawdopodobieństw dyskretnego rozkładu Poissona dla algorytmu uniformizacji, wykorzystywanego dla modelowania stanów nieustalonych łańcuchów Markowa z czasem ciągłym. Algorytm jest rozwinięciem popularnej metody Foxa-Glynna i oblicza wagi odpowiadające ww. rozkładowi w sposób umożliwiający dokładniejsze ustalenie wartości granicznych dla zadanego błędu obliczeń, co przekłada się bezpośrednio na efektywność obliczeniową.

Słowa kluczowe

EN

Poisson computing discrete distributions; uniformization; numerical methods; algorithm

PL

rozkład dyskretny Poissona; uniformizacja; metody numeryczne; algorytm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2017
• Tom: Vol. 38, nr 1B
• Strony: 77--88
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Burak M. R.

• West Pomeranian University of Technology, Applied Informatics, ul. Sikorskiego 37, 90-313 Szczecin, Poland

Bibliografia

• 1. Arns M., Buchholz P., Panchenko A. (2010): On the numerical analysis of inhomogeneous continuous-time Markov chains. INFORMS Journal on Computing, Vol. 22, No. 3, p. 416÷432. DOI:10.1287/ijoc.1090.0357.
• 2. Burak M. (2014): Multi-step uniformization with steady-state detection in nonstationary M/M/s queuing systems. arXiv preprint arXiv:14100804.
• 3. Fox B.L., Glynn P.W. (1988): Computing Poisson probabilities. Commun ACM, Vol. 31, no. 4, p. 440÷445. DOI:10.1145/42404.42409.
• 4. Grassmann W.K. (1978): Transient solutions in Markovian Queueing Systems. Computers & Operations Research 5(2):161,doi:10.1016/0305-0548(78)90010-2.
• 5. Jansen D.N. (2011): Understanding Fox and Glynn’s “Computing Poisson Probabilities”. Technical Paper.
• 6. Katoen J.P., Zapreev I.S., Hahn E.M., Hermanns H., Jansen D.N. (2009): The ins and outs of the probabilistic model checker MRMC. In: 2009 Sixth International Conference on the Quantitative Evaluation of Systems, Institute of Electrical & Electronics Engineers (IEEE),doi:10.1109/qest.2009.11.
• 7. Krzensk U. (2004): Simple and efficient algorithms for computing exact cumulative discrete probabilities and its inverses. Computational Statistics, Vol. 19, no. 4, p. 535÷550. DOI:10.1007/bf02753911.
• 8. Reibman A., Trivedi K. (1988): Numerical transient analysis of Markov models. Computers & Operations Research, Vol. 15, no. 1, p. 19÷36. DOI:10.1016/0305- 0548(88)90026-3.
• 9. Robertazzi T.G., Schwartz S.C. (1988): Best "ordering" for floating-point addition. ACM Trans Math Softw., Vol. 14, no. 41, p. 101÷110. DOI:10.1145/42288.42343.
• 10. Van Moorsel A.P., Sanders W.H. (1997): Transient solution of Markov models by combining adaptive and standard uniformization. IEEE Transactions on Reliability, Vol. 46, no. 3, p. 430÷440. DOI:10.1109/24.664016.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)