Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings

DOI10.1016/J.SPL.2011.06.002zbMATH Open1226.05227arXiv1106.0048OpenAlexW2142748559MaRDI QIDQ643216FDOQ643216

Authors: Subhankar Ghosh, Larry Goldstein, Martin Raič 

Publication date: 28 October 2011

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Abstract: A concentration of measure result is proved for the number of isolated vertices $Y$ in the ErdH{o}s-R'{e}nyi random graph model on $n$ edges with edge probability $p$. When $mu$ and $sigm{a}^2$ denote the mean and variance of $Y$ respectively, $P((Y-mu)/sigmaget)$ admits a bound of the form $e^{-k{t}^2}$ for some constant positive $k$ under the assumption $pin(0,1)$ and $npightarrowcin(0,infty)$ as $nightarrowinfty$. The left tail inequality ${\displaystyle }$ P(frac{Y-mu}{sigma}le -t)&le& exp(-frac{t^2sigma^2}{4mu}) ${\displaystyle }$ holds for all $nin2,3,\mathrm{...},pin(0,1)$ and $tge0$. The results are shown by coupling $Y$ to a random variable $Y^s$ having the $Y$-size biased distribution, that is, the distribution characterized by $E[Yf(Y)]=muE[f(Y^s)]$ for all functions $f$ for which these expectations exist.

Full work available at URL: https://arxiv.org/abs/1106.0048

Recommendations

• Concentration of the spectral norm of Erdős-Rényi random graphs
• scientific article; zbMATH DE number 17671
• Concentration of the Kirchhoff index for Erdős-Rényi graphs
• On the number of isolated vertices in a growing random graph
• On large deviation properties of Erdős-Rényi random graphs
• On the concentration of the domination number of the random graph
• A Berry-Esseen bound with applications to vertex degree counts in the Erdős-Rényi random graph
• On the concentration of the independence numbers of random hypergraphs
• Concentration of vertex degrees in a scale‐free random graph process
• scientific article; zbMATH DE number 5369609

zbMATH Keywords

large deviationssize biased couplingsgraph degree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Poisson convergence and semi-induced properties of random graphs
• Multivariate normal approximations by Stein's method and size bias couplings
• Title not available (Why is that?)
• Some large deviation results for sparse random graphs
• A central limit theorem for decomposable random variables with applications to random graphs
• Poisson convergence and random graphs
• CLT-related large deviation bounds based on Stein's method
• Title not available (Why is that?)
• Applications of size biased couplings for concentration of measures
• Concentration of measures via size-biased couplings
• Normal approximation for coverage models over binomial point processes
• On the number of vertices of given degree in a random graph
• Title not available (Why is that?)

Cited In (7)

• Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models
• Weighted Poincaré inequalities, concentration inequalities and tail bounds related to Stein kernels in dimension one
• Concentration of measures via size-biased couplings
• Title not available (Why is that?)
• Size biased couplings and the spectral gap for random regular graphs
• A Berry-Esseen bound with applications to vertex degree counts in the Erdős-Rényi random graph
• Central moment inequalities using Stein's method

This page was built for publication: Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings

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