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 ...
, the Azuma–Hoeffding inequality (named after
Kazuoki Azuma
(born 1939) is a Japanese mathematician. Azuma's inequality in probability theory is named after him.
Publications
*
References
External links
* , archived at the Internet Archive
Partial Bibliographyat CiNii
CiNii () is a bibliographic d ...
and
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 prob ...
) gives a
concentration result for the values of
martingales that have bounded differences.
Suppose
is a
martingale (or
super-martingale) and
:
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. ...
. Then for all positive integers ''N'' and all positive
reals ''
'',
:
And symmetrically (when ''X''
''k'' is a sub-martingale):
:
If ''X'' is a martingale, using both inequalities above and applying the
union bound
In probability theory, Boole's inequality, also known as the union bound, says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the probabilities of the individ ...
allows one to obtain a two-sided bound:
:
Proof
The proof shares similar idea of the proof for the general form of Azuma's inequality listed below. Actually, this can be viewed as a direct corollary of the general form of Azuma's inequality.
A general form of Azuma's inequality
Limitation of the vanilla Azuma's inequality
Note that the vanilla Azuma's inequality requires symmetric bounds on martingale increments, i.e.
. So, if known bound is asymmetric, e.g.
, to use Azuma's inequality, one need to choose
which might be a waste of information on the boundedness of
. However, this issue can be resolved and one can obtain a tighter probability bound with the following general form of Azuma's inequality.
Statement
Let
be a martingale (or supermartingale) with respect to
filtration . Assume there are
predictable processes and
with respect to
, i.e. for all
,
are
-
measurable
In mathematics, the concept of a measure is a generalization and formalization of Geometry#Length, area, and volume, geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly ...
, and constants