The additive Chernoff bound for the absolute value.

distribution-tailsmoment-generating-functionsprobabilityprobability distributionsupper-lower-bounds

I am trying to derive a generic, additive Chernoff bound for $\Pr[|X-\mu|\leq a]$ with $a>0$. By generic I mean a Chernoff bound in terms of the moment generating function instead of assuming a specific distribution of $X$.

Applying the Markov inequality gives the upper tail:

$$\Pr[X-\mu\geq a] = \Pr[X\geq \mu + a]\leq \frac{E[e^{Xt}]}{e^{(\mu + a)t}}$$

and the lower tail

$$\Pr[X-\mu \leq – a] = \Pr[X\leq \mu – a]\leq \frac{E[e^{-Xt}]}{e^{-(\mu – a)t}}$$

I am not sure how to combine these two to obtain a bound for $\Pr[|X-\mu|\leq a]$.

I could not find such generic bound in online resources. Only for $X$ following a Binomial distribution.

Best Answer

Consider the complement event. For instance, we can use the union bound as follows:

$$ \mathrm{P}(|X-\mu|\geq a) = \mathrm{P}(\{X-\mu\geq a\} \cup \{X-\mu\leq -a\} )\leq \mathrm{P}(X-\mu\geq a)+ \mathrm{P}(X-\mu\leq -a). $$ This is a generic approach and you may use other tricks for particular problems.