Sufficient Condition for Exponential Decay in Chernoff Bound (Large Deviations)

Let $X_i$ ($i=1,...,n$) be a sequence of independent and identically distributed random variables. Denote $\mu=\mathbb{E}[X_i]$ and $S_n=\frac{1}{n}\sum_{i=1}^nX_i$. This question concerns the tail probability $\Pr[S_n \ge \mu+\epsilon]$, where $\epsilon>0$ is a constant.

In the case that $|X_i|$ is bounded with probability one, Hoeffding's Inequality states that the tail probability decays to exponentially fast in $n$ for any $\epsilon > 0$. [EDIT: The paper http://arxiv.org/pdf/1209.6396v1.pdf (Theorem 1.1) used to state a theorem which made it seem that finite variance was sufficient, but this is not true, and the paper has now been edited to state the sufficient condition more precisely].

A more general sufficient condition is that each variable is sub-Gaussian - see Exercise 6 of http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/

With no assumptions at all on $X_i$, the probability may fail to decay exponentially. For example, under the Cauchy distribution (which has no first or second moment), the probability is bounded away from zero. However, is there a sufficient condition which is less restrictive than that of boundedness?

This question is related to Large Deviations Theory and the Chernoff bound. The following upper bound is straightforward:

$$\Pr[S_{n}\ge\mu+\epsilon]=\Pr[e^{\tau\sum_{i=1}^{n}X_{i}}\ge e^{\tau n(\mu+\epsilon)}]\le\frac{\mathbb{E}[e^{\tau\sum_{i=1}^{n}X_{i}}]}{e^{\tau n(\mu+\epsilon)}}=\frac{\mathbb{E}[e^{\tau X_{1}}]^{n}}{e^{\tau n(\mu+\epsilon)}}$$

where $\tau$ is an arbitrary positive constant, and the inequality is Markov's inequality. For the optimal $\tau$, and under some technical assumptions, one can obtain a lower bound with the same exponential behavior (see "Large Deviations Techniques and Applications" by Dembo/Zeitouni).

Is there a simple sufficient condition for the above Chernoff bound to decay exponentially, which is stronger than boundedness or sub-Gaussian?

[EDITED SINCE ORIGINAL POST - The original answer of "no" was in response to the questions "Does a bounded absolute first moment suffice?". I certainly agree with this answer of no, but I am still interested in finding a condition as general possible]

-
en.wikipedia.org/wiki/… – Steve Huntsman Nov 29 '12 at 14:24
I don't now if I understand your question correctly, but the answer seems to be a straightforward no. Existence of a finite expectation does not imply finite higher moments (and thus for sure not exponential moments). On the other hand, if some exponential moment exists, the decay is clearly exponential, no? – Stephan Sturm Nov 29 '12 at 17:25
Thanks for the replies. I don't fully understand your answer Stephan. First, can one always say that an unbounded second moment implies an unbounded exponential moment? The function x^2 is much lower than e^x for large positive values, but not for negative values. Also, why is the existence of an exponential moment sufficient? Don't we still need to prove that the chernoff bound behaves as a^n for some a with magnitude less than 1? Otherwise the Chernoff bound just bounds the probability by 1, which is trivial. – jmscarlett Nov 29 '12 at 23:10
I did not intend to provide an explicit counterexample, just a line of thought. But if you want to go further, take just the lognormal distribution: It has all finite moments, but no positive exponential one. The Chernoff bound is trivial 1. – Stephan Sturm Nov 29 '12 at 23:42
For the second part, it is true that $\tau$ may depend on $n$. But as we choose it for a given $n$ optimally, it follows that for all other $n$ it gives a weaker bound. But as this weaker bound decays exponentially, the optimal Chernoff bound can decay asymptotically only faster than exponentially. – Stephan Sturm Nov 29 '12 at 23:53

Note that Cramer's theorem applies in dimension 1 w/out any moment assumptions, but of course the rate function may vanish (for this version see theorem 2.2.3 in Dembo-Zeitouni). So the question is equivalent to the question when does the rate function vanish'' (the rate function is $\sup_{\lambda\in R} (\lambda x-\Lambda(\lambda))$, where $\Lambda(\lambda)= \log E(e^{\lambda X_1}))$. So if $\Lambda(\lambda)=\infty$ for all $\lambda\neq 0$, clearly there is no exponential convergence, not just a failure of the upper bound.

-

Theorem 1.1. in the paper is clearly false - for something like that to be true (two sided bound), usually one requires the variables to be bounded from both sides with probability 1 and then information about the variance gives you more information. Also, it would be enough that the generating function of each X_i is bounded by a generating function of some normal random variable (i.e. all X_i's are sub-Gaussian).

Counterexample for Theorem 1.1: Assume n=1 and EX=0 we, by Chebyshev's inequality P(|X|>x) < VarX/x^2 and it is optimal since the symmetric random variable that takes the values {-x,0,x} with P(X=x)=VarX/(2x^2) provides the equality. Theorem 1.1. would imply that VarX/x^2 is bounded above by an exponential function in x for all x, which is not the case.

In general it is known that if X_i have only second moments then you will not get a bound of better order than Var(X_1+...+X_n)/x^2 for large x for the probability in question. Please let me know if you want me to expand on this.

-
The proof of Thm 1.1 on page 5 says it only works for small enough $\alpha$, but the statement of Thm 1.1 has no such restriction. Has anyone tried contacting the author for an explanation? – Brendan McKay Feb 18 '13 at 12:10
I did - the correction is already made: cs.utah.edu/~jeffp/teaching/cs5955/L3-Chern-Hoeff.pdf – TOM Feb 19 '13 at 3:40
Thanks. I agree bounded variance does not suffice, and perhaps a bounded k-th moment doesn't suffice for any value of k. Perhaps a bounded k-th moment for all values of k would suffice, but I'm not sure. A more general sufficient condition that boundedness is that the variables are sub-Gaussian - see Exercise 6 of terrytao.wordpress.com/2010/01/03/… – jmscarlett Feb 19 '13 at 9:14