# Technical Report CS0911

 TR#: CS0911 Class: CS Title: Optimal Bounds on Tail Probabilities - A Simplified Approach Authors: A. Cohen, Y. Rabinovich, A. Schuster, and H. Shachnai PDF CS0911.pdf 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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0911), rather than to the URL of the PDF files directly. The latter URLs may change without notice.