Technical Report CS0911

Title: Optimal Bounds on Tail Probabilities - A Simplified Approach
Authors: A. Cohen, Y. Rabinovich, A. Schuster, and H. Shachnai
Abstract: Let $\{ X_i \}_{i=1}^\infty$ be independent random variables, assuming values in $[0,1]$, having a common mean $\mu$, and variances bounded by $\sigma^2$. Let $S_n = \sum_{i=1}^n X_i$. We give a general and simple %and easy to grasp method for obtaining asymptotically optimal upper bounds on probabilities of events of the form $\{S_n - E[S_n] \geq na\}$ with explicit dependence on $\mu$ and $\sigma^2$. For general bounded random variables the method yields the Bennett inequality, with a simplified proof. For specific classes of distributions the method can be used to derive bounds that are tighter than those achieved by the Bennett inequality. We demonstrate the power of the method by applying it to the case of symmetric three-point distributions, thus improving previous results for the List Update Problem.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion