Records, the maximal layer, and uniform distributions in monotone sets. (English) Zbl 0769.60044
Summary: Consider a nondecreasing nonnegative integrable function \(f\) on [0,1]. Draw an independent sample \((X_ 1,Y_ 1),\dots,(X_ n,Y_ n)\) of size \(n\) from the uniform distribution under \(f\), and let \(N_ n\) be the number of records in the sample, where \((X_ i,Y_ i)\) is a record when, for all \(j\neq i\), either \(X_ j>X_ i\) or \(Y_ j<Y_ i\). We study the dependence upon \(f\) of the constant \(C\) in the asymptotic formula \(\mathbb{E} N_ n\sim C\sqrt n\), and show that whenever \(\int^ 1_ 0f'>0\), \(N_ n/\mathbb{E} N_ n\to 1\) in probability. The results are related to the expected time analysis of algorithms for finding the collection of all records (i.e., the maximal layer).
MSC:
| 60G70 | Extreme value theory; extremal stochastic processes |
References:
| [1] | Glick, N., Breaking records and breaking boards, American Mathematical Monthly, 85, 2-26 (1978) · Zbl 0395.62040 |
| [2] | Rényi, A., Théorie des éléments saillants d’une suite d’observations, (Colloquium on Combinatorial Methods in Probability Theory (1962), Mathematisk Institut, Aarhus Universitet: Mathematisk Institut, Aarhus Universitet Denmark), 104-115 · Zbl 0139.35303 |
| [3] | Kung, H. T.; Luccio, F.; Preparata, F. P., On finding the maxima of a set of vectors, Journal of the ACM, 22, 469-476 (1975) · Zbl 0316.68030 |
| [4] | Bentley, J. L.; Shamos, M. I., Divide and conquer for linear expected time, Information Processing Letters, 7, 87-91 (1978) · Zbl 0404.68046 |
| [5] | Bentley, J. L.; Kung, H. T.; Schkolnick, M.; Thompson, C. D., On the average number of maxima in a set of vectors and applications, Journal of the ACM, 25, 536-543 (1982) · Zbl 0388.68056 |
| [6] | Gabow, H. N.; Bentley, J. L.; Tarjan, R. E., Scaling and related techniques for geometry problems, (Proceedings of the \(16^{th}\) Annual Symposium on the Theory of Computing (1984)), 135-143 |
| [7] | Machii, M.; Igarashi, Y., A hashing method of finding the maxima of a set of vectors, (Technical Report CS-84-2 (1984), Department of Computer Science, Gunma University: Department of Computer Science, Gunma University Gunma, Japan) |
| [8] | Kirkpatrick, D.; Seidel, R., The ultimate planar convex hull algorith, SIAM Journal on Computing, 15, 287-299 (1986) · Zbl 0589.68035 |
| [9] | Kapoor, S.; Ramanan, P., Lower bounds for maximal and convex layers problems, Algorithmica, 4, 447-459 (1989) · Zbl 0684.68053 |
| [10] | Frederickson, G. N.; Rodger, S., A new approach to the dynamic maintenance of maximal points in a plane, Discrete Computational Geometry, 5, 365-374 (1990) · Zbl 0714.68013 |
| [11] | Bentley, J. L.; Clarkson, K. L.; Levine, D. B., Fast linear expected-time alorithms for computing maxima and convex hulls, (Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (1990), SIAM: SIAM Philadelphia), 179-187 · Zbl 0800.68959 |
| [12] | Janardan, R., On the dynamic maintenance of maximal points in the plane, Information Processing Letters, 40, 59-64 (1991) · Zbl 0751.68074 |
| [13] | Barndorff-Nielsen, O.; Sobel, M., On the distribution of the number of admissible points in a vector, Theory of Probability and its Applications, 11, 249-269 (1966) · Zbl 0278.60007 |
| [14] | Devroye, L., A note on finding convex hulls via maximal vectors, Information Processing Letters, 11, 53-56 (1980) · Zbl 0444.68063 |
| [15] | Devroye, L., Moment inequalities for random variables in computational geometry, Computing, 30, 111-119 (1983) · Zbl 0502.60016 |
| [16] | Devroye, L., On the expected time required to construct the outer layer, Information Processing Letters, 20, 255-257 (1985) · Zbl 0572.68032 |
| [17] | Buchta, C., On the average number of maxima in a set of vectors, Information Processing Letters, 33, 63-65 (1989) · Zbl 0682.68041 |
| [18] | Dwyer, R. A., Kinder, gentler average-case analysis for convex hulls and maximal vectors, SIGACT News, 21, 64-71 (1990) |
| [19] | Natanson, I. P., Theory of Functions of a Real Variable (1955), Frederick Ungar Publ. Co: Frederick Ungar Publ. Co New York · Zbl 0064.29102 |
| [20] | Rényi, A.; Sulanke, R., Über die konvexe Hulle von \(n\) zufällig gewahlten Punkten, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2, 75-84 (1963) · Zbl 0118.13701 |
| [21] | Devroye, L., Lecture Notes on Bucket Algorithms, ((1986), Birkhäuser Verlag: Birkhäuser Verlag Boston) · Zbl 0644.68086 |
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.
