# What does the general case of bounded random variables mean in terms of Hoeffding's Inequality?

The following equation is Hoeffding's Inequality from Wikipedia for the general case of bounded random variables.

I have just come to understand Hoeffding's Inequality for the special case of Bernoulli Random Variables but the Hoeffding's Inequality for the general case of bounded random variables is somewhat difficult to understand. What do $$a$$ and $$b$$ mean in the denominator? what values can I plug in $$a$$ and $$b$$? If possible, I hope to know the understandable mathematical steps for the equation.
$$P(|S_n - \mathbb{E}[S_n]|\ge t) \le 2 \exp \left(-\frac{2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right)$$

• "Theorem 2 of Hoeffding (1963) is a generalization of the above inequality when it is known that $X_i$ are strictly bounded by the intervals $[a_i, b_i]$:" from the text line immediately above your quoted equation :) Feb 1 '20 at 3:03

Suppose that we have $$a_i \le X_i \le b_i,$$ then we have $$P(|S_n - \mathbb{E}[S_n]|\ge t) \le 2 \exp \left(-\frac{2t^2}{\sum_{i=1}^n (b_i-a_i)^2} \right)$$

For example, suppose $$X_1$$ is uniformly distributed from $$0$$ to $$1$$, then $$a_1=0$$ and $$b_1=1$$. If $$X_2$$ follows Binomial distribution $$Bin(5,p)$$ from then $$a_2=0$$ and $$b_2=5$$.

Edit:

Suppose you have exactly one distribution, that is $$S=X_1$$ and $$X_1 \sim Bin(5,p)$$. Then we have $$a_1=0, b_1=5$$, then we have

$$P(|S-5p|\ge t) \le 2 \exp \left( -\frac{2t^2}{25}\right)$$

However, if you have viewed it as $$S_5=\sum_{i=1}^5 Y_i$$ where $$Y_i \sim Bernoulli(p)$$. Then we have $$a_i=0, b_i=1$$, then we have

$$P(|S_5-5p| \ge t) \le 2 \exp \left( -\frac{2t^2}{5}\right)$$

Both are valid bounds but the first one is tighter.

• It looks like $X_i$ is some value between $0$ and $1$ assuming $X_i$ is uniformly distributed and the $\Sigma$ sums the value? I don't understand why it is called a general case. Moreover, looking at the special case of Bernoulli Random Variable, the right side has $2n$ on the numerator but it disappears in the general case. I'd like ask why if possible. Feb 1 '20 at 4:29
• We can have $a_1=0, b_1=1$ and $a_2=0, b_2=5$. They need not have the same bounds. Feb 1 '20 at 4:32
• that's strange...are you referring to the wikipedia page? and comparing the inequalities for $P(|\bar{X}−\mathbb{E}[X]|\ge t)$?The denominator tells us suppose you do not know the exact range of a distribution and you provide a not so tight estimate, you get a looser bound Feb 1 '20 at 4:57
• I have edited my post, Yes, suppose $X_1 \sim Uni(0,1)$ and $X_2 \sim Bin(5,p)$, you have computed the donominator correctly. Feb 1 '20 at 5:31
• even for the special case thre is no restriction that $X_i$ must be iid. The only condition is they must be independent. We can use the special case to sum up $Bernoulli(0.2)$ and $Bernoulli(0.7)$. The general case remove the restriction that the distribution must be bounded between $0$ and $1$. Feb 1 '20 at 5:41