2
$\begingroup$

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!

3 Answers 3

2

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.

  • 0
    Hi Shai. Thanks once again for the help. I took a look at Hoeffding's paper and can't indeed see an easy e$x$$t$ension to his argument. I was hoping someone would know of a different bound that (unlike so many other) did not involve knowing the variance of the distribution, etc, but it seems that the type of bound I'm looking for is not trivial. Thanks once again anyway!2011-01-10
0

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

.

0

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

  • 0
    The OP assumes that $X \in [a,b]$.2011-02-02