Hoeffding's Inequality for Sums of Weakly Dependent andom Variables



Friday, 24 June 2016, 16:00 to 17:30


  • A-201 (STCS Seminar Room)


Let X_1, X_2, ... ,X_n be, possibly dependent, [0,1]-valued random variables. The following question is important: What is a sharp upper bound on the probability that their sum is significantly larger (or significantly smaller) than their mean? We see the classical result by Wassily Hoeffding (1963) for independent random variables, and generalize the result to  several notions of weak dependence between the random variables.