General Case
Let
be independent random variables. Assume that the are almost surely bounded; that is, assume for that
We define the sum of these variables
Theorem 2 of Hoeffding (1963) proves the inequalities
which are valid for positive values of t. Here is the expected value of S.
Note that the inequalities also hold when the have been obtained using sampling without replacement; in this case the random variables are not independent anymore. A proof of this statement can be found in Hoeffding's paper. For slightly better bounds in the case of sampling without replacement, see for instance the paper by Serfling (1974).
Read more about this topic: Hoeffding's Inequality
Famous quotes containing the words general and/or case:
“I have never looked at foreign countries or gone there but with the purpose of getting to know the general human qualities that are spread all over the earth in very different forms, and then to find these qualities again in my own country and to recognize and to further them.”
—Johann Wolfgang Von Goethe (1749–1832)
“It is often the case that the man who can’t tell a lie thinks he is the best judge of one.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)