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

Improve this question
$\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
    Commented Feb 1, 2020 at 3:03

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – xabzakabecd
    Commented Feb 1, 2020 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$
    – Siong Thye Goh
    Commented Feb 1, 2020 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$
    – Siong Thye Goh
    Commented Feb 1, 2020 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$
    – Siong Thye Goh
    Commented Feb 1, 2020 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$
    – Siong Thye Goh
    Commented Feb 1, 2020 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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