Bounding probability that sum of random variables deviates from expected value

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...

-

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.

-
Thanks for the quick answer, Shai. I'm not sure if your idea would help, though, unless I'm missing something. Specifically, now the stuff that we have on the right-hand side of the inequality is not a constant anymore -- at least not independent of E[S]. In that case, Hoeffding's inequality would not apply, I believe, since the amount by which we want the sum to differ from the expected value is not a constant (like $t$, in the original post) -- it actually depends on the expectation itself, which might be unknown. Sorry if I'm missing something obvious... –  Bruno Jan 7 '11 at 9:18
${\rm E}[S]$ is a constant (even if unknown), hence $t-(k-1)E[S]$ is. In case $E[S]$ is unknown, it can be easily approximated as follows. ${\rm E}[S]=m{\rm E}[X]$, and $\frac{1}{n}\sum\nolimits_{i = 1}^n {X_i }$ should converge fast to $E[X]$ (as $n \to \infty$), assuming that $X_i \in [a,b]$. But why would ${\rm E}[S]$, equivalently ${\rm E}[X]$, be unknown? If you know the distribution of $X$, you should generally know its expectation. However, you should check whether the right-hand side, i.e. $t-(k-1)E[S]$, is positive. –  Shai Covo Jan 7 '11 at 9:45
Right, you can approximate it, but notice that Hoeffding's inequality does not assume anything about how the variables are distributed, and nonetheless has a well-defined bound that does NOT require you to know E[S] or E[X] or anything like that. Given any type of random variable, for which I might not know the distribution, that inequality gives me an upper bound on the probability of interest just in terms of the constant $t$ and on the interval of the values that X might assume. In my problem, I want to know ... –  Bruno Jan 7 '11 at 18:15
... something like this: what is the probability that $k$ times the sum of $m$ draws deviates from the expected value of that sum by more than 0.2 (or whatever constant I choose). In this case, t=0.2. This $t$ needs to be a concrete number that I can plug into the Hoeffding's equation. If I were to modify the problem like you suggested, such that the right-hand side of the inequality is $t - (k-1)E[S]$, I wouldn't know what that value is in order to plug it into the bound equation (...) –  Bruno Jan 7 '11 at 18:15
... Sure, I can approximate if I assume that I have a large enough number of draws, but then the bound is not exact anymore; it's an approximation. In my problem, approximating E[S] on the right-hand side wouldn't make sense since in the end that's exactly what I'm trying to estimate, and my interest in the upper bound is to find how many draws I need to take from X so that if I average them, I get close to E[S] by no more than $t$ with probability at least $\delta$ (for some given $t$ and $\delta$. ... –  Bruno Jan 7 '11 at 18:16

Are you looking for the Chebyshev's inequality? Obviously you need to know the variance of the distribution to apply it.

Chebyshev inequality,

P(|X−μ|≥kσ)≤ 1/$k^2$

where μ = E(X) and σ = Standard Deviation

.

-

Assuming I understand the question correctly, there is no such bound other than 1.

If S is well concentrated (say, a non zero constant), kS-E(S) can be made as large as you want by increasing E(S).

-
The OP assumes that $X \in [a,b]$. –  Shai Covo Feb 2 '11 at 0:51