 Lower-tail concentration for a weakly self-bounding function

ID: lower-tail-concentration-for-a-weakly-self-bounding-function

The entropy method gives

lo g E e^{- λ (Z - E Z)} \leq \frac{λ ^{2} E Z}{2}

for

λ \geq 0

. Consequently the Chernoff bound yields

P (Z - E Z \leq - t) \leq exp [- t^{2} / (2 E Z)]

 New to topics? Read the docs here!