Inverting generating functions with increased numerical precision — A computational experience

Abstract

In this paper, we consider the numerical inversion of a variety of generating functions (GFs) that arise in the area of engineering and non-engineering fields. Three classes of GFs are taken into account in a comprehensive manner: classes of probability generating functions (PGFs) that are given in rational and non-rational forms, and a class of GFs that are not PGFs. Among others, those PGFs that are not explicitly given but contain a number of unknowns are largely considered as they are often encountered in many interesting applied problems. For the numerical inversion of GFs, we use the methods of the discrete (fast) Fourier transform and the Taylor series expansion. Through these methods, we show that it is remarkably easy to obtain the desired sequence to any given accuracy, so long as enough numerical precision is used in computations. Since high precision is readily available in current software packages and programming languages, one can now lift, with little effort, the so-called Laplacian curtain that veils the sequence of interest. To demonstrate, we take a series of representative examples: the PGF of the number of customers in the discrete-time GeoX/Geo/c queue, the same in the continuous-time MX/D/c queue, and the GFs arising in the discrete-time renewal process.

Keywords

Queuing / applied probability / numerical inversion / generating function

References

[1] Abate J., Whitt W.. The Fourier-series method for inverting transforms of probability distributions. Queueing Systems, 1992, 10: 5-88.

[2] Abate J., Whitt W.. Numerical inversion of probability generating functions. Operations Research Letters, 1992, 12: 245-251.

[3] Abate J., Whitt W.. A heavy-traffic expansion for asymptotic decay rates of tail probabilities in multichannel queues. Operations Research Letters, 1994, 15: 223-230.

[4] Abate J., Choudhury G.L., Whitt W.. Grassmann W.K.. An introduction to numerical transform inversion and its application to probability models. Computational Probability, 2000, Norwell, Massachusetts: Kluwer Academic Publishers 257-323.

[5] Chaudhry M.L., Templeton J.G.C.. A First Course in Bulk Queues, 1983, New York: John Wiley & Sons.

[6] Chaudhry M.L.. QROOT Software Package, 1991, Kingston, Ontario, Canada: A&A Publication, 395 Carrie Crescent

[7] Chaudhry M.L., Templeton J.G.C., Medhi J.. Computational results of multiserver bulk-arrival queues with constant service time MX/D/c. Operations Research, 1992, 40: 229-238.

[8] Chaudhry M.L.. Alternative numerical solutions of stationary queueing-time distributions in discrete-time queues: GI/G/1. Journal of the Operational Research Society, 1993, 44: 1035-1051.

[9] Chaudhry M.L., Kim N.K.. A complete and simple solution for a discrete-time multi-server queue with bulk arrivals and deterministic service times. Operations Research Letters, 2003, 31: 101-107.

[10] Choudhry G.L., Leung K.K., Whitt W.. Calculating normalization constants of closed queueing networks by numerically inverting their generating functions. Journal of the Association for Computing Machinery, 1995, 42: 935-970.

[11] Choudhury G.L., Lucantoni D.M.. Numerical computation of the moments of a probability distribution from its transform. Operations Research, 1996, 44: 368-381.

[12] Choudhury G.L., Whitt W.. Probabilistic scaling for the numerical inversion of nonprobability transforms. INFORMS Journal on Computing, 1997, 9: 175-184.

[13] Daigle J.N.. Queue length distributions from probability generating functions via discrete Fourier transforms. Operations Research Letters, 1989, 8: 229-236.

[14] Feller W.. An Introduction to Probability Theory and Its Applications, Volume 1, Third Edition, 1968, New York: Jon Wiley & Sons

[15] Gouweleeuw F.N., Tijms H.C.. Computing loss probabilities in discrete-time queues. Operations Research, 1998, 46: 149-154.

[16] Kendall D.G.. Some recent work and further problems in the theory of queues. Theory of Probability and Its Applications, 1964, 9: 1-13.

[17] Kida, Y. (2000). UBASIC: Version 8.8f. Department of Mathematics, College of Science, Rikkyo University, Japan

[18] Kim N.K., Chae K.C., Chaudhry M.L.. An invariance relation and a unified method to derive stationary queue lengths. Operations Research, 2004, 52: 756-764.

[19] Kleinrock L.. Queueing Systems, vol. 1: Theory, 1975, New York: John Wiley & Sons

[20] Powell W.B., Humblet P.. The bulk service queue with a general control strategy: theoretical analysis and a new computational procedure. Operations Research, 1986, 34: 267-275.

[21] Rubin I., Zhang Z.. Message delay and queue-size analysis for circuit-switched TDMA systems. IEEE Transactions on Communications, 1991, 39: 905-914.

[22] Tijms H.C.. Stochastic Models: An Algorithmic Approach, 1994, Chichester: John Wiley & Sons.

[23] Zhao Y.Q., Campbell L.L.. Equilibrium probability calculations for a discrete-time bulk queue model. Queueing Systems, 1996, 22: 189-198.