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.

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?

share|improve this question
    
The maximum value of the variance of a random variable taking on values in $[-1,+1]$ almost surely is $1$ and occurs when the random variable is discrete, taking on values $\pm 1$ with equal probability $\frac{1}{2}$. Perhaps this fact can help. –  Dilip Sarwate Nov 6 '12 at 21:19
    
Unfortunately, the variance will in most cases be very close to zero, smaller than $10^{-10}$ just to give you an idea. I have computed it in some cases, and the computation works very good when I can use it with the Chernoff bound. In fact, I have already tried the estimate $\sigma^2\le 1$, and the result is disastrous for the algorithm. –  Jesko Hüttenhain Nov 6 '12 at 22:44
    
I deleted my answer below since I think I misinterpreted your question. (The answer said just 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) How can $\sigma$ be so small? For any fixed distribution on the $X_i$, the variance of their sum has to grow linearly with $n$ as $n\rightarrow\infty$, right? –  Neal Young Nov 7 '12 at 19:00
    
What happened with this question? –  Did Jan 14 '13 at 11:53
1  
Reposted at mathoverflow.net/questions/127887/… . –  user66151 Apr 18 '13 at 9:01
show 2 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.