I'm trying to derive an exponential tail bound like $P(X>t)<ae^{-bt}$ on a sum of independent random variables, except where the number of items in the sum grows with $t$. I can't figure it out.
More specifically, let $\{Y_i\}_{i \geq 1}$ be a sequence of iid positive integer-valued random variables. Assume that the $Y_1$ has a finite moment generating function in some neighborhood around 0. For some constants $c,c'$ I want a bound like:
$$P \left( \sum_{i=1}^{[f(t)]} Y_i > t\right) < c' \cdot \exp(-ct)$$
Question: without imposing any more assumptions, is there an easy way to see how fast can I let $f(t)$ grow and still get the exponential bound on the right-hand side?
Letting $m(s)$ be the mgf for the random variable $y$, a first shot using the Chernoff method starts like: $$P \left( \sum_{i=1}^{f(t)} Y_i > t \right) < \inf_{s>0} \left[ e^{-st} m(s)^{f(t)} \right]$$
If I try to parameterise $f(t)$ linearly by $f(t) = at$ for some $a>0$, then we get: $$P \left( \sum_{i=1}^{f(t)} Y_i > t \right) < \inf_{s>0} \left[ \frac{m(s)^a}{e^s} \right]^t$$ which makes me think that, at least with linear growth, we can't really say anything without knowing more about the mgf. Or that I'm going about this in completely the wrong way. Probably the latter.
If $f(t)=at$, then we are in precisely the realm of Cramer's Theorem. Specifically, assuming $E X_1<a^{-1}$ we have that $$P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)\le\exp(-\Lambda^*(a^{-1})t)$$ where $\Lambda(\lambda)=\log m(\lambda)$ is the log moment generating function and $\Lambda^*(x):=\sup_{\lambda\in\mathbb R}(\lambda x-\Lambda(\lambda))$ is the Legendre transform of $\Lambda$. (This much can actually be derived using your work with the Chernoff bound.) In fact, more is true: $$\lim_{t\to\infty}\frac1t\log P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)=-\Lambda^*(a^{-1}).$$ If $f$ is sublinear (i.e. $f(t)=o(t)$), we get an even better estimate asymptotic result: $$\lim_{t\to\infty}\frac1t\log P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)=-\infty.$$ This is because for any $\epsilon>0$ and sufficiently large $t$, we can dominate the probability with the corresponding probability where $f(t)$ is replaced by $\epsilon t$, so in particular we have $$\limsup_{t\to\infty}\frac1t\log P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)\le-\Lambda^*(\epsilon^{-1})$$ which tends to $-\infty$ as $\epsilon\to0$ since $\Lambda^*$ is convex. So in fact, for any $c>0$, there exists $C$ such that $$P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)\le Ce^{-ct}.$$ If however $f$ is superlinear (i.e. $t=o(f(t))$) then we are doomed. The idea is basically the same as above, except instead of looking at an upper bound with $\epsilon$ small we look at a lower bound with $M$ large. We can end up showing that $$P\left(\sum_{i=1}^{[f(t)]}X_i>t\right)\to1$$ as $t\to\infty$, so in particular we can never obtain such an upper bound.