TR#: | CS0911 |

Class: | CS |

Title: | Optimal Bounds on Tail Probabilities - A Simplified Approach |

Authors: | A. Cohen, Y. Rabinovich, A. Schuster, and H. Shachnai |

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.

To the list of the CS technical reports of 1997

To the main CS technical reports page