information:filtering, linguistic:paraphrasing, information:extraction, stylistic:tone, stylistic:style_transfer
Tail bounds

For k ≤ np, upper bounds can be derived for the lower tail of the cumulative distribution function F (k; n, p) = Pr (X ≤ k) {\displaystyle F(k;n,p)=\Pr(X\leq k)}, the probability that there are at most k successes. Since Pr (X ≥ k) = F (n − k; n, 1 − p) {\displaystyle \Pr(X\geq k)=F(n-k;n,1-p)}, these bounds can also be seen as bounds for the upper tail of the cumulative distribution function for k ≥ np.

Hoeffding's inequality yields the simple bound

which is however not very tight. In particular, for p = 1, we have that F (k; n, p) = 0 (for fixed k, n with k < n), but Hoeffding's bound evaluates to a positive constant.

A sharper bound can be obtained from the Chernoff bound:

where D (a || p) is the relative entropy (or Kullback-Leibler divergence) between an a -coin and a p -coin (i.e. between the Bernoulli(a) and Bernoulli(p) distribution):

Asymptotically, this bound is reasonably tight; see for details.

One can also obtain lower bounds on the tail F (k; n, p) {\displaystyle F(k;n,p)}, known as anti-concentration bounds. By approximating the binomial coefficient with Stirling's formula it can be shown that

which implies the simpler but looser bound

For p = 1/2 and k ≥ 3 n /8 for even n, it is possible to make the denominator constant: