ThmDex – An index of mathematical definitions, results, and conjectures.
Result R4141 on D1719: Expectation
Probabilistic Chernoff inequality
Formulation 0
Let $X \in \text{Random}(\mathbb{R})$ be a D3161: Random real number.
Let $\lambda > 0$ be a D5407: Positive real number.
Then \begin{equation} \mathbb{P}(X \geq \lambda) \leq \inf_{t \in [0, \infty)} \frac{1}{e^{t \lambda}} \mathbb{E}(e^{t X}) \end{equation}
Proofs
Proof 0
Let $X \in \text{Random}(\mathbb{R})$ be a D3161: Random real number.
Let $\lambda > 0$ be a D5407: Positive real number.
Let $0 \leq t < \infty$ be an unsigned basic real number. Since $e^{t X}$ now takes values in $(0, \infty) \subset [0, \infty)$, then we may apply R2016: Probabilistic Markov's inequality to obtain the inequality \begin{equation} \mathbb{P}(X \geq \lambda) = \mathbb{P}(e^{t X} \geq e^{t \lambda}) \leq \frac{1}{e^{t \lambda}} \mathbb{E}(e^{t X}) \end{equation} Since $t \in [0, \infty)$ was arbitrary, we may extend the right-hand side to infimum to obtain \begin{equation} \mathbb{P}(X \geq \lambda) \leq \inf_{t \in [0, \infty)} \frac{1}{e^{t \lambda}} \mathbb{E}(e^{t X}) \end{equation} $\square$