I'm working on a problem that requires me to find an upper bound on the probability that the sum of independent draws from a random variable deviates from the expected value of that sum by more than a given constant. Specifically, let $X$ be a random variable and suppose that we draw $m$ values for $X$. Let $S$ be the sum of those draws: $S=\sum_{i=1}^m X_i$, where $X_i$ is the $i$-th draw from $X$. This sum has expected value $E[S]$. If we assume that $X$'s values are always in the interval of $[a, b]$, one could try to find an upper bound on the probability that the sum of the draws deviates from the expected value of the sum by more than $t$:
$P(S – E[S] > t)$
Hoeffding's inequality tells us that an upper bound for this probability is
$\exp\bigg( \frac{-2t^2}{\sum_{i=1}^m (a – b)^2} \bigg)$
The problem that I have requires me to find an upper bound on the probability that $k$ times the sum of draws deviates from the expected value by more than $t$:
$P(kS – E[S] > t)$
where $k$ is a constant.
It seems that it should be easy to find an upper bound for this probability, but I'm kind of stuck: I've tried simple algebraic manipulations in order to try to get rid of the $k$ an transform that probability into something that would allow me to use Hoeffding's bound; I also took a look at other bounds, like the Bernstein inequalities, but nothing seems quite right.
Does anybody have an idea for a bound for this type of probability? I feel that the answer is right in front of me but I can't see it…
Thanks in advance!
Best Answer
Are you looking for something like this: $$ {\rm P}[kS - {\rm E}(S) > t] = {\rm P}[kS - {\rm E}(kS) > t - (k - 1){\rm E}(S)]. $$ Also not that $kS=kX_1 + \cdots + kX_m$ is a sum of $m$ i.i.d. random variables.
EDIT: Assuming, from a practical point of view, that ${\rm E}(X)$ is known (and $X \in [a,b]$), then, by Hoeffding's inequality, the above equation gives $$ {\rm P}[kS - {\rm E}(S) \geq t] \leq \exp \bigg( - \frac{{2[t - (k - 1)m{\rm E}(X)]^2 }}{{mk^2 (b - a)^2 }}\bigg), $$ provided that $t - (k - 1)m{\rm E}(X) > 0$ (note that $kX$ belongs to the interval $[ka,kb]$, whose length is $k(b-a)$). If, on the other hand, ${\rm E}(X)$ is not known, then nothing useful is likely to be achieved.