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?


1 Answer 1


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.

  • $\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, 2013 at 17:20
  • 1
    $\begingroup$ @Adam but then $t$ scales also, and $t/B$ stays constant, no? $\endgroup$
    – Igor Rivin
    Dec 17, 2013 at 22:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .