On random variate generation when only moments of Fourier coefficients are known. (English) Zbl 0677.65007
Essentially the method is a combination of acception/rejection with use of approximating series such that each succeeding member within the series is needed indeed only with (heavily) decreasing probability, which fact results in (unexpected) low expense in computation in all probability, for each number to be generated.
The discussed cases and examples exhibit also easily evaluable rejection criteria. The needed proofs succeed under weak assumptions concerning the distribution and the approximations. Knowledge of the first Fourier coefficient or moments is presupposed; for even functions with convex decreasing Fourier coefficients even no estimate of the series remainder is needed: usually the calculation requires comparison of the remaining rest of the infinite series, which may be delimited from above by an estimation with moderate computation-up to sufficient precision.
Besides standard Fourier series other kinds are considered: Legendre and Laguerre/Hermite polynomials, furthermore estimations derived from Lipschitz conditions. The resulting programs are elegantly short, even for usage of so-called \(\theta\) factors with Fourier series (reminding of relaxation coefficients) to improve (“smoothe”) the approximation and with many classes for the calculation of good estimates to the series remainder.
The probable, expected numbers of iteration, i.e. mainly the number of needed members in the series, for one random number to be generated are derived. The user should check the variance of these numbers and the effect of the limited precision in the computing system, when the programs are applied.
The discussed cases and examples exhibit also easily evaluable rejection criteria. The needed proofs succeed under weak assumptions concerning the distribution and the approximations. Knowledge of the first Fourier coefficient or moments is presupposed; for even functions with convex decreasing Fourier coefficients even no estimate of the series remainder is needed: usually the calculation requires comparison of the remaining rest of the infinite series, which may be delimited from above by an estimation with moderate computation-up to sufficient precision.
Besides standard Fourier series other kinds are considered: Legendre and Laguerre/Hermite polynomials, furthermore estimations derived from Lipschitz conditions. The resulting programs are elegantly short, even for usage of so-called \(\theta\) factors with Fourier series (reminding of relaxation coefficients) to improve (“smoothe”) the approximation and with many classes for the calculation of good estimates to the series remainder.
The probable, expected numbers of iteration, i.e. mainly the number of needed members in the series, for one random number to be generated are derived. The user should check the variance of these numbers and the effect of the limited precision in the computing system, when the programs are applied.
Reviewer: K.G.Brokate
MSC:
| 65C10 | Random number generation in numerical analysis |
| 62-04 | Software, source code, etc. for problems pertaining to statistics |
Keywords:
random variate generation; series method for random numbers; acception/rejection; Fourier coefficient; moments; estimation; Fourier series; numbers of iterationReferences:
| [1] | Ahrens, J. H.; Kohrt, K. D., Computer methods for efficient sampling from largely arbitrary statistical distributions, Computing, 26, 19-31 (1981) · Zbl 0426.65003 |
| [2] | Bary, N. K., A Treatise on Trigonometric Series, Vol. I (1964), Macmillan: Macmillan New York, NY · Zbl 0129.28002 |
| [3] | Bary, N. K., A Treatise on Trigonometric Series, Vol. II (1964), Macmillan: Macmillan New York, NY · Zbl 0129.28002 |
| [4] | Butzer, P. L.; Nessel, R. J., Fourier Analysis and Approximation (1971), Birkhauser: Birkhauser Basel · Zbl 0217.42603 |
| [5] | Carleson, L., On convergence and growth of partial sums of Fourier series, Acta Mathematica, 116, 135-157 (1966) · Zbl 0144.06402 |
| [6] | Cramer, H., On some classes of series used in mathematical statistics, Skandinaviske Matematikercongres (1976), Copenhagen · JFM 52.0518.01 |
| [7] | Devroye, L., The computer generation of random variables with a given characteristic function, Comput. Math. Appl., 7, 547-552 (1981) · Zbl 0469.65002 |
| [8] | Devroye, L., The series method in random variate generation and its application to the Kolmogorov-Smirnov distribution, Amer. J. Math.& Management Sci., 1, 359-379 (1981) · Zbl 0535.65002 |
| [9] | Devroye, L., On the use of probability inequalities in random variate generation, J. Statist. Computation & Simulation, 20, 91-100 (1984) · Zbl 0568.65002 |
| [10] | Devroye, L., Methods for generating random variates with Polya characteristic functions, Statist. & Probab. Lett., 2, 257-261 (1984) · Zbl 0568.65003 |
| [11] | Devroye, L., Nonuniform Random Variate Generation (1986), Springer: Springer Berlin, New York · Zbl 0584.65002 |
| [12] | Devroye, L., An automatic method for generating random variables with a given characteristic function, SIAM J. Appl. Math., 46, 698-719 (1986) · Zbl 0615.65002 |
| [13] | Devroye, L., Algorithms for generating discrete random variables with a given generating function or a given moment sequence, SIAM J. Scientific & Statist. Comput. (1988), to appear |
| [14] | Devroye, L.; Gyorfi, L., Nonparametric Density Estimation: The \(L_1\) View (1985), Wiley: Wiley New York · Zbl 0546.62015 |
| [15] | Edwards, R. E., Fourier Series: A Modern Introduction, Vol. 1 (1979), Springer: Springer Berlin/New York · Zbl 0424.42001 |
| [16] | Erdelyi, A.; Magnus, W.; Oberhettinger, F.; Tricomi, F., Higher Transcendental Functions, (Bateman Manuscript Project, Vol. II (1953), McGraw-Hill: McGraw-Hill New York) · Zbl 0052.29502 |
| [17] | Favard, J., Sur les meilleurs procedes d’approximation, (Bull. Soc. Math. de France, 61 (1937)). (Bull. Soc. Math. de France, 61 (1937)), 243-256 · Zbl 0017.25101 |
| [18] | Hunt, R. A., On the convergence of Fourier series, (Proc. Conf. on Orthogonal Expansions and Their Continuous Analogues (1968), Southern Illinois University Press: Southern Illinois University Press Carbondale, IL), 235-255, Edwardsville, IL · Zbl 0159.35701 |
| [19] | Jackson, D., The Theory of Approximation, Vol. 11 (1930), American Mathematical Society: American Mathematical Society Providence, RI, Colloquia Publications · JFM 56.0936.01 |
| [20] | Jorsboe, O. G.; Mejlbro, L., The Carleson-Hunt Theorem of Fourier Series (1982), Springer: Springer Berlin · Zbl 0493.42002 |
| [21] | Kendall, M.; Stuart, A., The Advanced Theory of Statistics, Vol. 1 (1977), Macmillan: Macmillan New York · Zbl 0353.62013 |
| [22] | Kolmogorov, A. N., Une serie de Fourier-Lebesgue divergente partout, Comptes Rendus de l’Academie des Sciences de Paris, 183, 1327-1328 (1926) · JFM 52.0269.02 |
| [23] | Korner, T. W., Everywhere divergent Fourier series, Coll. Math., 45, 103-118 (1981) · Zbl 0491.42011 |
| [24] | Kronmal, R. A.; Peterson, A. V., Generating normal random variables using the alias-rejection-mixture method, Proc. 1979 ASA Ann. Meeting, Computer Section (1980), Washington, D.C. |
| [25] | Marsaglia, G.; Maclaren, M. D.; Bray, T. A., A fast procedure for generating normal random variables, Comm. ACM, 7, 4-10 (1964) · Zbl 0127.09005 |
| [26] | Mozzochi, C. J., On The Pointwise Convergence of Fourier Series (1971), Springer: Springer Berlin · Zbl 0218.42006 |
| [27] | Muckenhoupt, B., Equiconvergence and almost everywhere convergence of Hermite and Laguerre series, SIAM J. Math. Analysis, 1, 295-321 (1970) · Zbl 0201.08501 |
| [28] | Picone, M., Appunti di Analise Superiore (1940), Naples · JFM 66.0198.01 |
| [29] | Sansone, G., Orthogonal Functions (1977), Krieger: Krieger Huntington, NY · Zbl 0341.42010 |
| [30] | Shohat, J. A.; Tamarkin, J. D., The Problems of Moments, (Mathematical Survey No. 1 (1943), American Mathematical Society: American Mathematical Society New York) · Zbl 0112.06902 |
| [31] | Stone, M. H., Developments in Hermite polynomials, Ann. Math., 29, 1-13 (1928) · JFM 53.0271.01 |
| [32] | Szego, G., Orthogonal Polynomials, (Colloquia Publications, Vol. 23 (1975), American Mathematical Society: American Mathematical Society Providence, RI) · JFM 65.0278.03 |
| [33] | Ulrich, G., Computer generation of distributions on the \(m\)-sphere, Appl. Statist., 33, 158-163 (1984) · Zbl 0547.65095 |
| [34] | Widder, D. V., The Laplace Transform (1941), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0060.24801 |
| [35] | Zygmund, A., Trigonometrical Series, Vols. 1, 2 (1959), Cambridge University Press: Cambridge University Press Oxford/New York · JFM 61.0263.03 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
