2015
09.03

See here.

  1. Hey Sariel,

    Thanks for posting. Just wanted to make a comment that often the delta > 2e-1 case is treated separately, but for delta larger than some constant, it follows from the (e^delta / (1+delta)^{1+delta})^{mu} bound that the tail is actually something like exp(-Omega(delta * ln(delta) * mu))) (as opposed to just the exp(-Omega(delta*mu)) written in many places). This extra ln(delta) in the exponent can be important sometimes. Also, a slightly stronger tail bound which both implies Chernoff and dominates Bernstein is Bennett’s inequality, which really isn’t much harder to prove and doesn’t seem to get enough credit (e.g. it’s not in the Dubhashi and Panconesi book as far as I can tell). It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}

    It's mentioned here as exercise 3: https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/

    • The last part got clobbered somehow and I can’t edit…the statement of Bennett is:

      It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}

    • The far bound that you mentioned is used quite a bit. It would indeed be useful to mention it somehow…