3
$\begingroup$

This is a repost of a question at math.stackexchange, 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:

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

Improve this question
$\endgroup$
8
  • $\begingroup$ (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. $\endgroup$
    – Neal Young
    Commented Nov 7, 2012 at 19:04
  • $\begingroup$ 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. $\endgroup$
    – Jesko Hüttenhain
    Commented Nov 7, 2012 at 21:12
  • $\begingroup$ 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.) $\endgroup$
    – Neal Young
    Commented Nov 7, 2012 at 22:59
  • $\begingroup$ 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$.) $\endgroup$
    – Neal Young
    Commented Nov 7, 2012 at 23:09
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Neal Young
    Commented Nov 8, 2012 at 16:14

1 Answer 1

Reset to default
2
$\begingroup$

You need McDiarmid's inequality, or in particular the Hoeffding inequality, 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}) $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jesko Hüttenhain
    Commented Nov 7, 2012 at 14:58
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Nov 7, 2012 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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