Berry-Esseen Bounds for the Number of Maxima in Planar Regions

Zhi-Dong Bai (National University of Singapore and Northeast Normal University)
Hsien-Kuei Hwang (Academia Sinica, Taipei)
Tsung-Hsi Tsai (Academia Sinica, Taipei)

Abstract


We derive the optimal convergence rate $O(n^{-1/4})$ in the central limit theorem for the number of maxima in random samples chosen uniformly at random from the right equilateral triangle with two sides parallel to the axes, the hypotenuse with the slope $-1$ and consituting the top part of the boundary of the triangle. A local limit theorem with rate is also derived. The result is then applied to the number of maxima in general planar regions (upper-bounded by some smooth decreasing curves) for which a near-optimal convergence rate to the normal distribution is established.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-26

Publication Date: June 10, 2003

DOI: 10.1214/EJP.v8-137

References

  1. Z.-D. Bai, C.-C. Chao, H.-K. Hwang and W.-Q. Liang (1998). On the variance of the number of maxima in random vectors and its applications, Annals of Applied Probability, 8, 886-895. Math. Review link
  2. Z.-D. Bai, H.-K. Hwang, W.-Q. Liang, and T.-H. Tsai (2001). Limit theorems for the number of maxima in random samples from planar regions, Electronic Journal of Probability, 6, paper no. 3, 41 pages; available at www.math.washington.edu/~ejpecp/EjpVol6/paper3.pdf  Math. Review link
  3. Yu. V. Prohorov (1953), Asymptotic behavior of the binomial distribution, in  Selected Translations in Mathematical Statistics and Probability, Vol. 1, pp. 87-95, ISM and AMS, Providence, R.I. (1961); translation from Russian of: Uspehi Matematiceskih Nauk, 8 (1953), no. 3 (35), 135-142. Math. Review link
  4. A. D. Barbour and A. Xia (2001). The number of two dimensional maxima, Advances in Applied Probability, 33, 727-750. Math. Review link
  5. Y. Baryshnikov (2000). Supporting-points processes and some of their applications, Probability Theo ry and Related Fields, 117, 163-182. Math. Review link
  6. R. A. Becker, L. Denby, R. McGill and A. R. Wilks (1987). Analysis of data from the "Places Rated Almanac", The American Statistician, 41, 169-186.
  7. A. J. Cabo and P. Groeneboom (1994). Limit theorems for functionals of convex hulls, Probability The ory and Related Fields, 100, 31-55. Math. Review link
  8. T. M. Chan (1996). Output-sensitive results on convex hulls, extreme points, and related problems, Discrete and Computational Geometry, 16, 369-387. Math. Review link
  9. S. N. Chiu and M. P. Quine, Central limit theory for the number of seeds in a growth model in Rd with inhomogeneous Poisson arrivals, Annals of Applied Probability, 7 (1997), 802-814. Math. Review link
  10. A. Datta and S. Soundaralakshmi (2000), An effcient algorithm for computing the maximum empty rectangle in three dimensions, Information Sciences, 128, 43-65. Math. Review link
  11. L. Devroye (1993). Records, the maximal layer, and the uniform distributions in monotone sets, Computers and Mathematics with Applications, 25, 19-31. Math. Review link
  12. M. E. Dyer and J. Walker (1998). Dominance in multi-dimensional multiple-choice knapsack problems, Asia-Pacific Journal of Operational Research, 15, 159-168. Math. Review link
  13. I. Z. Emiris, J. F. Canny and R. Seidel (1997). Effcient perturbations for handling geometric degeneracies, Algorithmica, 19, 219-242. Math. Review link
  14. J. L. Ganley (1999). Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, Discrete Applied Mathematics, 90, 161-171. Math. Review link
  15. M. J. Golin (1993). Maxima in convex regions, in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, (Austin, TX, 1993), 352-360, ACM, New York. Math. Review link
  16. P. Groeneboom (1988), Limit theorems for convex hulls, Probability Theory and Related Fields, 79, 327-368. Math. Review link
  17. H.-K. Hwang (2002). Second phase changes in random m-ary search trees and generalized quicksort: convergence rates, Annals of Probability, 31, 609-629. Math. Review link
  18. R. E. Johnston and L. R. Khan (1995). A note on dominance in unbounded knapsack problems, Asia-Paciffic Journal of Operational Research, 12, 145-160. Math. Review link
  19. S. Martello and P. Toth (1990). Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, New York. Math. Review link
  20. R. Neininger and L. Rüschendorf (2002). A general contraction theorem and asymptotic normality in combinatorial structures, Annals of Applied Probability, accepted for publication (2003); available at www.math.uni-frankfurt.de/~neiningr/.
  21. V. V. Petrov (1975). Sums of Independent Random Variables, Springer-Verlag, New York. Math. Review link
  22. M. Zachariasen (1999). Rectilinear full Steiner tree generation, Networks, 33, 125-143. Math. Review link
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.