Springe direkt zu Inhalt

Natalia Shenkman:

A comparative study of some proofs of Chernoff ’s bound with regard to their applicability for deriving concentration inequalities


Concentration inequalities provide bounds on the tail of the distribution of random variables. This thesis focuses on four different techniques used in the literature to derive the most basic tail bound for sums of independent {0, 1}-valued random variables, commonly referred to as the Chernoff bound. We study their suitability for deriving tail inequalities when the independence assumption as well as the restriction on the values of the random variables are relaxed. As a by-product, we improve the bound in Theorem 3.3 in Impagliazzo and Kabanets (2010).

Master of Education (M.Ed.)