= Exponential Markov bound
Applying <Markov's inequality> to the positive <random variable> $e^{tX}$ gives
$$
\Pr(X\geq x)\leq e^{-tx}M_X(t),
\qquad t>0.
$$
Here $M_X(t)=\mathbb E[e^{tX}]$ is the <moment-generating function>, and the useful bound requires it to be finite at the chosen $t$. Optimizing over $t>0$ gives the <Chernoff bound> method: an <exponential function> weights large values more strongly before applying the same average-budget argument.
For example, let $N$ have the <Poisson distribution> with parameter one. Its <expected value> and <variance> are both one, and its <moment-generating function> is $M_N(t)=\exp(e^t-1)$. At threshold four, choosing $t=\log4$ gives
$$
\mathbb P(N\geq4)\leq\exp(3-4\log4)=\frac{e^3}{256}\approx0.0784591.
$$
This $t$ minimizes the exponent $e^t-1-4t$ because its <derivative> is $e^t-4$, with positive <second derivative>. The direct <Markov's inequality> bound is $1/4$, and the two-sided <Chebyshev's inequality> bound, applied to a deviation of at least three from the <mean> one, is $1/9$. The exact <Poisson distribution> <tail probability> is $1-e^{-1}(1+1+1/2+1/6)\approx0.0189882$. These compare three valid bounds obtained from progressively different information; none is an exact <tail probability> formula for general <random variables>.
Back to article page
