Improved bounds on bell numbers and on moments of sums of random variables

• Autorzy: Berend D. , Tassa T.
• Języki publikacji: EN

Abstrakty

EN

We provide bounds for moments of sums of sequences of independent random variables. Concentrating on uniformly bounded nonnegative random variables, we are able to improve upon previous results due to Johnson et al. [10] and Latała [12]. Our basic results provide bounds involving Stirling numbers of the second kind and Bell numbers. By deriving novel effective bounds on Bell numbers and the related Bell function, we are able to translate our moment bounds to explicit ones, which are tighter than previous bounds. The study was motivated by a problem in operation research, in which it was required to estimate the L_p-moments of sums of uniformly bounded non-negative random variables (representing the processing times of jobs that were assigned to some machine) in terms of the expectation of their sum.

Słowa kluczowe

EN

sums of random variables; moments; bounds on moments; binomial distribution; Poisson distribution; Stirling numbers; Bell numbers

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2010
• Tom: Vol. 30, Fasc. 2
• Strony: 185--205
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Berend D.

• Departments of Mathematics and of Computer Science, Ben-Gurion University of the Negev, Beer Sheva, Israel

autor

Tassa T.

• Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel

Bibliografia

• [1] N. Alon, Y. Azar, G. Woeginger and T. Yadid, Approximation schemes for scheduling, in: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 493-500.
• [2] N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, New York, NY, 1958.
• [3] A. K. Chandra and C. K. Wong, Worst-case analysis of a placement algorithm related to storage allocation, SIAM J. Computing 4 (1975), pp. 249-263.
• [4] R. A. Cody and E. G. Coffman, Jr., Record allocation for minimizing expected retrieval costs on drum-like storage devices, J. Assoc. Comput. Mach. 23 (1976), pp. 103-115.
• [5] G. Dobinski, Summierung der reihe Σnm=m! für m = 1; 2; 3; 4; 5;…., Grunert Archiv (Arch. Math. Phys.) 61 (1877), pp. 333-336.
• [6] T. Figiel, P. Hitczenko, W. B. Johnson, G. Schechtman and J. Zinn, Extremal properties of Rademacher functions with applications to the Khintchine and Rosenthal inequalities, Trans. Amer. Math. Soc. 349 (1997), pp. 997-1027.
• [7] B. Fristedt and L. Gray, A Modern Approach to Probability Theory, Birkhäuser, Boston, MA, 1997.
• [8] R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969), pp. 416-429.
• [9] W. Hoeffding, On the distribution of the number of successes in independent trials, Ann. Math. Statist. 27 (1956), pp. 713-721
• [10] W. B. Johnson, G. Schechtman and J. Zinn, Best constants in moment inequalities for linear combinations of independent and exchangeable random variables, Ann. Probab. 13 (1985), pp. 234-253.
• [11] A. Khintchine, Über dyadische Bru¨che, Math. Z. 18 (1923), pp. 109-116.
• [12] R. Latała, Estimation of moments of sums of independent real random variables, Ann. Probab. 25 (1997), pp. 1502-1513.
• [13] A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-Hill, New York, NY, 1984.
• [14] V. H. de la Peña, R. Ibragimov and S. Sharakhmetov, On extremal distribution and sharp Lp-bounds for sums of multilinear forms, Ann. Probab. 31 (2003), pp. 630-675.
• [15] J. Pitman, Some probabilistic aspects of set partitions, Amer. Math. Monthly 104 (1997), pp. 201-209.
• [16] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, NY, 1980.
• [17] H. Robbins, A remark on Stirling’s formula, Amer. Math. Monthly 62 (1955), pp. 26-29.
• [18] H. Shachnai and T. Tassa, Approximation ratios for stochastic list scheduling, preprint.