×

zbMATH — the first resource for mathematics

Computing bounds on the expected maximum of correlated normal variables. (English) Zbl 1191.60024
Summary: We compute upper and lower bounds on the expected maximum of correlated normal variables (up to a few hundred in number) with arbitrary means, variances, and correlations. Two types of bounding processes are used: perfectly dependent normal variables, and independent normal variables, both with arbitrary mean values. The expected maximum for the perfectly dependent variables can be evaluated in closed form; for the independent variables, a single numerical integration is required. Higher moments are also available. We use mathematical programming to find parameters for the processes, so they will give bounds on the expected maximum, rather than approximations of unknown accuracy. Our original application is to the maximum number of people on-line simultaneously during the day in an infinite-server queue with a time-varying arrival rate. The upper and lower bounds are tighter than previous bounds, and in many of our examples are within 5% or 10% of each other. We also demonstrate the bounds’ performance on some PERT models, AR/MA time series, Brownian motion, and product-form correlation matrices.

MSC:
60E15 Inequalities; stochastic orderings
60J65 Brownian motion
60K10 Applications of renewal theory (reliability, demand theory, etc.)
65C50 Other computational problems in probability (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler RJ, Taylor JE (2007) Random fields and their geometry. Springer
[2] Azaïs J-M, Wschebor M (2001) Computing the distribution of the maximum of a gaussian process. Technical Report 01/44, Mathematics Dept., Universidad de la Republica, Uruguay · Zbl 0970.60042
[3] Berman SM (1992) Sojourns and extremes of stochastic processes. Wadsworth and Brooks/Cole · Zbl 0809.60046
[4] Bose RC, Gupta SS (1959) Moments of order statistics from a normal population. Biometrika 46(3/4):433–440, Dec · Zbl 0223.62059
[5] Brockwell PJ, Davis RA (1996) Introduction to time series and forecasting. Springer Texts in Statistics
[6] Brodtkorb PA (2006) Evaluating nearly singular multinormal expectations with application to wave distributions. Methodol Comput Appl Probab 8(1):65–91 · Zbl 1103.65014 · doi:10.1007/s11009-006-7289-y
[7] Brown LD, Gans N, Mandelbaum A, Sakov A, Shen H, Zeltyn S, Zhao LH (2005) Statistical analysis of a telephone call center: a queueing-science perspective. J Am Stat Assoc 100(469):36–50, Mar · Zbl 1117.62303 · doi:10.1198/016214504000001808
[8] Chinneck JW (1998) Analyzing mathematical programs using MProbe. Technical Report SCE-98-03, Systems and Computer Engineering, Carleton Univ. Software available at http://www.sce.carleton.ca/faculty/chinneck/mprobe.html · Zbl 1007.90064
[9] Cierco-Ayrolles C, Croquette A, Delmas C (2003) Computing the distribution of the maximum of gaussian random processes. Methodol Comput Appl Probab 5(4):427–438, Dec · Zbl 1033.60047 · doi:10.1023/A:1026233412905
[10] Clark CE (1961) The greatest of a finite set of random variables. Oper Res 9(2):145–162, Mar–Apr · Zbl 0201.51102 · doi:10.1287/opre.9.2.145
[11] Clark CE, Trevor Williams G (1958) Distributions of the members of an ordered sample. Ann Math Stat 29(3):862–870, Sep · Zbl 0086.12301 · doi:10.1214/aoms/1177706542
[12] Coles SG (2001) An introduction to statistical modeling of extreme values. Springer Series in Statistics. Springer · Zbl 0980.62043
[13] Cox DR (1955) Some statistical methods connected with series of events. J Royal Stat Soc B 17:129–164 · Zbl 0067.37403
[14] David HA (1981) Order statistics, 2nd edn. Wiley
[15] Eick SG, Massey WA, Whitt W (1993a) M t /G/ queues with sinusoidal arrival rates. Manage Sci 39(2):241–252, Feb · Zbl 0773.60086 · doi:10.1287/mnsc.39.2.241
[16] Eick SG, Massey WA, Whitt W (1993b) The physics of the M t /G/ queue. Oper Res 41(4):731–742, Jul–Aug · Zbl 0781.60086 · doi:10.1287/opre.41.4.731
[17] Genz A (1992) Numerical computation of multivariate normal probabilities. J Comput Graph Stat 1:141–149 · doi:10.2307/1390838
[18] Genz A, Monahan J (1999) A stochastic algorithm for high dimensional multiple integrals over unbounded regions with Gaussian weight. J Comput Appl Math 112(1–2):71–81, Nov · Zbl 0943.65034 · doi:10.1016/S0377-0427(99)00214-9
[19] Grandell J (1997) Mixed poisson processes. Number 77 in monographs on statistics and applied probability. Chapman and Hall · Zbl 0922.60005
[20] Green LV, Kolesar PJ, Svoronos A (1991) Some effects of nonstationarity on multiserver Markovian queueing systems. Oper Res 39(3):502–511, May–Jun · Zbl 0729.60100 · doi:10.1287/opre.39.3.502
[21] Henderson SG, Chen BPK (2001) Two issues in setting call centre staffing levels. Ann Oper Res 108(1–4):176–192, Nov · Zbl 1001.90503
[22] Hillier FS, Lieberman GJ (1995) Introduction to operations research, 7th edn. McGraw-Hill
[23] Kang S, Serfozo RF (1999) Extreme values of phase-type and mixed random variables with parallel-processing examples. J Appl Probab 36(1):194–210, Jun · Zbl 0948.60017 · doi:10.1239/jap/1032374241
[24] Lai TL, Robbins H (1976) Maximally dependent random variables. Proceedings of the National Academy of the Sciences USA 73(2):286–288, Feb · Zbl 0352.60013 · doi:10.1073/pnas.73.2.286
[25] Leadbetter MR, Lindgren G, Rootzen H (1983) Extremes and related properties of random sequences and processes. Springer Series in Statistics. Springer · Zbl 0518.60021
[26] Malcolm DG, Roseboom JH, Clark CE, Fazar W (1959) Application of a technique for research and development program evaluation. Oper Res 7:646–669 · Zbl 1255.90070 · doi:10.1287/opre.7.5.646
[27] Owen DB, Steck GP (1962) Moments of order statistics from the equicorrelated multivariate normal distribution. Ann Math Stat 33(4):1286–1291, Dec · Zbl 0107.36302 · doi:10.1214/aoms/1177704361
[28] Palm C (1988) Intensity variations in telephone traffic (translation of 1943 article in Ericcson Technics, vol 44, pp 1–189). North-Holland, Amsterdam
[29] Ross AM (2003a) Useful bounds on the expected maximum of correlated normal variables. Technical Report 03W-004, ISE Dept., Lehigh Univ., Aug
[30] Ross SM (2003b) Introduction to probability models, 8th edn. Academic Press · Zbl 1019.60003
[31] Ross AM, George Shanthikumar J (2008) Dial-up internet access: a two-provider cost model. Queueing Syst 51:5–27 · Zbl 1142.60407 · doi:10.1007/s11134-005-1671-2
[32] Slepian D (1962) The one-sided barrier problem for Gaussian processes. Bell Syst Tech J 41:463–501
[33] Teichroew D (1956) Tables of expected values of order statistics and products of order statistics for samples of size twenty or less from the normal distribution. Ann Math Stat 27(2):410–426, Jun · Zbl 0071.13501 · doi:10.1214/aoms/1177728266
[34] Thompson GM (1999) Setting staffing levels in pure service environments when the true mean daily customer arrival rate is a normal random variate (working paper)
[35] Tippett LHC (1925) On the extreme individuals and the range of samples taken from a normal population. Biometrika 17(3/4):364–387, Dec · JFM 51.0392.01
[36] Tong YL (1990) The multivariate normal distribution. Springer · Zbl 0689.62036
[37] Vitale RA (2000) Some comparisons for Gaussian processes. Proceedings of the American Math. Society 128(10):3043–3046 · Zbl 0955.60036 · doi:10.1090/S0002-9939-00-05367-3
[38] Yates R, Goodman D (2005) Probability and stochastic processes: a friendly introduction for electrical and computer engineers, 2nd edn. Wiley · Zbl 1059.60002
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.