Hoeffding's Lemma
   HOME

TheInfoList



OR:

In
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
, Hoeffding's lemma is an
inequality Inequality may refer to: Economics * Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy * Economic inequality, difference in economic well-being between population groups * ...
that bounds the
moment-generating function In probability theory and statistics, the moment-generating function of a real-valued random variable is an alternative specification of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compar ...
of any bounded
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the p ...
. It is named after the FinnishAmerican
mathematical statistician Mathematical statistics is the application of probability theory, a branch of mathematics, to statistics, as opposed to techniques for collecting statistical data. Specific mathematical techniques which are used for this include mathematical an ...
Wassily Hoeffding Wassily Hoeffding (June 12, 1914 – February 28, 1991) was a Finnish statistician and probabilist. Hoeffding was one of the founders of nonparametric statistics, in which Hoeffding contributed the idea and basic results on U-statistics. In pr ...
. The proof of Hoeffding's lemma uses
Taylor's theorem In calculus, Taylor's theorem gives an approximation of a ''k''-times differentiable function around a given point by a polynomial of degree ''k'', called the ''k''th-order Taylor polynomial. For a smooth function, the Taylor polynomial is the ...
and
Jensen's inequality In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906, building on an earlier ...
. Hoeffding's lemma is itself used in the proof of McDiarmid's inequality.


Statement of the lemma

Let ''X'' be any real-valued random variable such that a \leq X \leq b
almost surely In probability theory, an event is said to happen almost surely (sometimes abbreviated as a.s.) if it happens with probability 1 (or Lebesgue measure 1). In other words, the set of possible exceptions may be non-empty, but it has probability 0 ...
, i.e. with probability one. Then, for all \lambda \in \mathbb, :\mathbb \left e^ \right\leq \exp \Big(\lambda\mathbb \frac \Big), or equivalently, :\mathbb \left e^ \right\leq \exp \Big(\frac \Big).


Proof

Without loss of generality, by replacing X by X - \mathbb /math>, we can assume \mathbb = 0, so that a \leq 0 \leq b. Since e^ is a convex function of x, we have that for all x \in ,b/math>, :e^\leq \frace^+\frace^ So, :\begin \mathbb\left ^\right&\leq \frace^+\frace^\\ &= \frace^ + \frace^ \\ &= e^, \end where L(h)= \frac+\ln(1 + \frac). By computing derivatives, we find : L(0)=L'(0)=0 and L''(h)= -\frac. From the AMGM inequality we thus see that L''(h)\le\frac14 for all h, and thus, from
Taylor's theorem In calculus, Taylor's theorem gives an approximation of a ''k''-times differentiable function around a given point by a polynomial of degree ''k'', called the ''k''th-order Taylor polynomial. For a smooth function, the Taylor polynomial is the ...
, there is some 0 \le \theta \le 1 such that : L(h) = L(0) + h L'(0) + \frac h^2 L''(h\theta) \leq \frach^2. Thus, \mathbb\left ^\right\leq e^.


See also

*
Hoeffding's inequality In probability theory, Hoeffding's inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. Hoeffding's inequality was proven by Wass ...
* Bennett's inequality


Notes

Probabilistic inequalities {{probability-stub