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

Abstract

A concentration of measure result is proved for the number of isolated vertices $Y$ in the Erdős-Rényi random graph model on $n$ edges with edge probability $p$. When $\mu$ and ${\sigma }^2$ denote the mean and variance of $Y$ respectively, $P((Y-\mu )/\sigma \ge t)$ admits a bound of the form $e^{-k{t}^2}$ for some constant positive $k$ under the assumption $p\in (0,1)$ and $np\to c\in (0,\infty )$ as $n\to \infty$. The left tail inequality $$ P(\frac{Y-μ}σ\le -t)&\le& \exp(-\frac{t^2σ^2}{4μ}) $$ holds for all $n\in 2,3,...,p\in (0,1)$ and $t\ge 0$. 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)]=\mu E[f(Y^s)]$ for all functions $f$ for which these expectations exist.

7 pages. Corrected treatment of the concentration phenomenon for the number of isolated vertices application that appeared in arXiv:0906.3886v1, now with Martin Raic