We prove a Law of Large Numbers (LLN) for the domination number of class cover catch digraphs (CCCD) generated by random points in two (or higher) dimensions. DeVinney and Wierman (2002) proved the Strong Law of Large Numbers (SLLN) for the uniform distribution in one dimension, and Wierman and Xiang (2008) extended the SLLN to the case of general distributions in one dimension. In this article, using subadditive processes, we prove a SLLN result for the domination number generated by Poisson points in ℝ2. From this we obtain a Weak Law of Large Numbers (WLLN) for the domination number generated by random points in [0, 1]2 from uniform distribution first, and then extend these result to the case of bounded continuous distributions. We also extend the results to higher dimensions. The domination number of CCCDs and related digraphs have applications in statistical pattern classification and spatial data analysis.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ps/2021013
Keywords: Pattern classification, class cover catch digraph, domination number, law of large numbers, subadditive process
@article{PS_2021__25_1_376_0,
author = {Ceyhan, Elvan and Wierman, John C. and Xiang, Pengfei},
title = {Law of large numbers for a two-dimensional class cover problem},
journal = {ESAIM: Probability and Statistics},
pages = {376--407},
year = {2021},
publisher = {EDP-Sciences},
volume = {25},
doi = {10.1051/ps/2021013},
mrnumber = {4291368},
zbl = {1489.60045},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ps/2021013/}
}
TY - JOUR AU - Ceyhan, Elvan AU - Wierman, John C. AU - Xiang, Pengfei TI - Law of large numbers for a two-dimensional class cover problem JO - ESAIM: Probability and Statistics PY - 2021 SP - 376 EP - 407 VL - 25 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ps/2021013/ DO - 10.1051/ps/2021013 LA - en ID - PS_2021__25_1_376_0 ER -
%0 Journal Article %A Ceyhan, Elvan %A Wierman, John C. %A Xiang, Pengfei %T Law of large numbers for a two-dimensional class cover problem %J ESAIM: Probability and Statistics %D 2021 %P 376-407 %V 25 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ps/2021013/ %R 10.1051/ps/2021013 %G en %F PS_2021__25_1_376_0
Ceyhan, Elvan; Wierman, John C.; Xiang, Pengfei. Law of large numbers for a two-dimensional class cover problem. ESAIM: Probability and Statistics, Tome 25 (2021), pp. 376-407. doi: 10.1051/ps/2021013
[1] and , Ergodic theorems for superadditive processes. Journal für die Reine und Angewandte Mathematik 323 (1981) 53–67. | MR | Zbl
[2] , , , and , The domination number of on-line social networks and random geometric graphs. Theory and Applications of Models of Computation. TAMC 2015, edited by , and . In Vol. 9076 of Lecture Notes in Computer Science. Springer, Cham (2015). | MR | Zbl
[3] and , Approximation algorithms for the class cover problem. 6th International Symposium on Artificial Intelligence and Mathematics (2000). | Zbl
[4] and , The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association. Stat. Prob. Lett. 73 (2005) 37–50. | MR | Zbl | DOI
[5] , Extension of one-dimensional proximity regions to higher dimensions. Comp. Geom.-Theor. Appl. 43 (2010) 721–748. | MR | Zbl | DOI
[6] , Spatial clustering tests based on domination number of a new family of random digraphs. Commun. Stat. A-Ther. 40 (2011) 1363–1395. | MR | Zbl | DOI
[7] , Comparison of relative density of two random geometric digraph families in testing spatial clustering. TEST 23 (2014) 100–134. | MR | Zbl | DOI
[8] , The Class Cover Problem and its Applications in Pattern Recognition, Ph.D. dissertation, Johns Hopkins University (2003). | MR
[9] and , A new family of proximity graphs: class cover catch digraphs. Disc. Appl. Math. 154 (2006) 1975–1982. | MR | Zbl | DOI
[10] and , A SLLN for a one-dimensional class cover problem. Stat. Prob. Lett. 59 (2002) 425–435. | MR | Zbl | DOI
[11] , Stochastic Processes. Chapman & Hall, London (1953). | MR
[12] , , and , A hierarchical methodology for one-class problems with skewed priors. J. Classif . 22 (2005) 17–48. | MR | Zbl | DOI
[13] , The secrecy graph and some of its properties. IEEE International Symposium on Information Theory (ISIT’08). Toronto, Canada (2008) 539–543. | DOI
[14] and , First-passage percolation, subadditive processes, stochastic networks and generalized renewal theory, in Bernoulli-Bayes-Laplace Anniversary Volume, edited by and . Proceedings International Research Seminar, Statistical Laboratory, University of California, Berkeley. Springer Verlag (1965). | MR | Zbl
[15] , and , Domination in Graphs, Fundamentals. Marcel Dekker, Inc., New York (1998). | MR | Zbl
[16] , The ergodic theory of subadditive stochastic processes. J. R. Statist. Soc., Ser. B 30 (1968) 499–510. | MR | Zbl
[17] , Subadditive ergodic theory. Ann. Probab. 1 (1973) 883–909. | MR | Zbl
[18] , and , Learning pattern classification – a survey. IEEE Trans. Info. Theory 44 (1998) 2178–2206. | MR | Zbl | DOI
[19] and , Characterizing the scale dimension of a high-dimensional classification problem. Pattern Recogn. 36 (2003) 45–60. | Zbl | DOI
[20] and , Classification of imbalanced data with a geometric digraph family. J. Mach. Learn. Res. 17 (2016) 1–40. | MR | Zbl
[21] , Theory of Graphs. American Mathematical Society, Providence, R.I. (1962). | MR | Zbl
[22] and , Weak laws of large numbers in geometric probability. Ann. Appl. Probab. 13 (1993) 277–303. | MR | Zbl
[23] , , and , Classification using class cover catch digraphs. J. Classif . 20 (2003) 3–23. | MR | Zbl | DOI
[24] , , and , Class cover catch digraphs for latent class discovery in gene expression monitoring by DNA microarrays. Comp. Stat. Data An. on Visualization 43 (2003) 621–632. | MR | Zbl | DOI
[25] , A matching problem and subadditive Euclidean functionals. Ann. Appl. Probab. 3 (1993) 794–801. | MR | Zbl
[26] and A.H. Nandhu Kishore, Applications of dominating set of graph in computer networks. Int. J. Eng. Sci. Res. Technol. 3 (2014) 170–173.
[27] and , Percolation in the secrecy graph. Discr. Appl. Math. 161 (2013) 2120–2132. | MR | Zbl | DOI
[28] , Multiparameter subadditive processes. Ann. Prob. 4 (1976) 772–782. | MR | Zbl | DOI
[29] and , First-passage Percolation on the Square Lattice. Vol. 671 of Lect. Notes Math. (1978). | MR | Zbl
[30] , Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab. 4 (1981) 365–376. | MR | Zbl
[31] and , A general SLLN for a one-dimensional class cover problem. Stat. Prob. Lett. 78 (2008) 1110–1118. | MR | Zbl | DOI
[32] and , A CLT for a one-dimensional class cover problem. Stat. Prob. Lett. 79 (2009) 223–233. | MR | Zbl | DOI
[33] , Limit theorems in discrete stochastic geometry, Stochastic Geometry, Spatial Statistics and Random Fields, edited by . In Vol. 2068 of Lecture Notes in Mathematics. Springer, Berlin, Heidelberg (2013). | MR | Zbl | DOI
[34] , and , The algorithmic complexity of mixed domination in graphs. Theor. Comput. Sci. 412 (2011) 2387–2392. | MR | Zbl | DOI
Cité par Sources :
