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]
Best Answer
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.