I'm new to concentration inequalities and I have a question related to Hoeffding's inequality.

Let $X_1 ~ \dots X_n$ be a set of i.i.d random variables, s.t. $E[X_i] = \mu$, $Var[X_i] = \sigma^2$, and $0 \leq X_i \leq c$. Let $\bar{X}_n = \frac{1}{n}\sum_{i=1}^n X_i$ be the sample mean.

By Hoeffding's inequality we have that: \begin{eqnarray} \Pr \left[ (\bar{X}_n - E[\bar{X}_n]) \geq t \right]& \leq & \exp\left( - \frac{2nt^2}{c^2} \right), \end{eqnarray} for $t > 0$.

What I'm looking for is not $\Pr[ (\bar{X}_n - E[\bar{X}_n]) \geq t ]$, but the $\Pr [ \bar{X}_n \geq \beta + t]$, where $\beta > 0$.

Is there a different inequality for this probability?

Can I say that if $\beta \geq E[\bar{X}_n]$, then let $\beta = \alpha + E[\bar{X}_n]$, for constant $\alpha > 0$, and then proceed with Hoeffding's inequality. Then proceed in a similar way if $\beta \leq E[\bar{X}_n]$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.