In this section, we give a proof of Hoeffding's inequality[1].
For the proof, we require the following lemma. Suppose
is a real random variable with mean zero such that
. Then
To prove this lemma, note that if one of
or
is zero, then
and the inequality follows. If both are nonzero, then
must be negative and
must be positive.
Next, recall that
is a convex function on the real line. Thus for any
,
Combining the previous inequality with the fact that
results in
where
. Next let
and define
as
Note that
is well defined on
as
and for all
,
since
. The definition of
implies
. By Taylor's theorem, for every real
there exists a
between
and
such that
Note that
,
and
where the last inequality holds because for all
,
. Therefore,
. This implies
Using this lemma, we can prove Hoeffding's inequality. Suppose
are
independent random variables such that for every
,
, we have
. Let
. Then for
, Markov's inequality and the independence of the
's imply
To get the best possible upper bound, we find the minimum of the right hand side of the last inequality as a function of
. Define
as
Note that
is a quadratic function and thus achieves its minimum at
Thus we get
References[edit]
P^rh^m (talk) 19:48, 16 May 2014 (UTC)