Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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

.

share|improve this answer

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.