6
$\begingroup$

According to Hoeffding Inequality, if $X_1,\ldots,X_n$ are independent random variables with $\mathbb{P}(X_i \in [a_i,b_i]) = 1 \; \forall i = 1,\ldots,n$ then $\mathbb{P}(\bar{X_n} - \mathbb{E}[\bar{X_n}] \geq t) \leqslant \exp\left(-\frac{2t^2n^2}{\sum_{i=1}^{n}(b_i - a_i)^2}\right) \quad \forall t > 0.$ Does there exist any such bound for the probability of the event $\{\bar{X_n} - c\mathbb{E}[\bar{X_n}] \geqslant t\}$ for any constant $c$. Hoeffding Inequality is just a special case of this event when $c = 1$.

  • 1
    You can just apply Hoeffding's Inequality, replacing $t$ with $t + (c - 1)\mathbb{E}[\bar{X_n}]$.2012-12-06

1 Answers 1

3

To bound this event, you can just apply Hoeffding's Inequality as usual, replacing $t$ with $t + (c - 1)\mathbb{E}[\bar{X_n}]$.