# 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?

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