# Tail bounds for sample means of i.i.d random variables where the moment generating function exists

I want to figure out the proof of Lemma 4 in the following paper. The lemma states that

I can only deduce the generic Chernoff bound but can do no better. I don't know if this bound is the best we can do or if its relaxed for applications.

EDIT: I know, using Markov's inequality, that $$P\left(\left\lvert\overline{Y}_m\right\rvert>\delta\right)\leq \left(M_Y(\delta)\right)^me^{-m\delta^2}$$ where $$M_Y(\delta):=\mathbb{E}\left[e^{\delta Y}\right]$$ is the moment generating function evaluated at $$\delta$$. However, this is not a uniform bound that holds asymptotically. I am sure I am missing something trivial here but it evades me.

• The paper is behind paywall, can you add a screenshot here? Commented May 14 at 22:19
• By the way, how do you reach the inequality $P[|\overline{Y}_m| > \delta] \leq (M_Y(\delta))^me^{-m\delta^2}$ by Markov's inequality? It seems that in order to get "$m^2$" in the exponent, we must consider the MGF of $Y^2$ instead of $Y$. Commented May 15 at 0:16
• There is no $m^2$ in the exponent? There's a $\delta^2$ that comes in because you go from the mean to the sum (and then to the product of MGFs since the sum is of iid RVs) Commented May 18 at 4:27
• @Yashaswi_Mohanty Yes, I meant $\delta^2$... What I get by Markov's inequality is that $$P(|\sum_{i = 1}^m Y_i| > m\delta) = P(\sum_{i = 1}^m Y_i > m\delta) + P(\sum_{i = 1}^m Y_i < -m\delta) \leq \cdots,$$ so how $\delta$ is raised to $\delta^2$? Commented May 18 at 4:38
• $P(\bar{Y_m} > \delta) = P(m \bar{Y_m} > m \delta) = P(m \bar{Y_m} \delta > m \delta^2) = P(e^{m\bar{Y_m} \delta} > e^{m\delta^2} )...$. Something along those lines... The screenshot of the Lemma is now up. It's identical to the Tex'ed up version from earlier Commented May 18 at 4:44