The chi-squared moment generating function and its Chernoff bound

ProofIntermediate⏱ 30 minHigh-Dim Probabilitychi-squaredmgfchernoffjl

Problem

Let $S = \sum_{i=1}^kZ_i^2$ with $Z_i$ i.i.d. standard normal.

Show $\E e^{\lambda S} = (1-2\lambda)^{-k/2}$ for $\lambda<1/2$ .
Derive the upper tail bound $\P(S \ge (1+\eps)k) \le \exp\big(\tfrac k2(\log(1+\eps)-\eps)\big)$ .
Show the exponent is at most $-k\eps^2/8$ for $\eps\in(0,1)$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 3 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Johnson–Lindenstrauss dimension arithmetic	High-Dim Probability	Numerical	Beginner	15 min
Derive Hoeffding's inequality from Hoeffding's lemma	High-Dim Probability	Proof	Intermediate	30 min
From distance preservation to inner-product preservation	High-Dim Probability	Proof	Intermediate	30 min
Implement random projection and measure the distortion run	High-Dim Probability	Coding	Intermediate	1 hour
Massart's finite maximal inequality	Learning Theory	Proof	Advanced	30 min