4
$\begingroup$

This interesting question was asked at https://math.stackexchange.com/questions/231455/estimator-for-sum-of-independent-and-identically-distributed-iid-variables a while ago but got no answers. The original author is Jesko Hüttenhain.

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?

$\endgroup$
2
  • $\begingroup$ There's at least one mistake in the ``paper'' you refer to. Neither side depends on $n$ but for every $K$ we must have $\mathbb P\left[X > K\right] \to 1$ by the central limit theorem. If there's only one mistake the exponent in the right hand side should be $\left(2n-1\right)\frac{\lambda^2}4$ but go through it very carefully if you want to use this. Also if $|X_1|<1$ and $\mathbb E(X) = 0$ you must have $\sigma^2<1$ by Chebychev's inequality so know the variance. $\endgroup$
    – user32372
    Apr 18, 2013 at 8:13
  • $\begingroup$ Do you have a response to the answers on this page? $\endgroup$ Aug 10, 2022 at 20:11

2 Answers 2

3
$\begingroup$

I would use Hoeffding's inequality. It exploits the boundedness of the random variables (like your Theorem 1), only without the variance making an appearance, and you still get exponential decay in the probability estimate (unlike Chebyshev's inequality).

For a big-picture perspective on the different types of concentration inequalities available, check out Terry Tao's notes on the subject.

$\endgroup$
1
$\begingroup$

Inequality (4.6) in the paper at https://arxiv.org/abs/math/0701806 (a shortened version of which is at https://projecteuclid.org/euclid.aos/1176325373 ) implies, in your terms, that \begin{equation} P(|X|\ge x\sqrt n)\le\frac{2e^3}9\,P(|Z|\ge x) \le B(x):=\frac{4e^3}9\,\min\Big(\frac12,\frac1{x\sqrt{2\pi}}\Big)e^{-x^2/2} \end{equation} for $x\ge0$, where $Z\sim N(0,1)$. This bound, $B(x)$, is an improvement of Hoeffding's bound $2e^{-x^2/2}$ for $x>\frac{2e^3}{9\sqrt{2\pi}}=1.780\dots$. On the other hand, the Chebyshev bound $\frac1{x^2}$ is better (that is, smaller) than $2e^{-x^2/2}$ for $x\in(x_1,x_2)$, where $x_1=0.845\dots$ and $x_2\approx2.07\dots$, so that the bound $\min(\frac1{x^2},B(x))$ is better than Hoeffding's bound for $x>0.85$.

$\endgroup$

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.