(The one-sided Chebyshev inequality)                               This inequality states that if  a zero-mean rv X has a variance σ 2, then it satisfies the inequality     o 2 Pr{ X ≥ b } ≤ σ 2...

(The one-sided Chebyshev inequality)                               This inequality states that if  a zero-mean rv
X
has a variance
σ
2, then it satisfies the inequality

o
2

Pr{X
≥
b} ≤
σ
2

2         for every
b

>
0,                           (1.101)

+
b

with equality for some
b
only if
X
is binary and Pr{X

=
b} =
σ
2/(σ
2 +
b2). We prove this here using the same approach as in Exercise 1.31. Let
X
be a zero-mean rv that satisfies Pr{X

≥
b} =
β
for some
b

>
0 and 0


β
1. The variance
σ
2 of
X
can be expressed as

o
2 =

r
b−

−∞

x2fX
(x)
dx
+

r ∞

x2 fX
(x)
dx.                             (1.102)

b

We will first minimize
σ
2 over all zero-mean
X
satisfying Pr{X
≥
b} =
β.

(a)

(b)
Show that the first integral in (1.102) is constrained by

r
b−

−∞

fX
(x)
dx
= 1 −
β
and

r
b−

−∞

xfX
(x)
dx
≤ −b
β.

(c)
Minimize the first integral in (1.102) subject to the constraints in (b). Hint: If you scale
f
X
(x) up by 1/(1 −
β), it integrates to 1 over (−∞,
b) and the second con- straint becomes an expectation. You can then minimize the first integral in (1.102) by inspection.

(d)
Combine the results in (a) and (c) to show that
σ
2 ≥
b2β/(1 −
β). Find the minimizing distribution. Hint: It is binary.

(e)
Use (d) to establish (1.101). Also show (trivially) that if
Y
has a mean
Y
and

variance
σ
2, then PrfY

−
Y
≥
bl ≤
σ
2/(σ
2 +
b2)