Limit Theorems for the Number of Maxima in Random Samples from Planar Regions

Zhi-Dong Bai (National University of Singapore)
Hsien-Kuei Hwang (Academia Sinica)
Wen-Qi Liang (Academia Sinica)
Tsung-Hsi Tsai (Academia Sinica)

Abstract


We prove that the number of maximal points in a random sample taken uniformly and independently from a convex polygon is asymptotically normal in the sense of convergence in distribution. Many new results for other planar regions are also derived. In particular, precise Poisson approximation results are given for the number of maxima in regions bounded above by a nondecreasing curve.

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

Pages: 1-41

Publication Date: January 22, 2001

DOI: 10.1214/EJP.v6-76

References

  1. Aldous, D. and Diaconis, P. (1999). Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society (New Series) 36 413-432. MR2000g:60013
  2. Arnold, B. C., Balakrishnan, N. and Nagaraja, H. N. (1998). Records. John Wiley & Sons, Inc., New York. MR2000b:60127
  3. Bai, Z.-D., Chao, C.-C., Hwang, H.-K. and Liang, W.-Q. (1998). On the variance of the number of maxima in random vectors and its applications. Annals of Applied Probability 8 886-895. MR99f:60019
  4. Bai, Z.-D., Hwang, H.-K., Liang, W.-Q. and Tsai, T.-H. (2000) Limit theorems for the number of maxima in random samples from planar regions. Technical Report C-2000-05 , Institute of Statistical Science, Academia Sinica, Taiwan.
  5. Baik, J. and Rains, E. M. (1999). The asymptotics of monotone subsequences of involutions. preprint, 59 pages.
  6. Barndorff-Nielsen, O. and Sobel, M. (1966). On the distribution of the number of admissible points in a vector random sample. Theory of Probability and its Applications 11 249-269. MR34:6819
  7. Baryshnikov, Y. M. (1987) The distribution of the number of nondominating variants. Soviet Journal of Computer and Systems Sciences 24 107-111; translated from Izvestiya Akademii Nauk SSSR. Tekhnicheskaya Kibernetika, 47-50 (1986).MR88i:60165
  8. Baryshnikov, Y. (2000) Supporting-points processes and some of their applications. Probability Theory and Related Fields 117 163-182. MR1771659
  9. Becker,R. A., Denby, L., McGill, R. and Wilks, A. R. (1987). Analysis of data from Places Rated Almanac. American Statistician 41 169-186.
  10. Bentley, J. L., Clarkson, L. L. and Levine, D. B. (1993). Fast linear expected-time algorithms for computing maxima and convex hulls. Algorithmica 9 168-183. MR93m:68161
  11. Blair, C. (1986). Random linear programs with many variables and few constraints. Mathematical Programming 34 62-71. MR88a:90123
  12. Bollobás, B. and Winkler, P. (1988). The longest chain among random points in Euclidean space. Proceedings of the American Mathematical Society 103 347-353. MR89k:60011
  13. Buchta, C. and Reitzner, M. (1997). Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points. Probability Theory and Related Fields 108 385-415. MR98f:52002
  14. Bühlmann, H. (1970). Mathematical Methods in Risk Theory. Die Grundlehren der mathematischen Wissenschaften, Band 172, Springer-Verlag, New York. MR97k:62213
  15. Chow, Y. S. and Teicher, H. (1978). Probability Theory: Independence, Interchangeability, Martingales. Springer-Verlag, New York. MR98e:60003
  16. Datta, A., Maheshwari, A. and Sack, J.-R. (1996). Optimal parallel algorithms for direct dominance problems. Nordic Journal of Computing 3 72-88. MR97d:68234
  17. Devroye, L. (1980). A note on finding convex hulls via maximal vectors. Information Processing Letters 11 53-56. MR82a:68070
  18. Devroye, L. (1986). Lecture Notes on Bucket Algorithms. Birkh"auser Boston, Boston, MA. MR88m:68003
  19. Devroye, L. (1993). Records, the maximal layer, and uniform distributions in monotone sets. Computers and Mathematics with Applications 25 19-31. MR94f:60015
  20. Devroye, L. (1999). A note on the expected time for finding maxima by list algorithms. Algorithmica 23 97-108. MR99m:60071
  21. Dwyer, R. (1990). Kindler, gentler, average-case analysis for convex hulls and maximal vectors. SIGACT News 21 64-71.
  22. Elster, K.-H. (Ed.) (1993). Modern Mathematical Methods of Optimization. Akademie Verlag, Berlin; translated from the Russian by B. Luderer. MR95d:90004
  23. Flajolet, P. and Sedgewick, R. (1995). Mellin transforms and asymptotics: finite differences and Rice's integrals. Theoretical Computer Science 144 101-124. MR96i:39003
  24. Frieze, A. and Pittel, B. G. (1995). Probabilistic analysis of an algorithm in the theory of markets in indivisible goods. Annals of Applied Probability 5 768-808. MR96j:90025
  25. Golin, M. J. (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. MR93m:90059
  26. Güting, R. H., Nurmi, O. and Ottmann, T. (1989). Fast algorithms for direct enclosures and direct dominances. Journal of Algorithms 10 170-186. MR90j:90075
  27. Harsanyi, J. C. (1988). Rational Behavior and Bargaining Equilibrium in Games and Social Situations . Cambridge University Press, Cambridge; Reprint of the 1986 edition. MR89e:90032
  28. Hwang, H.-K. (1998) On convergence rates in the central limit theorems for combinatorial structures. European Journal of Combinatorics 19 329-343. MR99c:60014
  29. Hwang, H.-K. (1999). Asymptotics of Poisson approximation to random discrete distributions: an analytic approach. Advances in Applied Probability 31 448-491. MR2000k:60054
  30. Johnson, N. L., Kotz, S. and Kemp, A. (1992). Univariate Discrete Distributions. Second edition, John Wiley & Sons, New York. MR95d:62018
  31. Karlin, S. (1959). Mathematical Methods and Theory in Games, Programming and Economics, Volume I: Matrix Games, Programming, and Mathematical Economics. Addison-Wesley, Reading, Mass. MR93a:90001
  32. Leitmann, G. and Marzollo, A. (Eds.) (1975). Multicriteria Decision Making. Springer-Verlag, New York. MR56:4862
  33. Preparata, F. P. and Shamos, M. I. (1985). Computational Geometry: An Introduction. Springer-Verlag, New York. MR87d:68102
  34. Rényi, A. (1962). Théorie des éléments saillants d'une suite d'observations. Ann. Fac. Sci. Univ. Clermont-Ferrand No. 8 , 7-13; also in Selected papers of Alfréd Rényi, Volume III: 1962-1970, Edited by Pál Turán, Akadémiai Kiadó, Budapest (1976). MR44:3376
  35. Rényi, A. and Sulanke, R. (1963). Über die konvexe Hülle von n zufällig gewählten Punkten. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2 75-84. MR27:6190
  36. Sholomov, L. A. (1984). Survey of estimational results in choice problems. Engineering Cybernetics 21 51-75. MR85c:90002
  37. Stadler, W. (Ed.) (1988). Multicriteria Optimization in Engineering and in the Sciences. Plenum Press, New York. MR89f:90171
  38. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York. MR87h:90235
  39. Zeleny, M. (1974). Linear Multiobjective Programming. Lecture Notes in Economics and Mathematical Systems, Vol. 95, Springer-Verlag, Berlin-New York. MR50:3928
Bookmark and Share


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