Mathematics – Probability
Scientific paper
2011-05-31
Mathematics
Probability
7 pages. Corrected treatment of the concentration phenomenon for the number of isolated vertices application that appeared in
Scientific paper
A concentration of measure result is proved for the number of isolated vertices $Y$ in the Erd\H{o}s-R\'{e}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^{-kt^2}$ for some constant positive $k$ under the assumption $p \in (0,1)$ and $np\rightarrow c \in (0,\infty)$ as $n \rightarrow \infty$. The left tail inequality $$ P(\frac{Y-\mu}{\sigma}\le -t)&\le& \exp(-\frac{t^2\sigma^2}{4\mu}) $$ 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.
Ghosh Subhankar
Goldstein Larry
Raic Martin
No associations
LandOfFree
Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-324016