# Chernoff Bound for sum of sub-gaussian variables via truncation method

I am trying to follow the proof here for Proposition 6 in https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/, but I cannot figure out how the computation for the final part should be done:

Each $${X_{i,m}}$$ is clearly bounded in magnitude by $${2^m}$$; from the subgaussian hypothesis one can also verify that the mean and variance of $${X_{i,m}}$$ are at most $${C' \exp( - c' 2^{2m} )}$$ for some $${C', c' > 0}$$. If $${A}$$ is large enough, an application of the Chernoff bound (11) (or more precisely, the refinement in Exercise 3) then gives (after some computation) $$\displaystyle {\bf P}( |S_{n,m}| \geq 2^{-m-1} A n ) \leq C' 2^{-m} \exp( - c' A n )$$ (say) for some $${C', c' > 0}$$, and the claim follows.

What I've tried: Each $$X_{n,m}$$ is bounded by $$K=2^m$$. We also have $$\sigma=$$ square root of the variance of $$S_{n,m} \leq \sqrt{nC'}\exp(-c'2^{2m}/2)$$. Finally define $$\lambda := 2^{-m-1} A n /\sigma$$. We apply the improved Chernoff's bound as suggested: \begin{align*} {\bf P}( |S_{n,m}| \geq 2^{-m-1} A n ) &= {\bf P}( |S_{n,m}| \geq \lambda\sigma)\\ &\leq C \max( \exp( - c \lambda^2 ), {(\lambda K/\sigma)^{-c \lambda \sigma / K}} )\\ &\leq C \max\left(\exp(-c\cdot 2^{-2m-2}A^2n\exp(c'2^{2m})/C''),(A\exp(c'2^{2m})/2C')^{-2^{-2m-1}cAn} \right)\\ &\leq C'' \exp(-c''An)(A/2C')^{-2^{-2m-1}cAn}. \end{align*} $$(A/2C')^{-2^{-2m-1}cAn}$$ tends to $$1$$ as $$m$$ is large. I cannot get the $$2^{-m}$$ factor to show up in the final step.

• I think the $\exp(-c'2^{2m})$ should be a $\exp(c'2^{2m})$. Jun 27 '20 at 23:11
• Thank you for noticing it, I've edited my typo. Jun 27 '20 at 23:46

My guess is that $$P(|S_{n,m}| \ge 2^{-m-1}An)$$ is a typo. The first piece of evidence to support my guess is that right above in the proof, one encounters $$P(|S_{n,m}| \ge \frac{A}{100(m+1)^2}n)$$. The second piece of evidence is that, as you correctly showed, the proof doesn't work with $$P(|S_{n,m}| \ge 2^{-m-1}An)$$ instead.
Let $$\lambda = \frac{1}{100(m+1)^2}\frac{An}{\sigma}$$. Then $$P(|S_{n,m}| \ge \frac{An}{100(m+1)^2}) = P(|S_{n,m}| \ge \lambda \sigma) \le C\max(\exp(-c\lambda^2),(\lambda K/\sigma)^{-c\lambda \sigma K})$$. Note $$\exp(-c\lambda^2) = \exp\left(-c\frac{1}{m^4}A^2n\exp(c'2^{2m})\right)$$ is obviously at most $$C'2^{-m}\exp(-c'An)$$. And the term that was problematic for you, i.e. $$(\lambda K/\sigma)^{-c\lambda \sigma/K}$$, is now about $$(\frac{2^m}{m^2}A\exp(c'2^{2m}))^{-c\frac{An}{m^2}2^{-m}} \approx \exp(-c\frac{An}{m^2}c'2^m)$$, which is also clearly small enough.
• Now this bound makes a lot of sense to me. $2^{-m-1}$ may be too sharp a decay for this bound to work, and $O(1/m^2)$ would work perfectly. Thanks! Jun 27 '20 at 23:54