zbMATH — the first resource for mathematics

The ratio of the extreme to the sum in a random sequence. (English) Zbl 1164.60021
The ratio \(R_n=X_{(n)}/S_n\) is considered, where \(S_n=\sum_{i=1}^n X_i\), \(X_{(n)}=\max_{1\leq i\leq n} X_i\), \(X_i\) are i.i.d. random variables. It is shown that \({\mathbf E}R_n={{\mathbf E} X{(n)}\over {\mathbf E}S_n}(1+o(1))\) as \(n\to\infty\) if \({\mathbf E}X_i^2<\infty\) or if the survival function of \(X_i\) is regularly varying with the index of variation less then -1. The proof is based on an integral representation for \({\mathbf E}R_n\). The results are applied to a multiprocessor scheduling asymptotical analysis.

60F99 Limit theorems in probability theory
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI
[1] Arov, D.Z., Bobrov, A.A.: The extreme terms of a sample and their role in the sum of independent random variables. Theory Probab. Appl. 5, 377–96 (1960) · Zbl 0098.11202 · doi:10.1137/1105038
[2] Bingham, N.H., Teugels, J.L.: Conditions implying domains of attraction. In: Proceedings of the Sixth Conference on Probability Theory, Editura Academiei Republicii Socialiste Romania, Bucuresti, pp. 23–34 (1981) · Zbl 0469.60027
[3] Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular Variation. Cambridge University Press, Cambridge, England (1987) · Zbl 0617.26001
[4] Breiman, L.: On some limit theorems similar to the arc-sine law. Theory Probab. Appl. 10, 323–31 (1965) · Zbl 0147.37004 · doi:10.1137/1110037
[5] Chow, T.-L., Teugels, J.L.: The sum and the maximum of i.i.d. random variables. In: Mandl, P., Huskova, M. (eds) Asymptotic Statistics: Proc. Second Prague Symposium, pp. 81–92. North-Holland, Amsterdam (1979) · Zbl 0427.60025
[6] Chung, K.L.: A Course in Probability Theory, 2nd Ed. Academic, New York, NY (1974) · Zbl 0345.60003
[7] Coffman, E.G., Gilbert, E.G.: On the expected relative performance of list scheduling. Operat. Res. 33, 548–561 (1985) · Zbl 0569.90044 · doi:10.1287/opre.33.3.548
[8] Coffman, E.G., Lueker, G.S.: Probabilistic Analysis of Packing and Partitioning Algorithms. Wiley, New York, NY (1991) · Zbl 0759.90043
[9] Darling, D.A.: The role of the maximum term in the sum of independent random variables. Trans. AMS 73, 95–107 (1952) · Zbl 0047.37502 · doi:10.1090/S0002-9947-1952-0048726-0
[10] Downey, P.J.: Distribution-free bounds on the expectation of the maximum with scheduling applications. Operat. Res. Lett. 9, 189–201 (1990) · Zbl 0715.90068 · doi:10.1016/0167-6377(90)90018-Z
[11] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA (1979) · Zbl 0411.68039
[12] Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416–429 (1969) · Zbl 0188.23101 · doi:10.1137/0117039
[13] Graham, R.L.: Bounds on the performance of scheduling algorithms. In: Coffman, E.G. Jr. (ed.) Computer and Job-Shop Scheduling Theory. Wiley, New York, NY (1976)
[14] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Handbooks in Operations Research and Management Science, vol. 4, pp. 445–522: Logistics of Production and Inventory. North-Holland, Amsterdam (1993)
[15] McLeish, D.L., O’Brien, G.L.: The expected ratio of the sum of squares to the square of the sum. Ann. Probab. 10, 1019–1028 (1982) · Zbl 0545.60034 · doi:10.1214/aop/1176993722
[16] Maller, R.A., Resnick, S.I.: Limiting behaviour of sums and the term of maximum modulus. Proc. London Math. Soc. 49(3), 385–422 (1984) · Zbl 0543.60038 · doi:10.1112/plms/s3-49.3.385
[17] O’Brien, G.L.: A limit theorem for sample maxima and heavy branches in Galton-Watson trees. J. Appl. Prob. 17, 539–545 (1980) · Zbl 0428.60034 · doi:10.2307/3213043
[18] Olver, F.W.J.: Asymptotics and Special Functions. Academic, New York, NY (1974) · Zbl 0303.41035
[19] Resnick, S.I.: Extreme Values, Regular Variation and Point Processes. Springer, New York, NY (1987) · Zbl 0633.60001
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.