×

zbMATH — the first resource for mathematics

The Fourier-series method for inverting transforms of probability distributions. (English) Zbl 0749.60013
The paper reviews the Fourier-series method for calculating cumulative distribution functions and probability mass functions by numerically inverting characteristic functions, Laplace transforms and generating functions. The Fourier-series method can be interpreted as numerically integrating a standard inversion integral by means of the trapezoidal rule. The same formula is obtained by using the Fourier series of an associated periodic function constructed by aliasing; this explains the name of the method. The mathematical centrepiece of the method is the Poisson summation formula, which identifies the discretization error associated with the trapezoidal rule and thus helps bound it. Examples are given to illustrate the procedure.

MSC:
60E10 Characteristic functions; other transforms
65C99 Probabilistic methods, stochastic differential equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Abate and H. Dubner, A new method for generating power series expansions of functions, SIAM J. Numer. Anal. 5 (1968) 102-112. · Zbl 0155.22101 · doi:10.1137/0705008
[2] J. Abate and W. Whitt, Transient behavior of regulated Brownian motion I: starting at the origin, Adv. Appl. Prob. 19 (1987) 560-598. · Zbl 0628.60083 · doi:10.2307/1427408
[3] J. Abate and W. Whitt, Transient behavior of theM/M/1 queue via Laplace transforms, Adv. Appl. Prob. 20 (1988) 145-178. · Zbl 0638.60097 · doi:10.2307/1427274
[4] J. Abate and W. Whitt, Approximations for theM/M/1 busy-period distribution, in:Queueing Theory and its Applications, Liber Amicorum for J.W. Cohen, eds. O.J. Boxma and R. Syski (North-Holland, Amsterdam, 1988) pp. 149-191.
[5] J. Abate and W. Whitt, Simple spectral representations for the M/M/1 queue, Queueing Systems 3 (1988) 321-346. · Zbl 0671.60083 · doi:10.1007/BF01157854
[6] J. Abate and W. Whitt, Numerical inversion of Laplace transforms of probability distributions, AT&T Bell Laboratories, Murray Hill, NJ (1991). · Zbl 0821.65085
[7] J. Abate and W. Whitt, Numerical inversion of probability generating functions, AT&T Bell Laboratories, Murray Hill, NJ (1991). · Zbl 0758.60014
[8] M. Abramowitz and I.A. Stegun,Handbook of Mathematical Functions (National Bureau of Standards, Washington, DC, 1972). · Zbl 0543.33001
[9] N.C. Beaulieu, An infinite series for the computation of the complementary probability distribution function of a sum of independent random variables and its application to the sum of Rayleigh random variables, IEEE Trans. Commun. COM-38 (1990) 1463-1474. · doi:10.1109/26.61387
[10] R. Bellman, R.E. Kalaba and J. Lockett,Numerical Inversion of the Laplace Transform. Application to Biology, Economics, Engineering and Physics (American Elsevier, New York, 1966). · Zbl 0147.14003
[11] B.C. Berndt,Ramanujan’s Notebooks, Part II (Springer, New York, 1989). · Zbl 0716.11001
[12] D. Bertsimas and D. Nakazato, Transient and busy period analysis for theGI/G/1 queue; the method of stages, Queueing Systems 10 (1992) 153-184. · Zbl 0743.60091 · doi:10.1007/BF01159205
[13] H. Bohman, A method to calculate the distribution function when the characteristic function is known, Ark. Mat. 4 (1960) 99-157. · Zbl 0104.12002 · doi:10.1007/BF02592003
[14] H. Bohman, A method to calculate the distribution function when the characteristic function is known, BIT 10 (1970) 237-242. · Zbl 0206.16803 · doi:10.1007/BF01934194
[15] H. Bohman, From characteristic function to distribution function via Fourier analysis, BIT 12 (1972) 279-283. · Zbl 0243.65082 · doi:10.1007/BF01932299
[16] E.O. Brigham and R.E. Conley, Evaluation of cumulative probability distribution functions: improved numerical methods, IEEE Proc. 58 (1970) 1367-1368. · doi:10.1109/PROC.1970.7933
[17] A.S. Carasso, Infinitely divisible pulses, continuous deconvolution, and the characterization of linear time invariant systems, SIAM J. Appl. Math. 47 (1987) 892-927. · Zbl 0635.93036 · doi:10.1137/0147060
[18] H.S. Carslaw,Introduction to the Theory of Fourier’s Series and Integrals, 3rd ed. (Dover, New York, 1930). · JFM 56.0243.01
[19] J.K. Cavers, On the fast Fourier transform inversion of probability generating functions, J. Inst. Math. Appl. 22 (1978) 275-282. · Zbl 0394.65053 · doi:10.1093/imamat/22.3.275
[20] D.C. Champeney,A Handbook of Fourier Theorems (Cambridge University Press, New York, 1987). · Zbl 0632.42001
[21] K.L. Chung,A Course in Probability Theory, 2nd ed. (Academic Press, New York, 1974). · Zbl 0345.60003
[22] J.W. Cooley, P.A.W. Lewis and P.D. Welch, Application of the fast Fourier transform to the computation of Fourier integrals, Fourier series, and convolution integrals, IEEE Trans. AU-15 (1967) 79-84.
[23] J.W. Cooley, P.A.W. Lewis and P.D. Welch, Historical notes on the fast Fourier transform, Proc. IEEE 55 (1967) 1675-1677. · doi:10.1109/PROC.1967.5959
[24] J.W. Cooley, P.A.W. Lewis and P.D. Welch, The fast Fourier transform algorithm: programming considerations of sine, cosine and Laplace transforms, J. Sound Vib. 12 (1970) 315-337. · Zbl 0195.46301 · doi:10.1016/0022-460X(70)90075-1
[25] J.W. Cooley and J.W. Tukey, An algorithm for the machine computation of complex Fourier series, Math. Comp. 19 (1965) 297-301. · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[26] D.R. Cox,Renewal Theory (Methuen, London, 1962).
[27] K.S. Crump, Numerical inversion of Laplace transforms using a Fourier-series approximation, J. ACM 23 (1976) 89-96. · Zbl 0315.65074 · doi:10.1145/321921.321931
[28] J.N. Daigle, Queue length distributions from probability generating functions via discrete Fourier transforms, Oper. Res. Lett. 8 (1989) 229-236. · Zbl 0671.60098 · doi:10.1016/0167-6377(89)90066-7
[29] B. Davies and B.L. Martin, Numerical inversion of Laplace transforms: a critical evaluation and review of methods, J. Comp. Phys. 33 (1970) 1-32. · Zbl 0416.65077 · doi:10.1016/0021-9991(79)90025-1
[30] R.B. Davies, Numerical inversion of a characteristic function, Biometrika 60 (1973) 415-417. · Zbl 0263.65115 · doi:10.1093/biomet/60.2.415
[31] R.B. Davies, The distribution of a linear combination ofX 2 random variables, Appl. Stat. 29 (1980) 323-333. · Zbl 0473.62025 · doi:10.2307/2346911
[32] P.J. Davis and P. Rabinowitz,Methods of Numerical Integration, 2nd ed. (Academic Press, New York, 1984). · Zbl 0537.65020
[33] M.A.B. Deakin, Euler’s version of the Laplace transform, Amer. Math. Monthly 87 (1980) 264-269. · Zbl 0433.44001 · doi:10.2307/2321558
[34] G. de Balbine and J. Franklin, The calculation of Fourier integrals, Math. Comp. 20 (1966) 570-589. · Zbl 0196.49102 · doi:10.1090/S0025-5718-1966-0203976-9
[35] F.R. de Hoog, J.H. Knight and A.N. Stokes, An improved method for numerical inversion of Laplace transforms, SIAM J. Sci. Stat. Comput. 3 (1982) 357-366. · Zbl 0482.65066 · doi:10.1137/0903022
[36] G. Doetsch,Introduction to the Theory and Application of the Laplace Transformation (Springer, New York, 1974). · Zbl 0278.44001
[37] B.T. Doshi, Analysis of clocked schedules ? high priority tasks, AT&T Tech. J. 64 (1985) 633-659.
[38] B.T. Doshi and J. Kaufman, Sojourn times in anM/G/1 queue with Bernoulli feedback, in:Queueing Theory and Its Applications, Liber Amicorum for J.W. Cohen, eds. O.J. Boxma and R. Syski (North-Holland, Amsterdam, 1988).
[39] H. Dubner, Partitions approximated by finite cosine series, Math. Computation, to appear. · Zbl 0767.11046
[40] H. Dubner and J. Abate, Numerical inversion of Laplace transforms by relating them to the finite Fourier cosine transform, J. ACM 15 (1968) 115-123. · Zbl 0165.51403 · doi:10.1145/321439.321446
[41] F. Durbin, Numerical inversion of Laplace transforms: An efficient improvement to Dubner and Abate’s method, Comput. J. 17 (1974) 371-376. · Zbl 0288.65072
[42] W. Feller,An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed. (Wiley, New York, 1968). · Zbl 0155.23101
[43] W. Feller,An Introduction to Probability Theory and its Applications, Vol. II, 2nd ed. (Wiley, New York, 1971). · Zbl 0219.60003
[44] H.E. Fettis, Numerical calculation of certain definite integrals by Poisson’s summation formula, Math. Tables Other Aids Comput. 9 (1955) 85-92. · Zbl 0066.10601 · doi:10.2307/2002063
[45] B. Fornberg, Numerical differentiation of analytic functions, ACM Trans. Math. Software 7 (1981) 512-526. · Zbl 0465.65012 · doi:10.1145/355972.355979
[46] J. Foster and F.B. Richards, The Gibbs phenomenon for piecewise-linear approximations, Amer. Math. Monthly 98 (1991) 47-49. · Zbl 0735.42001 · doi:10.2307/2324037
[47] B.S. Garbow, G. Giunta, J.N. Lyness and A. Murli, Algorithm 662, A FORTRAN software package for the numerical inversion of the Laplace transform based on Weeks’ method, ACM Trans. Meth. Software 14 (1988) 171-176. · Zbl 0709.65505 · doi:10.1145/45054.214375
[48] W. Gautschi, On the condition of a matrix arising in the numerical inversion of the Laplace transform, Math. Comput. 23 (1969) 109-118. · Zbl 0182.50204 · doi:10.1090/S0025-5718-1969-0239729-8
[49] D.P. Gaver, Jr., Observing stochastic processes and approximate transform inversion, Oper. Res. 14 (1966) 444-459. · doi:10.1287/opre.14.3.444
[50] D.P. Gaver, Jr., Diffusion approximations and models for certain congestion problems, J. Appl. Prob. 5 (1968) 607-623. · Zbl 0194.20801 · doi:10.2307/3211925
[51] J. Gil-Palaez, Note on the inversion theorem, Biometrika 38 (1951) 481-482. · Zbl 0045.07204
[52] I.J. Good, Analogs of Poisson’s sum formula, Amer. Math. Monthly 69 (1962) 259-266. · Zbl 0106.02502 · doi:10.2307/2312938
[53] F.J. Harris, On the use of windows for harmonic analysis with the discrete Fourier transform, Proc. IEEE 66 (1978) 51-83. · doi:10.1109/PROC.1978.10837
[54] P.G. Harrison, Laplace transform inversion and passage-time distributions in Markov processes, J. Appl. Prob. 27 (1990) 74-87. · Zbl 0704.60094 · doi:10.2307/3214596
[55] H. Heffes and D.M. Lucantoni, A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance, IEEE J. Sel. Areas Commun. SAC-4 (1986) 856-868. · doi:10.1109/JSAC.1986.1146393
[56] D.P. Heyman, Mathematical models of database degradation, ACM Trans. Database Sys. 7 (1982) 615-631. · Zbl 0493.68098 · doi:10.1145/319758.319771
[57] G. Honig and U. Hirdes, A method for the numerical inversion of Laplace transforms, J. Comput. Appl. Math. 10 (1984) 113-129. · Zbl 0535.65090 · doi:10.1016/0377-0427(84)90075-X
[58] T. Hosono, Numerical inversion of Laplace transform, J. Inst. Elec. Eng. Jpn. 54?A64 (1979) 494 (in Japanese).
[59] T. Hosono, Numerical inversion of Laplace transform and some applications to wave optics, Radio Sci. 16 (1981) 1015-1019. · doi:10.1029/RS016i006p01015
[60] T. Hosono,Fast Inversion of Laplace Transform by BASIC (Kyoritsu Publishers, Japan, 1984; in Japanese).
[61] T. Hosono, Numerical algorithm for Taylor series expansion, Electronics and Communications in Japan 69 (1986) 10-18.
[62] T. Hosono, K. Yuda and A. Itoh, Analysis of transient response of electromagnetic waves scattered by a perfectly conducting sphere. The case of back- and forward-scattering, Electronics and Communications in Japan 71 (1988) 74-86. · doi:10.1002/ecja.4410711108
[63] J.T. Hsu and J.S. Dranoff, Numerical inversion of certain Laplace transforms by the direct application of fast Fourier transform (FFT) algorithm, Comput. Chem. Engng. 11 (1987) 101-110. · doi:10.1016/0098-1354(87)80011-X
[64] S. Ichikawa and A. Kishima, Application of Fourier-series technique to inverse Laplace transform (Part I), Mem. Fac. Eng. Kyoto U. 34 (1972) 53-67.
[65] S. Ichikawa and A. Kishima, Application of Fourier-series technique to inverse Laplace transform (Part II), Mem. Fac. Eng. Kyoto U. 35 (1973) 393-400.
[66] D.L. Jagerman, An inversion technique for the Laplace transform with applications, Bell Sys. Tech. J. 57 (1978) 669-710. · Zbl 0395.44003
[67] D.L. Jagerman, An inversion technique for the Laplace transform, Bell Sys. Tech. J. 61 (1982) 1995-2002. · Zbl 0496.65064
[68] D.L. Jagerman, MATHCALC, AT&T Bell Laboratories, Holmdel, NJ (1987).
[69] D.L. Jagerman, The approximation sequence of the Laplace transform, AT&T Bell Laboratories, Holmdel, NJ (1989).
[70] R. Johnsonbaugh, Summing an alternating series, Amer. Math. Monthly 86 (1979) 637-648. · Zbl 0425.65002 · doi:10.2307/2321292
[71] J. Keilson, Exponential spectra as a tool for the study of single-server systems, J. Appl. Prob. 15 (1978) 162-170. · Zbl 0386.60072 · doi:10.2307/3213246
[72] D.G. Kendall, A summation formula for finite trigonometric integrals, Quart. J. Math. 13 (1942) 172-184. · Zbl 0060.25704 · doi:10.1093/qmath/os-13.1.172
[73] J.E. Kiefer and G.H. Weiss, A comparison of two methods for accelerating the convergence of Fourier-series, Comput Math. Appl. 7 (1981) 527-535. · Zbl 0466.65002 · doi:10.1016/0898-1221(81)90036-5
[74] Y. Kida, UBASIC Version 8.12, Faculty of Science, Kanazawa University, 1-1 Marunouchi, Kanazawa 920, Japan (1990).
[75] L. Kleinrock,Queueing Systems, Vol. 1: Theory (Wiley, New York, 1975). · Zbl 0334.60045
[76] H. Kobayashi,Modeling and Analysis (Addison-Wesley, Reading, MA, 1978). · Zbl 0423.68001
[77] S. Koizumi, A new method of evaluation of the Heaviside operational expression by Fourier series, Phil. Mag. 19 (1935) 1061-1076. · Zbl 0012.06305
[78] V.I. Krylov and N.S. Skoblya,A Handbook of Methods of Approximate Fourier Transformation and Inversion of the Laplace Transformation (Mir Publ., Moscow, 1977).
[79] Y.K. Kwok and D. Barthez, An algorithm for the numerical inversion of Laplace transforms, Inverse Problems 5 (1989) 1089-1095. · Zbl 0749.65086 · doi:10.1088/0266-5611/5/6/014
[80] E. Lukacs,Characteristic Functions, 2nd ed. (Hafner, New York, 1970). · Zbl 0201.20404
[81] Y.L. Luke, Simple formulas for the evaluation of some higher transcendental functions, J. Math. Phys. 34 (1955) 298-307. · Zbl 0070.12805
[82] J.N. Lyness, Differentiation formulas for analytic functions, Math. Comp. 22 (1968) 352-356. · Zbl 0159.45002 · doi:10.1090/S0025-5718-1968-0230468-5
[83] J.N. Lyness and G. Giunta, A modification of the Weeks method for numerical inversion of the Laplace transform, Math. Comp. 47 (1986) 313-322. · Zbl 0611.65088 · doi:10.1090/S0025-5718-1986-0842138-1
[84] J.N. Lyness and C.B. Moler, Numerical differentation of analytic functions, SIAM J. Numer. Anal. 4 (1967) 202-210. · Zbl 0155.48003 · doi:10.1137/0704019
[85] W.F. Magnus, F. Oberhettinger and R.P. Soni,Formulas and Theorems for the Special Functions of Mathematical Physics (Springer, New York, 1966). · Zbl 0143.08502
[86] M.R. Middleton, Transient effects inM/G/1 queues, Ph.D. dissertation, Stanford University (1979).
[87] P.L. Mills, Numerical inversion of z-transforms with application to polymer kinetics, Comp. Chem. 2 (1987) 137-151. · Zbl 0617.65136 · doi:10.1016/0097-8485(87)80032-3
[88] A. Murli and M. Rizzardi, Algorithm 682, Talbot’s method for the Laplacc inversion problem, ACM Trans. Math. Software 16 (1990) 158-168. · Zbl 0900.65374 · doi:10.1145/78928.78932
[89] N. Mullineux and J.R. Reed, Numerical inversion of integral transforms, Comput. Math. Appl. 3 (1977) 299-306. · Zbl 0377.65067 · doi:10.1016/0898-1221(77)90086-4
[90] R.E. Nancc, U.N. Bhat and B.G. Claybrook, Busy period analysis of a time sharing system: transform inversion, J. ACM 19 (1972) 453-463. · Zbl 0248.68024 · doi:10.1145/321707.321716
[91] I.P. Natanson,Constructive Function Theory, Vol. I, Uniform Approximation (F. Ungar, New York, 1964). · Zbl 0133.31101
[92] W.D. Neumann, UBASIC: A public-domain BASIC for mathematics, Notices Amer. Math. Soc. 36 (1989) 557-559.
[93] A.H. Nuttall, Numerical evaluation of cumulative probability distribution functions directly from characteristic functions, IEEE Proc. 57 (1969) 2071-2072. · doi:10.1109/PROC.1969.7468
[94] F. Oberhettinger,Fourier Transforms of Distributions and Their Inverses (Academic, New York, 1973). · Zbl 0306.65002
[95] W.C. Obi, LAPLACE ? A performance analysis library (PAL) module, AT&T Bell Laboratories, Holmdel, NJ (1987).
[96] R. Piessens, A bibliography on numerical inversion of the Laplace transform and its applications, J. Comput. Appl. Math. 1 (1975) 115-128. · Zbl 0302.65092 · doi:10.1016/0771-050X(75)90029-7
[97] R. Piessens, and N.D.P. Dang, A bibliography on numerical inversion of the Laplace transform and its applications: A supplement, J. Comput. Appl. Math. 2 (1976) 225-228. · Zbl 0334.65098 · doi:10.1016/0771-050X(76)90009-7
[98] R. Piessens and R. Huysmans, Algorithm 619. Automatic numerical inversion of the Laplace transforms, ACM Trans. Math. Softw. 10 (1984) 348-353. · Zbl 0546.65087 · doi:10.1145/1271.319416
[99] L.K. Platzman, J.C. Ammons and J.J. Bartholdi, III, A simple and efficient algorithm to compute tail probabilities from transforms, Oper. Res. 36 (1988) 137-144. · Zbl 0655.65150 · doi:10.1287/opre.36.1.137
[100] S.D. Poisson, Mémoire sur le Calcul Numérique des Integrales Défines, Mem. Acad. Sci. Inst. France 6 (1823) 571-602.
[101] E.L. Post, Generalized differentiation, Trans. Amer. Math. Soc. 32 (1930) 723-781. · JFM 56.0349.01 · doi:10.1090/S0002-9947-1930-1501560-X
[102] L.R. Rabiner and B. Gold,Theory and Application of Digital Signal Processing (Prentice-Hall, Englewood Cliffs, NJ, 1975).
[103] A.A.G. Requicha, Direct computation of distribution functions from characteristic functions using the fast Fourier transform, IEEE Proc. 58 (1970) 1154-1155. · doi:10.1109/PROC.1970.7875
[104] J. Riordan,Stochastic Service Systems (Wiley, New York, 1962). · Zbl 0106.33601
[105] S.O. Rice, Efficient evaluation of integrals of analytic functions by the trapezoidal rule, Bell Sys. Tech. J. 52 (1973) 707-722. · Zbl 0278.65025
[106] S.O. Rice, Numerical evaluation of integrals with infinite limits and oscillating integrands, Bell. Sys. Tech. J. 54 (1975) 155-164.
[107] S. Ross,Stochastic Processes (Wiley, New York, 1983). · Zbl 0555.60002
[108] B. Schorr, Numerical inversion of a class of characteristic functions, BIT 15 (1975) 94-102. · Zbl 0311.65012 · doi:10.1007/BF01933000
[109] M. Silverberg, Improving the efficiency of Laplace-transform Inversion for network analysis, Electronics Lett. 6 (1970) 105-106. · doi:10.1049/el:19700071
[110] R.M. Simon, M.T. Stroot and G.H. Weiss, Numerical inversion of Laplace transforms with applications to percentage labeled experiments, Comput. Biomed. Res. 6 (1972) 596-607. · doi:10.1016/0010-4809(72)90039-0
[111] W.L. Smith, On the distribution of queueing times, Proc. Camb. Phil. Soc. 49 (1953) 449-461. · Zbl 0053.10002 · doi:10.1017/S0305004100028620
[112] W. Squire, The numerical treatment of Laplace transforms: the Koizumi inversion method, Int. J. Num. Meth. Eng. 20 (1984) 1697-1702. · Zbl 0555.65087 · doi:10.1002/nme.1620200912
[113] H. Stehfest, Algorithm 368. Numerical inversion of Laplace transforms, Commun. ACM 13 (1970) 479-49 (erratum 13, 624).
[114] F. Stenger, (1981) Numerical methods based on Whittaker cardinal, or sine functions, SIAM Rev. 23 (1981) 165-224. · Zbl 0461.65007 · doi:10.1137/1023037
[115] D. Stoyan,Comparison Methods for Queues and Other Stochastic Models (Wiley, Chichester, 1983). · Zbl 0536.60085
[116] A. Talbot, The accurate numerical inversion of Laplace transforms, J. Inst. Math. Appl. 23 (1979) 97-120. · Zbl 0406.65054 · doi:10.1093/imamat/23.1.97
[117] D. ter Haar, An easy approximate method of determining the relaxation spectrum of a viscoelastic material, J. Polymer Sci. 6 (1951) 247-250. · doi:10.1002/pol.1951.120060211
[118] H.C. Tijms,Stochastic Modelling and Analysis: A Computational Approach (Wiley, Chichester, 1986). · Zbl 0606.90128
[119] G.P. Tolstov,Fourier Series (Dover, New York, 1976).
[120] B. Van Der Pol and H. Bremmer,Operational Calculus (Cambridge Press, 1955; reprinted, Chelsea, New York, 1987). · Zbl 0066.09101
[121] J.M. Varah, Pitfalls in the numerical solution of linear ill-posed problems, SIAM J. Sci. Stat. Comput. 4 (1983) 164-176. · Zbl 0533.65082 · doi:10.1137/0904012
[122] F. Veillon, Une nouvelle méthode de calcul de la transformée inverse d’une fonction au sens de Laplace et de la deconvolution de deux fonctions, R.A.I.R.O. 6 (1972) 91-98. · Zbl 0246.65036
[123] F. Veillon, Algorithm 486. Numerical inversion of Laplace transform, Commun. AGM 17 (1974) 587-589.
[124] W.T. Weeks, Numerical inversion of Laplace transforms using Laguerre functions, J. ACM 13 (1966) 419-426. · Zbl 0141.33401 · doi:10.1145/321341.321351
[125] D.V. Widder, The inversion of the Laplace integral and the related moment problem, Trans. Amer. Math. Soc. 36 (1934) 107-200. · Zbl 0008.30603 · doi:10.1090/S0002-9947-1934-1501737-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.