On the number of reflexive and shared nearest neighbor pairs in one-dimensional uniform data

• Autorzy: Bahadir S. , Ceyhan E.

Identyfikatory

DOI

10.19195/0208-4147.38.1.7

• Języki publikacji: EN

Abstrakty

EN

For a random sample of points in R, we consider the number, of pairs whose members are nearest neighbors (NNs) to each other and the, number of pairs sharing a common NN. The pairs of the first type are called, reflexive NNs, whereas the pairs of the latter type are called shared NNs. In, this article, we consider the case where the random sample of size n is from, the uniform distribution on an interval. We denote the number of reflexive NN pairs and the number of shared NN pairs in the sample by R_n and Q_n, respectively. We derive the exact forms of the expected value and the variance for both R_n and Q_n, and derive a recurrence relation for R_n which may also be used to compute the exact probability mass function (pmf) of R_n. Our approach is a novel method for finding the pmf of R_n and agrees with the results in the literature. We also present SLLN and CLT results for both R_n and Q_n as n goes to infinity.

Słowa kluczowe

EN

asymptotic normality; central limit theorem; exact distribution; law of large numbers; nearest neighbor graphs; nearest neighbor digraphs; random permutation

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2018
• Tom: Vol. 38, Fasc. 1
• Strony: 123--137
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Bahadir S.

• Department of Mathematics and Computer Science, Yıldırım Beyazıt University, Ankara, 06010, Turkey

autor

Ceyhan E.

• Department of Statistics, University of Pittsburgh, Pittsburgh, PA, 15260, USA

Bibliografia

• [1] P. J. Bickel and L. Breiman, Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test, Ann. Probab. 11 (1) (1983), pp. 185-214.
• [2] M. R. Brito, A. J. Quiroz, and J. E. Yukich, Intrinsic dimension identification via graph-theoretic methods, J. Multivariate Anal. 116 (2013), pp. 263-277.
• [3] E. Ceyhan, Overall and pairwise segregation tests based on nearest neighbor contingency tables, Comput. Statist. Data Anal. 53 (8) (2008), pp. 2786-2808.
• [4] E. Ceyhan, Testing spatial symmetry using contingency tables based on nearest neighbor relations, Sci. World J. (2014), Article ID 698296.
• [5] G. Chartrand and L. Lesniak, Graphs & Digraphs, Chapman & Hall/CRC, Boca Raton 1996.
• [6] K. L. Chung, A Course in Probability Theory, Academic Press, New York 1974.
• [7] P. J. Clark and F. C. Evans, Distance to nearest neighbor as a measure of spatial relationships in populations, Ecology 35 (4) (1954), pp. 445-453.
• [8] P. J. Clark and F. C. Evans, On some aspects of spatial pattern in biological populations, Science 121 (1955), pp. 397-398.
• [9] T. F. Cox, Reflexive nearest neighbors, Biometrics 37 (2) (1981), pp. 367-369.
• [10] M. F. Dacey, The spacing of river towns, Ann. Assoc. Am. Geogr. 50 (1) (1960), pp. 59-61.
• [11] P. M. Dixon, Testing spatial segregation using a nearest-neighbor contingency table, Ecology 75 (7) (1994), pp. 1940-1948.
• [12] E. G. Enns, P. F. Ehlers, and T. Misi, A cluster problem as defined by nearest neighbours, Canad. J. Statist. 27 (4) (1999), pp. 843-851.
• [13] D. Eppstein, M. S. Paterson, and F. F. Yao, On nearest-neighbor graphs, Discrete Comput. Geom. 17 (3) (1997), pp. 263-282.
• [14] J. H. Friedman and L. C. Rafsky, Graph-theoretic measures of multivariate association and prediction, Ann. Statist. 11 (2) (1983), pp. 377-391.
• [15] N. Henze, On the fraction of random points with specified nearest-neighbour interactions and degree of attraction, Adv. in Appl. Probab. 19 (4) (1987), pp. 873-895.
• [16] W. Hoeffding, A class of statistics with asymptotically normal distribution, Ann. Math. Statist. 19 (3) (1948), pp. 293-325.
• [17] W. Hoeffding and H. Robbins, The central limit theorem for dependent random variables, Duke Math. J. 17 (1948), pp. 773-780.
• [18] C. Houdré and R. Restrepo, A probabilistic approach to the asymptotics of the length of the longest alternating subsequence, Electron. J. Combin. 17 (1) (2010), Research paper 168.
• [19] T. Kozakova, R. Meester, and S. Nanda, The size of components in continuum nearest-neighbor graphs, Ann. Probab. 34 (2) (2006), pp. 528-538.
• [20] C. M. Newman, Y. Rinott, and A. Tversky, Nearest neighbors and Voronoi regions in certain point processes, Adv. in Appl. Probab. 15 (4) (1983), pp. 726-751.
• [21] M. D. Penrose and J. E. Yukich, Central limit theorems for some graphs in computational geometry, Ann. Appl. Probab. 11 (4) (2001), pp. 1005-1041.
• [22] D. K. Pickard, Isolated nearest neighbors, J. Appl. Probab. 19 (2) (1982), pp. 444-449.
• [23] D. A. Pinder and M. E. Witherick, A modification of nearest-neighbour analysis for use in linear situations, Geography 60 (1) (1975), pp. 16-23.
• [24] D. Romik, Local extrema in random permutations and the structure of longest alternating subsequences, Discrete Math. Theor. Comput. Sci. Proc. AO (FPSAC 2011), pp. 825-834.
• [25] M. F. Schilling, Mutual and shared neighbor probabilities: Finite- and infinite-dimensional results, Adv. in Appl. Probab. 18 (2) (1986), pp. 388-405.
• [26] R. P. Stanley, Longest alternating subsequences of permutations, Michigan Math. J. 57 (2009), pp. 675-687.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).