Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 8 (2003) > Paper 9 open journal systems 


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 triangle of the shape . 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: PDF

Pages: 1-26

Published on: June 10, 2003
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489