Kolmogorov bounds for decomposable random variables and subgraph counting by the Stein–Tikhomirov method
Peter Eichelsbacher, Benedikt Rednoß
Abstract
We derive normal approximation bounds in the Kolmogorov distance for random variables possessing decompositions of Barbour, Karoński, and Ruciński (J. Combin. Theory Ser. B 47 (1989) 125–145). We highlight the example of standardized subgraph counts in the Erdős–Rényi random graph. We prove a bound by generalizing the argumentation of Röllin (Probab. Engrg. Inform. Sci. (2022) 747–773), who used the Stein–Tikhomirov method to prove a bound in the special case of standardized triangle counts. Our bounds match the best available Wasserstein bounds.
Topics & Concepts
MathematicsCombinatoricsRandom graphUpper and lower boundsDiscrete mathematicsGraphRandom variableStatisticsMathematical analysisRandom Matrices and ApplicationsLimits and Structures in Graph TheoryPoint processes and geometric inequalities