Timeline for Concentration inequalities for very rare events on a multiplicative scale

11 events

when toggle format	what		by	license	comment
Nov 14, 2020 at 8:05	comment	added	Harry West		There are a couple of inequalities for very large deviations stated in "Random Graphs" by Bollobás, Theorem 1.7. Maybe someone knows a more comprehensive reference.
Nov 13, 2020 at 17:28	vote	accept	Adam
Nov 13, 2020 at 17:28	vote	accept	Adam
Nov 13, 2020 at 17:28
Nov 13, 2020 at 14:53	comment	added	user44143		@IosifPinelis, agreed; since the question asks for information on the decay rate as $N\to\infty$, that seems the right place to start.
Nov 13, 2020 at 14:38	comment	added	Iosif Pinelis		@MattF. : The normal approximation to the binomial distribution works only if $npq$ is large, where $q:=1-p$. So, if $p=o(1/n)$ (say), then this approximation will not work.
Nov 13, 2020 at 9:59	comment	added	user44143		$NA_N$ is binomial, so roughly normal with mean $Np$ and variance $Np(1-p)$, and $A_N>\sqrt{p}$ is an event at $$\frac{N\sqrt{p}-Np}{\sqrt{Np(1-p)}}=\sqrt{N}\frac{1-\sqrt{p}}{\sqrt{1-p}}$$ standard deviations. This will be rare, and can be estimated using standard approximations for the normal distribution.
Nov 13, 2020 at 9:20	history	became hot network question
Nov 13, 2020 at 3:10	history	edited	Iosif Pinelis		edited tags
Nov 13, 2020 at 2:48	answer	added	Iosif Pinelis		timeline score: 7
Nov 13, 2020 at 1:10	review	First posts
Nov 13, 2020 at 2:31
Nov 13, 2020 at 1:10	history	asked	Adam	CC BY-SA 4.0