 Hoeffding inequality

ID: hoeffding-inequality

a_{i} \leq X_{i} \leq b_{i}

, then

P (\sum_{i} (X_{i} - E X_{i}) \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i} ( b _{i} - a _{i} ) ^{2}}),

with the same bound for the lower tail.

 New to topics? Read the docs here!