<p>You need McDiarmid's inequality, or in particular the <a href="http://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_Case" rel="nofollow">Hoeffding inequality</a>, which is a simplification: </p>

<p>Given $n$ independent $X_i$ with the property that $X_i \in [a_i, b_i]$, and $X = (1/n)\sum X_i$, then </p>

<p>$$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b_i - a_i)^2}) $$</p>

CC BY-SA 3.0
2012-11-07T14:58:30.953Z
Using the variable $Z=\sum_i X_i=nX$ as well as $X_i\in[-1,1]$ and $E(X_i)=0$, we have $\sum(b_i-a_i)^2=4n$ and your formula basically says $$\Pr(|Z|\ge\lambda)=\Pr(|X|\ge n^{-1}\lambda)\le 2e^{-\lambda^2/2n}.$$ However, Chernoff says $$\Pr(|Z|\ge\lambda)\le 2e^{-\lambda^2/4\sigma^2}.$$ Even with the trivial observation $\sigma\le 1$, I would achieve a bound of $2e^{-\lambda^2/4}$ (which is better than $2e^{-\lambda^2/2n}$ for $n>2$) and even that one is, by far, not good enough. Do I have any other option?
Jesko Hüttenhain
CC BY-SA 3.0
2012-11-07T23:57:18.987Z
There's a variant of McDiarmid's inequality called Bernstein's inequality if you have formal bounds on the variance. In general, you should look at the Dubhashi-Panconesi book on concentration of measure.
Suresh Venkat
CC BY-SA 3.0
2012-11-07T08:53:06.990Z
2012-11-07T08:53:06.990Z
Suresh Venkat
<p>This is a <a href="https://math.stackexchange.com/questions/231455/estimator-for-sum-of-independent-and-identically-distributed-iid-variables">repost of a question at math.stackexchange</a>, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.</p>

<p>Consider the Chernoff bound described in Theorem 1 of <a href="http://cseweb.ucsd.edu/~klevchen/techniques/chernoff.pdf" rel="nofollow noreferrer">this paper</a>:</p>

<blockquote>
  <p><strong>Theorem 1.</strong> Let $X_1,\ldots,X_n$ be discrete, independent random variables such that $E[X_i] = 0$ and $|X_i|&lt;1$ for all $i$. Let $X:=\sum_{i=1}^n X_i$ and $\sigma^2$ be the variance of $X$. Then,
  $$\Pr\left[|X|\ge \lambda\sigma\right] \le 2e^{-\lambda^2/4}$$
  for any $0\le\lambda\le 2\sigma$.</p>
</blockquote>

<p>I want to apply this estimator for a computation, but the variance of the variables $X_i$ is unknown to me. Apart from that, my variables satisfy all the conditions of Theorem 1. In fact, my variables are independent and <em>identically distributed</em> (iid).</p>

<p>On the other hand, there is <a href="http://en.wikipedia.org/wiki/Chebyshev&#39;s_inequality#Finite_samples" rel="nofollow noreferrer">Chebyshev's inequality for finite samples</a> which does not require knowledge of the variance (or mean) of a given random variable and replaces it with the corresponding values of my given sample.
 However, the estimator is not good enough for my application and I was wondering if there is an estimator similar to Theorem 1 but not featuring the variance of the distribution itself. </p>

<p>Intuitively speaking, it would be nice to have the best of both worlds: If that is not possible, then what is the best bound I can achieve for a sum of iid variables, without any knowledge about their variance?</p>

<p><strong>Edit.</strong> I will explain the application in greater detail. I have a tree, at its leaves $v$ are labels $\ell(v)$ with values from the interval $[-1,1]$. I want to know whether these values sum to zero, but summing them up would take too long, because there are too many of them. However, I can easily do a random walk from the root to a leaf. Viewing the tree as a decision tree this way, let $p(v)$ be the probability of each leaf $v$. I then sample a couple of leaves $v_1,\ldots,v_n$ and compute the values $\tfrac{\ell(v_i)}{P\cdot p(v_i)}$, where $P$ is an upper bound for $\tfrac{1}{p(v)}$. Under the null hypthesis that the leaf lables sum to zero, the expected value of a random variable sampling this fraction is 
$$\sum_v p(v) \cdot \frac{\ell(v)}{Pp(v)} = \frac{1}{P} \sum_v \ell(v) = 0.$$
Hence, I am in the situation of Theorem 1. I compute 
$$t=\sum_{i=1}^n \frac{\ell(v_i)}{P\cdot p(v_i)\cdot\sigma}$$
and by Theorem 1, $2e^{-t^2/4}$ is an upper bound for the probability that this sample was obtained under the assumption of the null hypothesis. Now, this works very well for small test instances when I compute $\sigma$ - which actually requires me to search the entire tree. For larger instances, that's exactly what I am trying to avoid, so I need something different. It would be less of a problem to use the mean or the standard deviation of my <em>sample</em>, for instance.</p>

<p>Note that 
$$\textstyle
\sigma^2 = E(X^2)- E(X)^2 = E(X^2) = E(\sum_{i=1}^n X_i^2) + E(\sum_{i\ne j} X_i X_j).$$
Since $X_i$ and $X_j$ are independent, this means $\sigma^2 = n E(X_1^2)$. In my application, the expected value of $X_1^2$ is so small that reasonably large sample sizes cannot negate the effect that $\sigma^2$ is very small.</p>

CC BY-SA 3.0
2012-11-07T19:04:56.183Z
(repost of my comment at math.stackexhange.)  I think I misinterpreted your question, so I deleted my comments below (saying that, given no information about the variance, Chernoff bounds are the best you can do). Can you clarify two points?  (1) Are you seeking a bound to *analyze* an algorithm, or to use *within* an algorithm (somehow along with sampling)?  (2) You mentioned somewhere that in your case $\sigma << 1$.  Why does this happen in your case?  (For any fixed distribution on the $X_i$, the variance of their sum has to grow linearly with $n$ as $n\rightarrow\infty$, right?)  Thanks.
Neal Young
CC BY-SA 3.0
2012-11-07T21:12:45.063Z
I have tried to explain my application in greater detail in my above edit. I cannot tell you precisely why $\sigma$ is so small in my application, it's merely an empirical observation so far. I think that the values $\ell(v)$ might actually come from an intervall much terser around $0$, but I can't be sure. If I let $n$ grow large enough to negate that effect, the method becomes infeasable, from what I can tell even for small instances.
Jesko Hüttenhain
CC BY-SA 3.0
2012-11-07T22:59:11.107Z
Thanks. Do you need to tell whether the sum is exactly zero, or just *near* zero (and if so, critically, *how near*)?  (The first seems impossible without more information.  Consider the setting where either all leaves have $\ell(v) = 0$, or all but one has $\ell(v)=0$.  This setting fits your description, but you cannot hope to determine whether $\sum_v \ell(v) = 0$ without sampling enough to cover all leaves.)
Neal Young
CC BY-SA 3.0
2012-11-07T23:09:04.147Z
Do you mean to imply that $|\ell(v)/p(v)|\le 1$?  (Your use of the bound seems to assume that but you state only that $|\ell(v)|\le 1$.)
Neal Young
CC BY-SA 3.0
2012-11-08T06:55:27.130Z
I'm sorry, I forgot something important. I scale with a constant $P$ to ensure $|\ell(v)/p(v)|\le 1$, I added that. Regarding your other question, I indeed want to know whether the sum is *exactly* zero..
Jesko Hüttenhain
CC BY-SA 3.0
2012-11-08T16:14:19.227Z
FWIW, the problem you describe, in general, is co-NP-hard (and actually #P-hard).  E.g., Given a Boolean formula $\Phi$, sample a random assignment to the variables, and let $\ell(v)=1$ if the assignment corresponding to $v$ satisfies $\Phi$.  Then the sum is zero iff $\Phi$ is not satisfiable.  So, if there was a poly-time algorithm for your problem (in general), you would have P=NP.  (Similarly, you would also have P=#P.  Similarly, determining the answer w.h.p. is hard.)  Is this what you are seeking?  (That is, an efficient algorithm to determine whether the sum is non-zero?)
Neal Young
CC BY-SA 3.0
2012-11-08T17:55:25.593Z
What you say is true. That is more or less the reason *why* I am attempting a probabilistic approach, not a deterministic one. Furthermore, I am not even trying to prove that the sum *is* zero, I am only trying to discard that null hypothesis. My algorithm won't even detect all no-instances. It is one of those things that might be good in practice, though.
Jesko Hüttenhain
CC BY-SA 3.0
2012-11-08T21:45:50.720Z
Thanks for clarifying.  FWIW, even a randomized algorithm can't do it in polytime with probability 1/poly(n), unless e.g. BPP=NP (which is unlikely).  Independent of complexity, in a black-box model (where you can only learn about $\ell(v)$ by querying with $v$, and $\ell:V\rightarrow \{0,1\}$ can be arbitrary) you provably can't distinguish between zero sum and non-zero sum with high probability without querying most of the leaves.  (I keep more or less repeating myself here in the comments, so perhaps I don't understand your goal in a formal sense.  I am curious though, thanks.)
Neal Young
<pr.probability><st.statistics><chernoff-bound>
Estimator for sum of independent and identically distributed (iid) variables
Jesko Hüttenhain
# Estimator for sum of independent and identically distributed (iid) variables

(Asked by: username_0 on 2012-11-07)

This is a [repost of a question at math.stackexchange](https://math.stackexchange.com/questions/231455/estimator-for-sum-of-independent-and-identically-distributed-iid-variables), but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.

Consider the Chernoff bound described in Theorem 1 of [this paper](http://cseweb.ucsd.edu/~klevchen/techniques/chernoff.pdf):

> **Theorem 1.** Let $X\_1,\ldots,X\_n$ be discrete, independent random variables such that $E[X\_i] = 0$ and $|X\_i|<1$ for all $i$. Let $X:=\sum\_{i=1}^n X\_i$ and $\sigma^2$ be the variance of $X$. Then,
> $$\Pr\left[|X|\ge \lambda\sigma\right] \le 2e^{-\lambda^2/4}$$
> for any $0\le\lambda\le 2\sigma$.

I want to apply this estimator for a computation, but the variance of the variables $X\_i$ is unknown to me. Apart from that, my variables satisfy all the conditions of Theorem 1. In fact, my variables are independent and *identically distributed* (iid).

On the other hand, there is [Chebyshev's inequality for finite samples](http://en.wikipedia.org/wiki/Chebyshev's_inequality#Finite_samples) which does not require knowledge of the variance (or mean) of a given random variable and replaces it with the corresponding values of my given sample.
However, the estimator is not good enough for my application and I was wondering if there is an estimator similar to Theorem 1 but not featuring the variance of the distribution itself.

Intuitively speaking, it would be nice to have the best of both worlds: If that is not possible, then what is the best bound I can achieve for a sum of iid variables, without any knowledge about their variance?

**Edit.** I will explain the application in greater detail. I have a tree, at its leaves $v$ are labels $\ell(v)$ with values from the interval $[-1,1]$. I want to know whether these values sum to zero, but summing them up would take too long, because there are too many of them. However, I can easily do a random walk from the root to a leaf. Viewing the tree as a decision tree this way, let $p(v)$ be the probability of each leaf $v$. I then sample a couple of leaves $v\_1,\ldots,v\_n$ and compute the values $\tfrac{\ell(v\_i)}{P\cdot p(v\_i)}$, where $P$ is an upper bound for $\tfrac{1}{p(v)}$. Under the null hypthesis that the leaf lables sum to zero, the expected value of a random variable sampling this fraction is
$$\sum\_v p(v) \cdot \frac{\ell(v)}{Pp(v)} = \frac{1}{P} \sum\_v \ell(v) = 0.$$
Hence, I am in the situation of Theorem 1. I compute
$$t=\sum\_{i=1}^n \frac{\ell(v\_i)}{P\cdot p(v\_i)\cdot\sigma}$$
and by Theorem 1, $2e^{-t^2/4}$ is an upper bound for the probability that this sample was obtained under the assumption of the null hypothesis. Now, this works very well for small test instances when I compute $\sigma$ - which actually requires me to search the entire tree. For larger instances, that's exactly what I am trying to avoid, so I need something different. It would be less of a problem to use the mean or the standard deviation of my *sample*, for instance.

Note that
$$\textstyle
\sigma^2 = E(X^2)- E(X)^2 = E(X^2) = E(\sum\_{i=1}^n X\_i^2) + E(\sum\_{i\ne j} X\_i X\_j).$$
Since $X\_i$ and $X\_j$ are independent, this means $\sigma^2 = n E(X\_1^2)$. In my application, the expected value of $X\_1^2$ is so small that reasonably large sample sizes cannot negate the effect that $\sigma^2$ is very small.

**Tags:** pr.probability, st.statistics, chernoff-bound
> **Comments:**
> **username_1**: (repost of my comment at math.stackexhange.)  I think I misinterpreted your question, so I deleted my comments below (saying that, given no information about the variance, Chernoff bounds are the best you can do). Can you clarify two points?  (1) Are you seeking a bound to *analyze* an algorithm, or to use *within* an algorithm (somehow along with sampling)?  (2) You mentioned somewhere that in your case $\sigma << 1$.  Why does this happen in your case?  (For any fixed distribution on the $X_i$, the variance of their sum has to grow linearly with $n$ as $n\rightarrow\infty$, right?)  Thanks.  
> **username_0**: I have tried to explain my application in greater detail in my above edit. I cannot tell you precisely why $\sigma$ is so small in my application, it's merely an empirical observation so far. I think that the values $\ell(v)$ might actually come from an intervall much terser around $0$, but I can't be sure. If I let $n$ grow large enough to negate that effect, the method becomes infeasable, from what I can tell even for small instances.  
> **username_1**: Thanks. Do you need to tell whether the sum is exactly zero, or just *near* zero (and if so, critically, *how near*)?  (The first seems impossible without more information.  Consider the setting where either all leaves have $\ell(v) = 0$, or all but one has $\ell(v)=0$.  This setting fits your description, but you cannot hope to determine whether $\sum_v \ell(v) = 0$ without sampling enough to cover all leaves.)  
> **username_1**: Do you mean to imply that $|\ell(v)/p(v)|\le 1$?  (Your use of the bound seems to assume that but you state only that $|\ell(v)|\le 1$.)  
> **username_0**: I'm sorry, I forgot something important. I scale with a constant $P$ to ensure $|\ell(v)/p(v)|\le 1$, I added that. Regarding your other question, I indeed want to know whether the sum is *exactly* zero..  
> **username_1**: FWIW, the problem you describe, in general, is co-NP-hard (and actually #P-hard).  E.g., Given a Boolean formula $\Phi$, sample a random assignment to the variables, and let $\ell(v)=1$ if the assignment corresponding to $v$ satisfies $\Phi$.  Then the sum is zero iff $\Phi$ is not satisfiable.  So, if there was a poly-time algorithm for your problem (in general), you would have P=NP.  (Similarly, you would also have P=#P.  Similarly, determining the answer w.h.p. is hard.)  Is this what you are seeking?  (That is, an efficient algorithm to determine whether the sum is non-zero?)  
> **username_0**: What you say is true. That is more or less the reason *why* I am attempting a probabilistic approach, not a deterministic one. Furthermore, I am not even trying to prove that the sum *is* zero, I am only trying to discard that null hypothesis. My algorithm won't even detect all no-instances. It is one of those things that might be good in practice, though.  
> **username_1**: Thanks for clarifying.  FWIW, even a randomized algorithm can't do it in polytime with probability 1/poly(n), unless e.g. BPP=NP (which is unlikely).  Independent of complexity, in a black-box model (where you can only learn about $\ell(v)$ by querying with $v$, and $\ell:V\rightarrow \{0,1\}$ can be arbitrary) you provably can't distinguish between zero sum and non-zero sum with high probability without querying most of the leaves.  (I keep more or less repeating myself here in the comments, so perhaps I don't understand your goal in a formal sense.  I am curious though, thanks.)  

---

## 1 answers

### Answer by username_2 on 2012-11-07. Score: 2

You need McDiarmid's inequality, or in particular the [Hoeffding inequality](http://en.wikipedia.org/wiki/Hoeffding%27s_inequality#General_Case), which is a simplification:

Given $n$ independent $X\_i$ with the property that $X\_i \in [a\_i, b\_i]$, and $X = (1/n)\sum X\_i$, then

$$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b\_i - a\_i)^2}) $$

> **Comments:**
> **username_0**: Using the variable $Z=\sum_i X_i=nX$ as well as $X_i\in[-1,1]$ and $E(X_i)=0$, we have $\sum(b_i-a_i)^2=4n$ and your formula basically says $$\Pr(|Z|\ge\lambda)=\Pr(|X|\ge n^{-1}\lambda)\le 2e^{-\lambda^2/2n}.$$ However, Chernoff says $$\Pr(|Z|\ge\lambda)\le 2e^{-\lambda^2/4\sigma^2}.$$ Even with the trivial observation $\sigma\le 1$, I would achieve a bound of $2e^{-\lambda^2/4}$ (which is better than $2e^{-\lambda^2/2n}$ for $n>2$) and even that one is, by far, not good enough. Do I have any other option?  
> **username_2**: There's a variant of McDiarmid's inequality called Bernstein's inequality if you have formal bounds on the variance. In general, you should look at the Dubhashi-Panconesi book on concentration of measure.  

---

