0
$\begingroup$

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)$$

$\endgroup$
1
  • 2
    $\begingroup$ "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 :) $\endgroup$
    – jbowman
    Feb 1 '20 at 3:03
1
$\begingroup$

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.

$\endgroup$
16
  • $\begingroup$ 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. $\endgroup$
    – StoryMay
    Feb 1 '20 at 4:29
  • 1
    $\begingroup$ We can have $a_1=0, b_1=1$ and $a_2=0, b_2=5$. They need not have the same bounds. $\endgroup$ Feb 1 '20 at 4:32
  • 1
    $\begingroup$ 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 $\endgroup$ Feb 1 '20 at 4:57
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 1 '20 at 5:31
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 1 '20 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.