Multivariate Records Based on Dominance

Hsien-Kuei Hwang (Academia Sinica Taipei)
Tsung-Hsi Tsai (Academia Sinica Taipei)

Abstract


We consider three types of multivariate records in this paper and derive the mean and the variance of their numbers for independent and uniform random samples from two prototype regions: hypercubes $[0,1]^d$ and d-dimensional simplex. Central limit theorems with convergence rates are established when the variance tends to infinity. Effective numerical procedures are also provided for computing the variance constants to high degree of precision.

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

Pages: 1863-1892

Publication Date: November 16, 2010

DOI: 10.1214/EJP.v15-825

References

  1. Z.-D. Bai, L. Devroye, H.-K. Hwang and H.-T. Tsai, Maxima in hypercubes, Random Structures Algorithms 27 (2005), 290-309. Math. Review 2162600
  2. Z.-D. Bai, H.-K. Hwang, W.-Q. Liang and T.-H. Tsai, Limit theorems for the number of maxima in random samples from planar regions, Electron. J. Probab. 6 (2001), no. 3, 41 pp. (electronic). Math. Review 1816046
  3. J. Baik, P. Deift and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc. 12 (1999), 1119-1178. Math. Review 1682248
  4. Yu. Baryshnikov and A. Gnedin, Counting intervals in the packing process, Ann. Appl. Probab. 11 (2001), 863-877. Math. Review 1865026
  5. W.-M. Chen, H.-K. Hwang and T.-H. Tsai, Maxima-finding algorithms for multidimensional samples: A two-phase approach, preprint, 2010. Math. Review number not available.
  6. H.-H. Chern, M. Fuchs and H.-K. Hwang, Phase changes in random point quadtrees, ACM Trans. Algorithms 3 (2007), no. 2, Art. 12, 51 pp. Math. Review 2335295
  7. H.-H. Chern, H.-K. Hwang and T.-H. Tsai, An asymptotic theory for Cauchy-Euler differential equations with applications to the analysis of algorithms, J. Algorithms 44 (2002), 177-225. Math. Review 1933199
  8. 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, Ann. Appl. Probab. 7 (1997), 802-814. Math. Review 1459271
  9. A. Darrasse, H.-K. Hwang, O. Bodini and M. Soria, The connectivity-profile of random increasing k-trees, preprint (2009); available at arXiv:0910.3639v1. Math. Review number not available.
  10. J.-D. Deuschel and O. Zeitouni, Limiting curves for iid records, Ann. Probab. 23 (1995), 852-878. Math. Review 1334175
  11. L. Devroye, Universal limit laws for depths in random trees, SIAM J. Comput. 28 (1999), 409-432. Math. Review 1634354
  12. P. Flajolet, X. Gourdon and P. Dumas, Mellin transforms and asymptotics: harmonic sums, Theoret. Comput. Sci. 144 (1995), 3-58. Math. Review 1337752
  13. P. Flajolet, G. Labelle, L. Laforest and B. Salvy, Hypergeometrics and the cost structure of quadtrees, Random Structures Algorithms 7 (1995), 117-144. Math. Review 1369059
  14. P. Flajolet and R. Sedgewick, Mellin transforms and asymptotics: finite differences and Rice's integrals, Theoret. Comput. Sci. 144 (1995), 101-124. Math. Review 1337755
  15. P. Flajolet and R. Sedgewick, Analytic Combinatorics}, Cambridge University Press, Cambridge, 2009. Math. Review 2483235
  16. A. Gnedin, Records from a multivariate normal sample, Statist. Prob. Lett. 39 (1998) 11-15. Math. Review 01649331
  17. A. Gnedin, The chain records, Electron. J. Probab. 12 (2007), 767-786. Math. Review 2318409
  18. C. M. Goldie and S. Resnick, Records in a partially ordered set, Ann. Probab 17 (1989), 678-699. Math. Review 985384
  19. C. M. Goldie and S. Resnick, Many multivariate records, Stoch. Process. Appl. 59 (1995), 185-216. Math. Review 1357651
  20. E. Hashorva and J. Hüsler, On asymptotics of multivariate integrals with applications to records, Stoch. Models 18 (2002), 41-69. Math. Review 1888285
  21. E. Hashorva and J. Hüsler, Multiple maxima in multivariate samples, Stoch. Prob. Letters 75 (2005), 11-17. Math. Review 2185605
  22. H.-K. Hwang, On convergence rates in the central limit theorems for combinatorial structures, European J. Combin. 19 (1998), 329-343. Math. Review 1621021
  23. M. Kałuszka, Estimates of some probabilities in multidimensional convex records, Appl. Math. (Warsaw) 23 (1995), 1-11. Math. Review 1330054
  24. A. M. Vershik and S. V. Kerov, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Soviet Math. Dokl. 233 (1977), 527-531. Math. Review 0480398
Bookmark and Share


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