3
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – 61plus
    Jun 27 '20 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.