Bounds on Binomial Tails With Applications.

Novel bounds on the left- and right-tail probability of the Binomial distribution are presented. Specifically, bounds on the left-tail probability $\text {P}\!\left [{S_{n}\leqslant an}\right]$ with $a\in (0,p)$ and the right-tail probability $\text {P}\!\left [{S_{n}\geqslant an}\right]$ with $a\in (p,1)$ , where $S_{n}$ follows the Binomial law with parameters $n\geqslant 1$ and $p\in (0,1)$ , are derived. The bounds are tighter than the best known closed-form expressions. The presented upper and lower bounds on the right-tail match an asymptotic expansion of $\log \text {P}\!\left [{S_{n}\geqslant na}\right]$ up to, and including, the $\log n$ term. In particular, the ratio between the upper and lower bounds is $1/(1-c/n)$ , where $c$ is independent of $n$. Similar results are presented for the left-tail probability. Applications to finite blocklength source and channel coding are presented. [ABSTRACT FROM AUTHOR]