7.4 Other inequalities

Result 7.4.1 (One-sided Chebyshev inequality). If \(X\) is a random variable with mean \(0\) and finite variance \(\sigma ^2\), then for any \(a > 0\), \[ P(X \ge a) \le \frac {\sigma ^2}{\sigma ^2 + a^2} . \]

Proof. For any \(k > 0\), \(X \ge a\) implies \(X + k \ge a + k > 0\), and hence \((X + k)^2 \ge (a + k)^2\). By Markov’s inequality, \begin {align*} P(X \ge a) &\le P\bigl ((X + k)^2 \ge (a + k)^2\bigr ) \le \frac {E(X + k)^2}{(a + k)^2} \\ &= \frac {E(X^2 + 2kX + k^2)}{(a + k)^2} = \frac {\sigma ^2 + k^2}{(a + k)^2} , \end {align*}

since \(E(X) = 0\). This holds for every \(k > 0\), so we choose the \(k\) that makes the bound smallest. With \(g(k) = (\sigma ^2 + k^2)/(a + k)^2\), \[ g'(k) = \frac {2k(a + k)^2 - 2(\sigma ^2 + k^2)(a + k)}{(a + k)^4} = \frac {2(a + k)(ak - \sigma ^2)}{(a + k)^4} , \] since \(k(a + k) - \sigma ^2 - k^2 = ak - \sigma ^2\). For \(k > 0\) this vanishes only at \(k = \sigma ^2/a\), where \(g\) is smallest. Then \[ P(X \ge a) \le \frac {\sigma ^2 + \sigma ^4/a^2}{(a + \sigma ^2/a)^2} = \frac {\sigma ^2(a^2 + \sigma ^2)/a^2}{(a^2 + \sigma ^2)^2/a^2} = \frac {\sigma ^2}{a^2 + \sigma ^2} . \] □

Example 7.4.2. In Example 7.1.3, the number \(X\) of items produced in a week has mean \(60\) and variance \(16\). Find a lower bound for the probability that this week’s production will be fewer than \(70\).

Solution. Apply the one-sided inequality to \(X - 60\), which has mean \(0\) and variance \(16\), with \(a = 10\): \[ P(X \ge 70) = P(X - 60 \ge 10) \le \frac {16}{16 + 10^2} = \frac {16}{116} = 0.138 . \] So \(P(X < 70) \ge 1 - 0.138 = 0.862\). The ordinary Chebyshev inequality would give only \(P(X \ge 70) \le P(|X - 60| \ge 10) \le 0.16\); using one side of the distribution improves the bound.

Result 7.4.3 (Chernoff bounds). If \(X\) has moment generating function \(M_X(t)\), then for any \(a\),

(i)
\(P(X \ge a) \le e^{-at}M_X(t)\) for all \(t > 0\);
(ii)
\(P(X \le a) \le e^{-at}M_X(t)\) for all \(t < 0\).

Proof. (i) For \(t > 0\), \(x \mapsto e^{tx}\) is increasing, so \(X \ge a\) exactly when \(e^{tX} \ge e^{ta}\). By Markov’s inequality applied to the non-negative variable \(e^{tX}\), \[ P(X \ge a) = P\bigl (e^{tX} \ge e^{ta}\bigr ) \le \frac {E\bigl (e^{tX}\bigr )}{e^{ta}} = e^{-at}M_X(t) . \] (ii) For \(t < 0\), \(x \mapsto e^{tx}\) is decreasing, so \(X \le a\) exactly when \(e^{tX} \ge e^{ta}\), and the same argument applies. □

Since the bounds hold for every \(t\) of the right sign, the best bound is obtained by choosing \(t\) to minimise \(e^{-at}M_X(t)\).

Definition 7.4.4. A twice-differentiable real-valued function \(f\) on an interval is

(i)
convex if \(f''(x) \ge 0\) for all \(x\) in the interval;
(ii)
concave if \(f''(x) \le 0\) for all \(x\) in the interval.

Example 7.4.5. Show that \(f(x) = x^2\), \(g(x) = e^{ax}\) and, for \(x > 0\) and an integer \(n \ge 1\), \(h(x) = -x^{1/n}\) are convex.

Solution. \(f'(x) = 2x\) and \(f''(x) = 2 \ge 0\), so \(f\) is convex, and \(-f(x) = -x^2\) is concave.

\(g'(x) = ae^{ax}\) and \(g''(x) = a^2e^{ax} \ge 0\), so \(g\) is convex, and \(-e^{ax}\) is concave.

\(h'(x) = -\frac 1nx^{\frac 1n - 1}\) and \[ h''(x) = -\frac 1n\Bigl (\frac 1n - 1\Bigr )x^{\frac 1n - 2} = \frac {n - 1}{n^2}x^{\frac 1n - 2} \ge 0 \qquad (x > 0) , \] so \(h\) is convex, and \(x^{1/n}\) is concave on \(x > 0\).

Result 7.4.6 (Jensen’s inequality). If \(g\) is a convex function and \(X\) is a random variable with finite mean, then \[ E\bigl (g(X)\bigr ) \ge g\bigl (E(X)\bigr ) . \]

Proof. Let \(\mu = E(X)\), and expand \(g(X)\) by Taylor’s theorem about \(\mu \): \[ g(X) = g(\mu ) + g'(\mu )(X - \mu ) + \frac {g''(\eta )}{2}(X - \mu )^2 , \] where \(\eta \) lies between \(X\) and \(\mu \). Since \(g''(\eta ) \ge 0\), the last term is non-negative, so \[ g(X) \ge g(\mu ) + g'(\mu )(X - \mu ) . \] Taking expectations, and using \(E(X - \mu ) = 0\), \[ E\bigl (g(X)\bigr ) \ge g(\mu ) = g\bigl (E(X)\bigr ) . \] □

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.