Hoeffding's lemma
Encyclopedia
In probability theory
, Hoeffding's lemma is an inequality that bounds the moment-generating function
of any bounded
random variable
. It is named after the Finnish–American
mathematical statistician
Wassily Hoeffding
.
The proof of Hoeffding's lemma uses Taylor's theorem
and Jensen's inequality
. Hoeffding's lemma is itself used in the proof of McDiarmid's inequality.
E[X] = 0 and such that a ≤ X ≤ b almost surely
. Then, for all λ ∈ R,
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, Hoeffding's lemma is an inequality that bounds the moment-generating function
Moment-generating function
In probability theory and statistics, the moment-generating function of any random variable is an alternative definition of its probability distribution. Thus, it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or...
of any bounded
Bounded function
In mathematics, a function f defined on some set X with real or complex values is called bounded, if the set of its values is bounded. In other words, there exists a real number M...
random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
. It is named after the Finnish–American
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
mathematical statistician
Mathematical statistics
Mathematical statistics is the study of statistics from a mathematical standpoint, using probability theory as well as other branches of mathematics such as linear algebra and analysis...
Wassily Hoeffding
Wassily Hoeffding
Wassily Hoeffding was an American statistician and probabilist...
.
The proof of Hoeffding's lemma uses Taylor's theorem
Taylor's theorem
In calculus, Taylor's theorem gives an approximation of a k times differentiable function around a given point by a k-th order Taylor-polynomial. For analytic functions the Taylor polynomials at a given point are finite order truncations of its Taylor's series, which completely determines the...
and Jensen's inequality
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. Given its generality, the inequality appears in many forms depending on the context,...
. 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 with expected valueExpected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
E[X] = 0 and such that a ≤ X ≤ b almost surely
Almost surely
In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory...
. Then, for all λ ∈ R,