Normal approximation for sums of weighted U-statistics -- application to Kolmogorov bounds in random subgraph counting

DOI10.3150/19-BEJ1141MaRDI QIDQ2278673zbMATH OpenOpenAlexFDO

Authors Nicolas Privault, Grzegorz Serafin

Publication date 5 December 2019

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.05339, https://projecteuclid.org/euclid.bj/1574758839

Berry-Esseen bound central limit theorem Kolmogorov distance Malliavin-Stein method normal approximation random graph Stein-Chen method subgraph count

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Central limit and other weak theorems (60F05) Stochastic calculus of variations and the Malliavin calculus (60H07)

Abstract: We derive normal approximation bounds in the Kolmogorov distance for sums of discrete multiple integrals and

U

-statistics made of independent Bernoulli random variables. Such bounds are applied to normal approximation for the renormalized subgraphs counts in the Erd{H o}s-R'enyi random graph. This approach completely solves a long-standing conjecture in the general setting of arbitrary graph counting, while recovering and improving recent results derived for triangles as well as results using the Wasserstein distance.

Review text

The first author and \textit{G. L. Torrisi} [ALEA, Lat. Am. J. Probab. Math. Stat. 12, No. 1, 309--356 (2015; Zbl 1329.60079)] derived Stein bouds in the Wasserstein distance for functionals of not necessarily symmetric Bernoulli sequences, and \textit{K. Krokowski} et al. [Ann. Inst. Henri Poincaré, Probab. Stat. 52, No. 2, 763--803 (2016; Zbl 1341.60005)] obtained Kolmogorov distance bounds via second order Poincaré inequalities for the discrete not necessarily symmetric Bernoulli sequences. The paper under review derives a new Kolmogorov distance bound to normal distribution for the distribution of functionals of discrete multiple stochastic integrals (sums of weighted U-statistics) by the Malliavin approach to the Stein and Stein-Chen methods. The authors of the reviewed article further apply the main result Theorem 3.1 to normal approximation of the renormalized count of the subgraphs which are isomorphic to an arbitrary graph in the Erdős-Rényi random graph \(G_n(p)\) for \(n\) vertices and a probability \(p\in (0, 1)\). Section 2 sets the notation and results of the stochastic analysis of Bernoulli processes \(X_n\) (i.i.d with \(P(X_n=1)=p\) and \(P(X_n=-1)=q\)). Proposition 2.1 follows from Theorem 3.1 of [Krokowski et al., loc. cit.] to obtain the Kolmogorov distance bound on the form of discrete multiple stochastic integral of order \(n\), and Proposition 2.2 gives a bound on symmetrization similar to \(2ab \le a^2 + b^2\). Section 3 presents the Kolmogorov distance bound on discrete multiple stochastic integrals with components in the inequality from Proposition 2.1 and estimates of Proposition 2.2 in the similar manner of the proof of Theorem 4.2 in [loc. cit.]. The whole proof occupies the whole section of Theorem 3.1 with the Kolmogorov distance bound by variation of the discrete multiple stochastic integrals and its monomials with symmetrizations. Section 4 directly applies result in Section 3 to random graphs. The second main result is to have the Kolmogorov distance bound on a sum of multiple stochastic integrals with Bernoulli variables, by Theorem 3.1, and specify the symmetrizations. Special cases are discussed too. It would be nice and helpful to have intuitive explanations in the proofs of main Theorem 3.1 and Theorem 4.2.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Normal approximation for sums of weighted \(U\)-statistics -- application to Kolmogorov bounds in random subgraph counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2278673)