6
$\begingroup$

Given $n$ (real-valued) random variables $X_1, X_2, ..., X_n \in [0, B]$, it can be derived from Hoeffding's Inequality that: $$\mathbb{P}^n\left[ \bar{X} - \mathbb{E}_n[ \bar{X} ] \geq t \right] \leq \exp \left( - \frac{2 n t^2}{B^2} \right) $$ where $\bar{X} = \frac{1}{n} \sum_{i=1}^{n} X_i$, and $\mathbb{P}^n$ is the product measure $\mathbb{P} \times \mathbb{P} \times \ldots \mathbb{P}$ ($n$ times).

Is there a tighter bound if we have (integer-valued) random variables $X_1, X_2, ..., X_n \in \{0, 1, ..., B-1, B\}$? What similar inequalities are available for discrete, bounded, random variables?

|cite|improve this question
$\endgroup$
1
$\begingroup$

This is as good as it gets, I am afraid. In fact, if you read the article you link to, the first example of the use of Hoeffding' inequality is for Bernoulli random variables! More formally, you can approximate continuous RVs by discrete ones, so you should have about the same behavior.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Dear Igor, thanks for the answer. What is not clear to me is what prevents me from scaling $X$ so that I make $B$ arbitrarily small. $\endgroup$ – user693 Dec 17 '13 at 17:20
  • 1
    $\begingroup$ @Adam but then $t$ scales also, and $t/B$ stays constant, no? $\endgroup$ – Igor Rivin Dec 17 '13 at 22:47

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.