betaFeedback

WorksMathematics

Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests

Abstract

Given a graph sequence {Gn}n∈N\{G_n\}_{n\in\mathbb{N}}, denote by TnT_n the number of monochromatic edges when the vertices of GnG_n are independently colored red or blue with probabilities pp and 1−p1-p, respectively. We characterize the asymptotic normality of TnT_n, after centering and scaling to unit variance, in terms of subgraph (motif) counts and standardized moments. One of the highlights of our results is a third moment phenomenon: for every fixed p∈(0,1)\{12}p\in(0,1)\backslash\{\frac12\}, asymptotic normality holds if and only if the standardized third moment converges to zero. The more familiar fourth moment condition, which requires the standardized fourth moment to converge to 33, gives an equivalent characterization except at the two exceptional probabilities p=1±1/32p=\frac{1\pm1/\sqrt3}{2}. At these values, the standardized fourth moment converges to 33 for every graph sequence with a diverging number of edges, even when Gaussian convergence fails. In contrast, in the balanced case p=12p=\frac12, the fourth moment condition characterizes asymptotic normality, while the third moment condition is insufficient. These results identify three distinct regimes for moment characterizations of Gaussian convergence, determined by the coloring probability. We further show that the third moment condition remains sufficient in the sparse regime, where p=pn→0p=p_n \to 0. As an application, we derive the limiting null distribution of two-sample statistics based on undirected KK-nearest-neighbor graphs in the Poissonized setting, identifying sharp growth conditions on KK for asymptotic normality.

Introduction

Let {Gn}n∈N\{G_n\}_{n\in\mathbb{N}} be a sequence of simple, undirected graphs with vertex set [n]:={1,…,n}[n]:=\{1,\ldots,n\} and edge set E(Gn)E(G_n). Suppose the vertices of GnG_n are independently colored red with probability p∈(0,1)p\in(0,1) and blue with probability 1−p1-p. Let TnT_n be the number of monochromatic edges in E(Gn)E(G_n) and UnU_n be its standardized version. Despite being elementary the statistic UnU_n exhibits a rich range of limiting behaviors and arises in a wide range of problems across combinatorial probability and statistical inference. In the balanced (uniform) case p=12p=\frac{1}{2}, it can be expressed as a second-order Rademacher chaos, that is, a quadratic form in independent Rademacher variables (see (11)). This is a prototypical example of a degenerate UU-statistic of order two [17, 30, 35], which arises in many contexts, such as the Hamiltonian of Ising models [2, 11], tests of independence in autoregressive models [3], and Ramsey theory [1, 34]. The unbalanced (biased) case p≠12p \ne\frac{1}{2} also arises naturally in nonparametric two-sample testing based on geometric graphs (see § 1.3 for details) and in motif estimation problems [7, 33].

Since the statistic UnU_n is a sum of locally dependent indicators (see (2)), sufficient conditions for its asymptotic normality can be obtained using standard versions of Stein’s method or other normal approximation techniques. Identifying necessary and sufficient conditions, however, is considerably more delicate. For graph sequences with ∣E(Gn)∣→∞|E(G_n)| \to\infty, asymptotic normality in the balanced case p=12p = \frac{1}{2} is characterized by a fourth moment phenomenon [6, 9]:

Un→DN(0,1)if and only ifE[Un4]→3.U_n \xrightarrow{D} N(0,1) \quad\text{if and only if} \quad\mathbb{E}\left[U_n^4\right] \to3.

The unbalanced case, despite its practical relevance, has received considerably less attention.

In this paper, we develop a general framework for characterizing the asymptotic normality of UnU_n for every fixed p∈(0,1)p \in(0,1) and providing sufficient conditions in the regime when p=pn→0p = p_n \to0. Our results reveal a new third moment phenomenon: for every fixed p≠12p \ne\frac{1}{2}, asymptotic normality is equivalent to E[Un3]→0\mathbb{E}\left[U_n^3\right] \to0. A particularly striking feature is the emergence of the two exceptional probabilities p=1±1/32p = \frac{1 \pm1/\sqrt{3}}{2}. At these values, the fourth moment converges to its Gaussian value even when asymptotic normality fails (see Example 6.1), whereas the third moment continues to characterize Gaussian convergence. Outside these exceptional values, the fourth moment condition also characterizes asymptotic normality (see Theorem 1.1). At p=12p = \frac{1}{2}, (see Example 6.2), we provide an example to show that the third moment condition is insufficient. In the sparse regime, (see Proposition 1.3, Theorem 1.2, Example 6.3 and Example 6.4), where p=pn→0p = p_n \to0, as n→∞n \to\infty we show that the third moment condition is sufficient for asymptotic normality of UnU_n. Interestingly, the third moment condition is strictly weaker than the fourth moment condition in this regime, although neither is necessary for asymptotic normality. In addition for the fixed pp regime we provide necessary and sufficient conditions in terms of motif counts for the third and fourth moment phenomena to hold (see Theorem 1.1). We establish a similar result for the sparse regime, prescribing a sufficient decay rate of pnp_n in terms of motif counts (see Lemma 1.4).

Next, using the above results we derive the asymptotic null distribution of two-sample tests based on undirected KK-nearest-neighbor (KK-NN) graphs in the Poissonized setting. Allowing KK to grow with the sample size has been often recommended to improve power for graph-based nonparametric tests [4, 13]. Our results provide sharp general growth conditions that justify normal calibration in this regime. Specifically, we show that under the null hypothesis, the test statistic is asymptotically normal for arbitrary KK when the limiting sample proportions are unequal, and for K=o(n)K = o(n) when the sample sizes are equal (see Theorem 1.6 for precise statement). The same framework also gives conditions for asymptotic normality of two-sample edge-count statistics based on general similarity graphs.

The rest of the introduction is organized as follows. In § 1.1 we define the model and statistics precisely and state our main results on the third and fourth moment phenomena for monochromatic edges. We then show asymptotic properties of graph based two-sample tests in § 1.3. We conclude in § 1.4 by discussing the novelty and significance of our main results in relation to the existing literature and outlining the proofs of these results.

Third and Fourth Moment Phenomena for Monochromatic Edges

Let {Gn}n∈N\{G_n\}_{n\in\mathbb{N}} be a sequence of simple, undirected graphs with vertex set [n]:={1,…,n}[n] := \{1,\ldots,n\} and edge set E(Gn)E(G_n). Let dGn(i)d_{G_n}(i) will be the degree of the ii-th vertex of GnG_n, for 1≤i≤n1 \le i \le n. Suppose the vertices of GnG_n are independently colored red with probability p∈(0,1)p \in(0,1) and blue with probability 1−p1-p. For 1≤i≤n1 \le i \le n, denote by XiX_i the color of the vertex ii, with Xi=1X_i = 1 for red and Xi=0X_i = 0 for blue. Our object of interest in this paper is the number of monochromatic edges in GnG_n, that is,

Tn:=∑{i,j}∈E(Gn)1{Xi=Xj}.(1)T_n := \sum_{\{i,j\}\in E(G_n)} \mathbf{1}\{X_i = X_j\}. \tag*{(1)}

Denote the centered and rescaled version of TnT_n by:

Un:=Tn−E[Tn]Var⁡[Tn].(2)U_n := \frac{T_n-\mathbb{E}[T_n]}{\sqrt{\operatorname{Var}[T_n]}}. \tag*{(2)}

Throughout, for a finite graph HH (a motif), we will denote by N(H,Gn)N(H,G_n) the number of copies of HH in GnG_n. We will use pictograms for the motifs, so for instance N(edge motif,Gn)N(\text{edge motif},G_n) will denote the number of edges in GnG_n and N(4-cycle motif,Gn)N(\text{4-cycle motif},G_n) will denote the number of 4-cycles on GnG_n. Recall that XiX_i is the color of the vertex ii, for 1≤i≤n1 \le i \le n. Hence,

E[1{Xi=Xj}]=p2+(1−p)2=12(1+u),\mathbb{E}[\mathbf{1}\{X_i=X_j\}]=p^2+(1-p)^2=\frac{1}{2}(1+u),

where u:=(2p−1)2∈[0,1)u:=(2p-1)^2\in[0,1). Then, from (1),

E[Tn]=12(1+u)N(edge motif,Gn).\mathbb{E}[T_n]=\frac{1}{2}(1+u)N(\text{edge motif},G_n).

Further, since the indicators of a pair of edges being monochromatic are independent when the edges are disjoint, a direct computation gives,

Var⁡[Tn]=1−u24N(edge motif,Gn)+u−u22N(wedge motif,Gn).(3)\operatorname{Var}[T_n]=\frac{1-u^2}{4}N(\text{edge motif},G_n)+\frac{u-u^2}{2}N(\text{wedge motif},G_n). \tag*{(3)}

Note that the second term in (3) vanishes when u=0u=0, that is, p=12p=\frac{1}{2}. Consequently, the leading order of the variance changes depending on whether or not p=12p=\frac{1}{2}. This dichotomy is reflected throughout our results, with the balanced case often exhibiting different asymptotic behavior.

For two positive sequences {an}n∈N\{a_n\}_{n\in\mathbb{N}} and {bn}n∈N\{b_n\}_{n\in\mathbb{N}} we write an=o(bn)a_n=o(b_n) if an/bn→0a_n/b_n\to0, an=O(bn)a_n=O(b_n) if an/bna_n/b_n is bounded, and an≍bna_n\asymp b_n if both an=O(bn)a_n=O(b_n) and bn=O(an)b_n=O(a_n). All asymptotics are taken as n→∞n\to\infty. We separate our results on the asymptotic normality of UnU_n in two regimes: the fixed pp regime, in which p∈(0,1)p\in(0,1) is a fixed constant, and the sparse regime, in which p=pn→0p=p_n\to0, as n→∞n\to\infty.

The Fixed pp Regime: The following theorem characterizes the asymptotic normality of UnU_n in terms of its third and fourth moments and the growth rates of certain motif counts, when the coloring probability p∈(0,1)p\in(0,1) is fixed..

References

  1. [1]P. Balister, E. Powierski, A. Scott, and J. Tan. A local limit theorem for the edge counts of random induced subgraphs of a random graph. arXiv:2503.23164, 2025.arxiv.org/abs/2503.23164
  2. [2]A. Basak and S. Mukherjee. Universality of the mean-field for the Potts model. Probability Theory and Related Fields, 168(3–4):557–600, 2017.arxiv.org/abs/1508.03949
  3. [3]R. J. Beran. Rank spectral processes and tests for serial dependence. The Annals of Mathematical Statistics, 43(6):1749–1766, 1972.DOI
  4. [4]B. B. Bhattacharya. A general asymptotic framework for distribution-free graph-based two-sample tests. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 81(3):575–602, 2019.arxiv.org/abs/1508.07530
  5. [5]B. B. Bhattacharya. Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs. The Annals of Statistics, 48(5):2879–2903, 2020.arxiv.org/abs/1512.00384
  6. [6]B. B. Bhattacharya, P. Diaconis, and S. Mukherjee. Universal limit theorems in graph coloring problems with connections to extremal combinatorics. The Annals of Applied Probability, 27(1):337–394, 2017.arxiv.org/abs/1310.2336
  7. [7]B. B. Bhattacharya, S. Das, and S. Mukherjee. Motif estimation via subgraph sampling: The fourth-moment phenomenon. The Annals of Statistics, 50(2):987–1011, 2022.DOI
  8. [8]B. B. Bhattacharya, X. Fang, and H. Yan. Normal approximation and fourth moment theorems for monochromatic triangles. Random Structures & Algorithms, 60(1):25–53, 2022.arxiv.org/abs/2004.05732
  9. [9]B. B. Bhattacharya, S. Das, S. Mukherjee, and S. Mukherjee. Fluctuations of quadratic chaos. Communications in Mathematical Physics, 405(10):237, 2024.DOI
  10. [10]S. G. Bobkov, G. P. Chistyakov, and F. Götze. Regularized distributions and entropic stability of Cramer’s characterization of the normal law. Stochastic Processes and their Applications, 126 (12):3865–3887, 2016. Extended version available as arXiv:1504.02961.DOI
  11. [11]S. Chatterjee. Estimation in spin glasses: A first step. The Annals of Statistics, 35(5):1931–1946, 2007.DOI
  12. [12]S. Chatterjee. A new method of normal approximation. The Annals of Probability, 36(4):1584–1610, 2008.DOI
  13. [13]H. Chen and J. H. Friedman. A new graph-based two-sample test for multivariate and object data. Journal of the American Statistical Association, 112(517):397–409, 2017.DOI
  14. [14]S. Das, Z. Himwich, and N. Mani. A fourth-moment phenomenon for asymptotic normality of monochromatic subgraphs. Random Structures & Algorithms, 63(4):968–996, 2023.DOI
  15. [15]P. de Jong. A central limit theorem for generalized quadratic forms. Probability Theory and Related Fields, 75(2):261–277, 1987.DOI
  16. [16]P. de Jong. A central limit theorem for generalized multilinear forms. Journal of Multivariate Analysis, 34(2):275–289, 1990.DOI
  17. [17]V. H. de la Peña and E. Giné. Decoupling: From Dependence to Independence. Probability and Its Applications. Springer, New York, first edition, 2012.
  18. [18]C. Döbler. New bounds for normal approximation on product spaces with applications to monochromatic edges, random sums and an infinite de Jong CLT. arXiv:2403.14334, 2024.arxiv.org/abs/2403.14334
  19. [19]C. Döbler and K. Krokowski. On the fourth moment condition for Rademacher chaos. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55(1):61–97, 2019.arxiv.org/abs/1706.00751
  20. [20]B. Efron and C. Stein. The jackknife estimate of variance. The Annals of Statistics, 9(3):586–596, 1981.
  21. [21]X. Fang. A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs. Electronic Communications in Probability, 20:1–6, 2015. Article 21.arxiv.org/abs/1408.0509
  22. [22]J. H. Friedman and L. C. Rafsky. Multivariate generalizations of the Wald–Wolfowitz and Smirnov two-sample tests. The Annals of Statistics, 7(4):697–717, 1979.DOI
  23. [23]F. Götze and A. N. Tikhomirov. Asymptotic distribution of quadratic forms. The Annals of Probability, 27(2):1072–1098, 1999.DOI
  24. [24]F. Götze and A. N. Tikhomirov. Asymptotic distribution of quadratic forms and applications. Journal of Theoretical Probability, 15(2):423–475, 2002.DOI
  25. [25]L. Györfi and T. Nemetz. f-dissimilarity: A general class of separation measures of several probability measures. In I. Csiszár and P. Elias, editors, Topics in Information Theory, volume 16 of Colloquia Mathematica Societatis János Bolyai, pages 309–321, Amsterdam, 1977. North-Holland. Second Colloquium, Keszthely, Hungary, 1975.
  26. [26]L. Györfi, M. Kohler, A. Krzyżak, and H. Walk. A Distribution-Free Theory of Nonparametric Regression. Springer Series in Statistics. Springer-Verlag, New York, 2002.
  27. [27]P. Hall. Central limit theorem for integrated square error of multivariate nonparametric density estimators. Journal of Multivariate Analysis, 14(1):1–16, 1984.DOI
  28. [28]N. Henze and M. D. Penrose. On the multivariate runs test. The Annals of Statistics, 27(1):290–298, 1999.DOI
  29. [29]Z. Huang and B. Sen. A kernel measure of dissimilarity between M distributions. Journal of the American Statistical Association, 119(548):3020–3032, 2024.arxiv.org/abs/2210.00634
  30. [30]S. Janson. Gaussian Hilbert Spaces, volume 129 of Cambridge Tracts in Mathematics. Cambridge University Press, 1997.DOI
  31. [31]R. R. Kanekar. Power properties of the two sample test based on the nearest neighbors graph. The Annals of Statistics, 54(5):2560–2585, 2026.arxiv.org/abs/2504.10719
  32. [32]Y. T. Kim and H. S. Park. The optimal third moment theorem. Journal of the Korean Statistical Society, 48(4):636–658, 2019.DOI
  33. [33]J. M. Klusowski and Y. Wu. Counting motifs with graph sampling. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 1966–2011. PMLR, 2018.arxiv.org/abs/1802.07773
  34. [34]M. Kwan, A. Sah, L. Sauermann, and M. Sawhney. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi, 11:e21, 2023. Article e21.DOI
  35. [35]A. J. Lee. U-Statistics: Theory and Practice. Marcel Dekker, New York, 1990.
  36. [36]L. Lovász. Large Networks and Graph Limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, 2012.DOI
  37. [37]N. Mani and D. Mikulincer. Characterizing the fourth-moment phenomenon of monochromatic subgraph counts via influences. The Annals of Applied Probability, 36(1):744–775, 2026.arxiv.org/abs/2403.14068
  38. [38]L. Neufcourt and F. G. Viens. A third-moment theorem and precise asymptotics for variations of stationary Gaussian sequences. ALEA. Latin American Journal of Probability and Mathematical Statistics, 13(1):239–264, 2016.arxiv.org/abs/1603.00365
  39. [39]I. Nourdin and G. Peccati. Stein’s method on Wiener chaos. Probability Theory and Related Fields, 145(1–2):75–118, 2009.arxiv.org/abs/0712.2940
  40. [40]I. Nourdin and G. Peccati. Normal Approximations with Malliavin Calculus: From Stein’s Method to Universality, volume 192 of Cambridge Tracts in Mathematics. Cambridge University Press, 2012.DOI
  41. [41]I. Nourdin and G. Peccati. The optimal fourth moment theorem. Proceedings of the American Mathematical Society, 143(7):3123–3133, 2015.arxiv.org/abs/1305.1527
  42. [42]I. Nourdin, G. Peccati, and G. Reinert. Stein’s method and stochastic analysis of Rademacher functionals. Electronic Journal of Probability, 15:55, 2010.arxiv.org/abs/0810.2890
  43. [43]D. Nualart and G. Peccati. Central limit theorems for sequences of multiple stochastic integrals. The Annals of Probability, 33(1):177–193, 2005.DOI
  44. [44]M. D. Penrose. Random Geometric Graphs, volume 5 of Oxford Studies in Probability. Oxford University Press, Oxford, 2003.
  45. [45]M. D. Penrose and J. E. Yukich. Weak laws of large numbers in geometric probability. The Annals of Applied Probability, 13(1):277–303, 2003.DOI
  46. [46]P. R. Rosenbaum. An exact distribution-free test comparing two multivariate distributions based on adjacency. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(4):515–530, 2005.DOI
  47. [48]V. I. Rotar’. Some limit theorems for polynomials of second degree. Theory of Probability and Its Applications, 18(3):499–507, 1974.DOI
  48. [49]M. F. Schilling. Multivariate two-sample tests based on nearest neighbors. Journal of the American Statistical Association, 81(395):799–806, 1986.DOI
  49. [50]C. J. Stone. Consistent nonparametric regression. The Annals of Statistics, 5(4):595–620, 1977.
  50. [51]D. Zhou and H. Chen. A new ranking scheme for modern data and its application to two-sample hypothesis testing. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 3615–3668. PMLR, 2023.
  51. [52]Y. Zhu and H. Chen. Limiting distributions of graph-based test statistics on sparse and dense graphs. Bernoulli, 30(1):770–796, 2024.DOI

Paper details

vlnc:W_pkwrbfkx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Fable 5.1 (bare), GPT-5.6 Sol (bare), GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents