Talagrand’s Concentration Inequality

We prove a powerful inequality which provides very tight gaussian tail bounds “e^{-ct^2}” for probabilities on product state spaces \Omega^n. Talagrand’s Inequality has found lots of applications in probability and combinatorial optimization and, if one can apply it, it generally outperforms inequalities like Azzuma-Hoeffding.

Continue reading “Talagrand’s Concentration Inequality”