Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T13:58:18.575Z Has data issue: false hasContentIssue false
  • English
  • Français

The limit distribution of the maximum probability nearest-neighbour ball

Part of: Stochastic processes Limit theorems

Published online by Cambridge University Press:  30 July 2019

László Györfi ,
Norbert Henze  and
Harro Walk
László Györfi*
Affiliation:
Budapest University of Technology and Economics
Norbert Henze*
Affiliation:
Karlsruhe Institute of Technology (KIT)
Harro Walk*
Affiliation:
University of Stuttgart
*
*Postal address: Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar Tudósok krt. 2., Budapest, H-1117, Hungary.
**Postal address: Institute of Stochastics, Karlsruhe Institute of Technology (KIT), Englerstr. 2, D-76133 Karlsruhe, Germany.
***Postal address: Institute of Stochastics and Applications, University of Stuttgart, Pfaffenwaldring 57, D-70569 Stuttgart, Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

Let X1, …, Xn be independent random points drawn from an absolutely continuous probability measure with density f in ℝd. Under mild conditions on f, wederive a Poisson limit theorem for the number of large probability nearest-neighbour balls. Denoting by Pn the maximum probability measure of nearest-neighbour balls, this limit theorem implies a Gumbel extreme value distribution for nPn − ln n as n → ∞. Moreover, we derive a tight upper bound on the upper tail of the distribution of nPn − ln n, which does not depend on f.

Keywords

Nearest neighbourGumbel extreme value distributionPoisson limit theoremexchangeable event

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 60G09: Exchangeability 60G70: Extreme value theory; extremal processes
Type
Research Papers
Information
Journal of Applied Probability , Volume 56 , Issue 2 , June 2019 , pp. 574 - 589
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baccelli, F. and Blaszczyszyn, B. (2009). Stochastic Geometry and Wireless Networks: Theory (Foundations Trends Networking 3), Vol. I. NoW Publishers.Google Scholar
Baccelli, F. and Blaszczyszyn, B. (2010). Stochastic Geometry and Wireless Networks: Applications (Foundations Trends Networking 4), Vol. II. NoW Publishers.Google Scholar
Biau, G. and Devroye, L. (2015). Lectures on the Nearest Neighbor Method. Springer, Cham.CrossRefGoogle Scholar
Billingsley, P. (1986). Probability and Measure. John Wiley, New York.Google Scholar
Calka, P. and Chenavier, N. (2014). Extreme values for characteristic radii of a Poisson-Voronoi tessellation. Extremes 17, 359–385.CrossRefGoogle Scholar
Chenavier, N. and Hemsley, R. (2016). Extremes for the inradius in the Poisson line tessellation. Adv. Appl. Prob. 48, 544–573.CrossRefGoogle Scholar
Devroye, L. and Györfi, L. (1985). Nonparametric Density Estimation: The L1 View. John Wiley, New York.Google Scholar
Devroye, L., Györfi, L. and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. Springer, New York.CrossRefGoogle Scholar
Fritz, J. (1975). Distribution-free exponential error bound for nearest neighbor pattern classification. IEEE Trans. Inf. Theory IT-21, 552–557.CrossRefGoogle Scholar
Graham, R.L., Knuth, D.E. and Patashnik, O. (1994). Concrete Mathematics. Addison-Wesley, Reading, MA.Google Scholar
Györfi, L., Kohler, M., KrzyZak, A. and Walk, H. (2002). A Distribution-Free Theory of Nonparametric Regression. Springer, New York.CrossRefGoogle Scholar
Henze, N. (1982). The limit distribution for maxima of ‘weighted’ rth-nearest-neighbour distances. J. Appl. Prob. 19, 344–354.CrossRefGoogle Scholar
Henze, N. (1983). Ein asymptotischer Satz über den maximalen Minimalabstand von unabhängigen Zufallsvektoren mit Anwendungen auf einen Anpassungstest im ℝp und auf der Kugel. [An asymptotic theorem on the maximum minimum distance of independent random vectors, with application to a goodness-of-fit test in ℝp and on the sphere]. Metrika 30, 245–259 (in German).CrossRefGoogle Scholar
Rogers, C. A. (1963). Covering a sphere with spheres. Mathematika 10, 157–164.CrossRefGoogle Scholar