IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i5p772-d356862.html
   My bibliography  Save this article

Computing the Stationary Distribution of Queueing Systems with Random Resource Requirements via Fast Fourier Transform

Author

Listed:
  • Valeriy A. Naumov

    (Service Innovation Research Institute, 8 A Annankatu, 00120 Helsinki, Finland)

  • Yuliya V. Gaidamaka

    (Applied Informatics and Probability Department, Peoples’ Friendship University of Russia (RUDN University), Miklukho-Maklaya St. 6, Moscow 117198, Russian
    Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilov St. 44-2, Moscow 119333, Russian)

  • Konstantin E. Samouylov

    (Applied Informatics and Probability Department, Peoples’ Friendship University of Russia (RUDN University), Miklukho-Maklaya St. 6, Moscow 117198, Russian
    Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilov St. 44-2, Moscow 119333, Russian)

Abstract

Queueing systems with random resource requirements, in which an arriving customer, in addition to a server, demands a random amount of resources from a shared resource pool, have proved useful to analyze wireless communication networks. The stationary distributions of such queuing systems are expressed in terms of truncated convolution powers of the cumulative distribution function of the resource requirements. Discretization of the cumulative distribution function and the application of the fast Fourier transform are a traditional way of calculating convolutions. We suggest finding truncated convolution powers of the cumulative distribution functions by calculating the convolution powers of the truncated cumulative distribution functions via fast Fourier transform. This radically decreases computational complexity. We introduce the concept of resource load and investigate the accuracy of the proposed method at low and high resource loads. It is shown that the proposed method makes it possible to quickly and accurately calculate truncated convolution powers required for the analysis of queuing systems with random resource requirements.

Suggested Citation

  • Valeriy A. Naumov & Yuliya V. Gaidamaka & Konstantin E. Samouylov, 2020. "Computing the Stationary Distribution of Queueing Systems with Random Resource Requirements via Fast Fourier Transform," Mathematics, MDPI, vol. 8(5), pages 1-9, May.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:5:p:772-:d:356862
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/5/772/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/5/772/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Grübel, Rudolf & Hermesmeier, Renate, 2000. "Computation of Compound Distributions II: Discretization Errors and Richardson Extrapolation," ASTIN Bulletin, Cambridge University Press, vol. 30(2), pages 309-331, November.
    2. Grübel, Rudolf & Hermesmeier, Renate, 1999. "Computation of Compound Distributions I: Aliasing Errors and Exponential Tilting," ASTIN Bulletin, Cambridge University Press, vol. 29(2), pages 197-214, November.
    3. Ruckdeschel, Peter & Kohl, Matthias, 2014. "General Purpose Convolution Algorithm in S4 Classes by Means of FFT," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 59(i04).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Richard L. Warr & Cason J. Wight, 2020. "Error Bounds for Cumulative Distribution Functions of Convolutions via the Discrete Fourier Transform," Methodology and Computing in Applied Probability, Springer, vol. 22(3), pages 881-904, September.
    2. Vernic, Raluca, 2018. "On the evaluation of some multivariate compound distributions with Sarmanov’s counting distribution," Insurance: Mathematics and Economics, Elsevier, vol. 79(C), pages 184-193.
    3. Hu, Xiang & Duan, Baige & Zhang, Lianzeng, 2017. "De Vylder approximation to the optimal retention for a combination of quota-share and excess of loss reinsurance with partial information," Insurance: Mathematics and Economics, Elsevier, vol. 76(C), pages 48-55.
    4. Paul Embrechts & Marco Frei, 2009. "Panjer recursion versus FFT for compound distributions," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 69(3), pages 497-508, July.
    5. Sangüesa, C., 2008. "Error bounds in approximations of random sums using gamma-type operators," Insurance: Mathematics and Economics, Elsevier, vol. 42(2), pages 484-491, April.
    6. Li Qin & Susan M. Pitts, 2012. "Nonparametric Estimation of the Finite-Time Survival Probability with Zero Initial Capital in the Classical Risk Model," Methodology and Computing in Applied Probability, Springer, vol. 14(4), pages 919-936, December.
    7. Sanguesa, C., 2006. "Approximations of ruin probabilities in mixed Poisson models with lattice claim amounts," Insurance: Mathematics and Economics, Elsevier, vol. 39(1), pages 69-80, August.
    8. Dominique Guegan & Bertrand Hassani, 2009. "A modified Panjer algorithm for operational risk capital calculations," PSE-Ecole d'économie de Paris (Postprint) halshs-00443846, HAL.
    9. Dominique Guegan & Bertrand Hassani, 2009. "A modified Panjer algorithm for operational risk capital calculations," Post-Print halshs-00443846, HAL.
    10. Jenq-Tzong Shiau, 2021. "Analytical Water Shortage Probabilities and Distributions of Various Lead Times for a Water Supply Reservoir," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 35(11), pages 3809-3825, September.
    11. Xiaolin Luo & Pavel V. Shevchenko, 2009. "Computing Tails of Compound Distributions Using Direct Numerical Integration," Papers 0904.0830, arXiv.org, revised Feb 2010.
    12. Dominique Guegan & Bertrand Hassani, 2009. "A new algorithm for the loss distribution function with applications to Operational Risk Management," Documents de travail du Centre d'Economie de la Sorbonne 09023, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne, revised Nov 2009.
    13. Dominique Guegan & Bertrand Hassani, 2009. "A new algorithm for the loss distribution function with applications to Operational Risk Management," Post-Print halshs-00384398, HAL.
    14. Thomas Siller, 2013. "Measuring marginal risk contributions in credit portfolios," Quantitative Finance, Taylor & Francis Journals, vol. 13(12), pages 1915-1923, December.
    15. Lorenzo Cappello & Stephen G. Walker, 2018. "A Bayesian Motivated Laplace Inversion for Multivariate Probability Distributions," Methodology and Computing in Applied Probability, Springer, vol. 20(2), pages 777-797, June.
    16. Ruckdeschel, Peter & Kohl, Matthias, 2014. "General Purpose Convolution Algorithm in S4 Classes by Means of FFT," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 59(i04).
    17. Taro Ohdoko & Satoru Komatsu, 2023. "Integrating a Pareto-Distributed Scale into the Mixed Logit Model: A Mathematical Concept," Mathematics, MDPI, vol. 11(23), pages 1-22, November.
    18. Pavel V. Shevchenko, 2010. "Calculation of aggregate loss distributions," Papers 1008.1108, arXiv.org.
    19. Biscarri, William & Zhao, Sihai Dave & Brunner, Robert J., 2018. "A simple and fast method for computing the Poisson binomial distribution function," Computational Statistics & Data Analysis, Elsevier, vol. 122(C), pages 92-100.
    20. Raluca Vernic, 2018. "On the Evaluation of the Distribution of a General Multivariate Collective Model: Recursions versus Fast Fourier Transform," Risks, MDPI, vol. 6(3), pages 1-14, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:5:p:772-:d:356862. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.