# Hoeffding inequality adapted to discrete random variables

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?

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.

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