Lecture 4: Tails of Random Variables
Sub-Gaussian behavior, Chernoff bounds, and robust means
High-dimensional statements often reduce to two one-dimensional tasks: control the tail of one random variable, and then make that control survive a union over many variables. Exponential moments are designed for exactly this job.
1 The Chernoff method
For every random variable \(X\), every \(t\in\mathbb R\), and every \(\lambda>0\), Markov’s inequality gives \[ \mathbb P\{X\geq t\} =\mathbb P\{e^{\lambda X}\geq e^{\lambda t}\} \leq e^{-\lambda t}\mathbb Ee^{\lambda X}. \] We then choose \(\lambda\) to make the bound as small as possible. This simple argument is the Chernoff method.
Definition 1 (Sub-Gaussian random variable) A mean-zero random variable \(X\) is sub-Gaussian with variance proxy \(\sigma^2\) if \[ \mathbb Ee^{\lambda X} \leq \exp\left(\frac{\sigma^2\lambda^2}{2}\right) \qquad\text{for every }\lambda\in\mathbb R. \]
Proposition 1 (Sub-Gaussian tail bound) If \(X\) is sub-Gaussian with variance proxy \(\sigma^2\), then \[ \mathbb P\{|X|\geq t\} \leq 2\exp\left(-\frac{t^2}{2\sigma^2}\right) \qquad(t\geq0). \]
For \(\lambda>0\), Chernoff’s method gives \[ \mathbb P\{X\geq t\} \leq \exp\left(-\lambda t+\frac{\sigma^2\lambda^2}{2}\right). \] The exponent is minimized at \(\lambda=t/\sigma^2\), which gives \(e^{-t^2/(2\sigma^2)}\). Apply the same argument to \(-X\) and use a union bound.
The adjective “sub-Gaussian” describes the tail scale, not the distribution. A bounded random variable, a Rademacher sign, and many nonlinear functions of independent variables can all have Gaussian-type tails.
2 Worked example: Binomial and Poisson tails
Where does a variance proxy actually come from in practice? A concrete example is the sum of independent Bernoullis, which interpolates between Gaussian and Poisson behavior depending on how far out in the tail you look.
Theorem 1 (A Poisson-type tail bound) Let \(X=\sum_{i=1}^nB_i\) for independent Bernoulli variables \(B_i\sim\operatorname{Ber}(p_i)\), not necessarily identical, and let \(\mu=\mathbb EX=\sum_ip_i\). Then for every \(t\geq\mu\), \[ \mathbb P\{X\geq t\}\leq\left(\frac{e\mu}{t}\right)^te^{-\mu}. \]
For \(\lambda\geq0\), \[ \mathbb Ee^{\lambda X}=\prod_{i=1}^n\big(1+p_i(e^\lambda-1)\big) \leq\prod_{i=1}^n\exp\big(p_i(e^\lambda-1)\big) =\exp\big(\mu(e^\lambda-1)\big), \] using \(1+x\leq e^x\). Chernoff’s method gives \[ \mathbb P\{X\geq t\}\leq\exp\big(-\lambda t+\mu(e^\lambda-1)\big) \qquad\text{for every }\lambda\geq0. \] The right side is minimized at \(\lambda=\log(t/\mu)\geq0\) (valid since \(t\geq\mu\)), which gives \[ \exp\big(t-\mu-t\log(t/\mu)\big)=\left(\frac{e\mu}{t}\right)^te^{-\mu}. \]
Far out in the tail (\(t\gg\mu\)), this bound decays like \(\exp(-t\log t)\) — heavier than any quadratic exponent can capture, and the reason a Poisson or Binomial variable is not globally sub-Gaussian. But close to the mean, the same bound is Gaussian.
Lemma 1 (Moderate deviations look Gaussian) There is an absolute constant \(\delta>0\) such that, for \(0\leq t\leq\delta\mu\), \[ \mathbb P\{X\geq\mu+t\}\leq\exp\left(-\frac{t^2}{4\mu}\right), \] and consequently \(\mathbb P\{|X-\mu|\geq t\}\leq2\exp(-t^2/4\mu)\) for \(0\leq t\leq\delta\mu\).
Write \(t=\mu u\) for small \(u\geq0\) in the exponent from Theorem 1. Taylor expanding \(\log(1+u)\) at \(u=0\) gives \[ t-\mu-t\log(t/\mu)=-\mu\big(u\log(1+u)-u\big)=-\frac{\mu u^2}{2}+O(\mu u^3). \] Substituting back \(t=\mu u\) turns \(\mu u^2/2\) into \(t^2/2\mu\), and the error term is \(O(t^3/\mu^2)=O(t^2/\mu)\), which is small enough to weaken \(t^2/2\mu\) to \(t^2/4\mu\) once \(t\leq\delta\mu\) for a small enough absolute constant \(\delta\). Apply the same argument with \(B_i\) replaced by \(1-B_i\) for the lower tail.
So a Poisson or Binomial variable is genuinely sub-Gaussian in a moderate-deviations window around its mean, and only develops a heavier, non-Gaussian tail once the deviation becomes comparable to \(\mu\) itself.
This heavier tail is not just a weakness of our bound: a Poisson or Binomial variable genuinely is this heavy once you leave the moderate-deviations window, so it is not sub-Gaussian globally.
3 Bounded variables and sums
Lemma 2 (Hoeffding’s lemma) If \(a\leq X\leq b\) almost surely, then \[ \mathbb E\exp\big(\lambda(X-\mathbb EX)\big) \leq \exp\left(\frac{\lambda^2(b-a)^2}{8}\right) \] for every \(\lambda\in\mathbb R\).
After an affine rescaling it suffices to treat \(0\leq X\leq1\). Convexity of \(x\mapsto e^{\lambda x}\) places its graph below the chord joining its values at \(0\) and \(1\): \[ e^{\lambda x}\leq 1+x(e^\lambda-1). \] Taking expectations bounds the moment generating function by that of a Bernoulli variable with the same mean. A one-variable calculus estimate for the centered Bernoulli moment generating function yields \(\exp(\lambda^2/8)\). Undoing the rescaling proves the claim.
Bounded variables are automatically sub-Gaussian this way, with a variance proxy determined only by their range. Lecture 5 shows that sums of independent sub-Gaussians add variance proxies; combining that fact with Hoeffding’s lemma above produces Hoeffding’s inequality for sums of independent bounded variables, and lets us compare this range-based proxy to the true variance in the Bernoulli case.
4 Maxima and the cost of many comparisons
If \(X_1,\ldots,X_m\) satisfy \(\mathbb P\{|X_i|\geq t\}\leq2e^{-t^2/K^2}\), no independence is required for the union bound \[ \mathbb P\left\{\max_{i\leq m}|X_i|\geq t\right\} \leq2m e^{-t^2/K^2}. \] The natural scale of the maximum is therefore \(K\sqrt{\log m}\). This is the tail version of the finite-set Gaussian-width calculation from Lecture 3.
5 Median-of-means
The ordinary empirical mean has excellent concentration for sub-Gaussian data. What if we assume only finite variance?
Chebyshev’s inequality alone gives \(\mathbb P\{|\overline X_N-\mu|>\delta\}\leq\sigma^2/(N\delta^2)\) for the plain empirical mean \(\overline X_N\), and without further moment assumptions this cannot be improved: there exist mean-\(\mu\), variance-\(\sigma^2\) distributions for which the plain mean really does deviate by \(\delta\) with probability of order \(1/N\), however large \(N\) is taken. Finite variance alone buys only polynomial confidence in \(N\), not the exponential, \(\log(1/\delta)\)-type confidence that sub-Gaussian data gives for free. Median-of-means recovers exponential confidence, at the cost of only a constant factor in accuracy.
Let \(X_1,\ldots,X_N\) be independent with mean \(\mu\) and variance at most \(\sigma^2\). Divide them into \(k\) blocks of equal size \(m=\lfloor N/k\rfloor\), form the mean in each block, and take the median of the block means. Call the result \(\widehat\mu_{\mathrm{mom}}\).
Theorem 2 (Median-of-means estimate) There are universal constants \(C,c>0\) such that \[ \mathbb P\left\{ |\widehat\mu_{\mathrm{mom}}-\mu| >C\sigma\sqrt{\frac{k}{N}} \right\} \leq2e^{-ck}. \] Thus choosing \(k\asymp\log(1/\delta)\) yields error \[ O\left(\sigma\sqrt{\frac{\log(1/\delta)}{N}}\right) \] with probability at least \(1-\delta\), under only a variance assumption.
A block mean \(\overline X_j\) has variance at most \(\sigma^2/m\). By Chebyshev, \[ \mathbb P\{|\overline X_j-\mu|>2\sigma/\sqrt m\}\leq\frac14. \] The median can be bad only if at least half of the block means are bad. The bad-block indicators are independent Bernoulli variables with means at most \(1/4\). A Chernoff bound shows that the probability of at least \(k/2\) bad blocks is at most \(2e^{-ck}\). Since \(m\asymp N/k\), the stated error scale follows.
Median-of-means separates two tasks: averaging within blocks controls scale, and taking a median across blocks amplifies confidence. Fixing \(k=\lceil\sqrt N\rceil\) blocks gives a single estimator with failure probability \(2e^{-c\sqrt N}\to0\) and no free parameter to tune; letting \(k\) grow with the desired confidence \(\log(1/\delta)\), as in Theorem 2, is what turns this into an estimator with a genuinely tunable confidence level.
6 A discrepancy example
Let \(a_1,\ldots,a_n\in[-1,1]^d\). Choose independent Rademacher signs \(\varepsilon_i\in\{-1,1\}\). For each coordinate \(j\), \[ \sum_{i=1}^n\varepsilon_i a_{ij} \] is sub-Gaussian with variance proxy at most \(n\). Hence \[ \mathbb P\left\{ \left\|\sum_{i=1}^n\varepsilon_i a_i\right\|_\infty>t \right\} \leq2d\exp\left(-\frac{t^2}{2n}\right). \] Taking \(t=\sqrt{2n\log(4d)}\) makes the right-hand side at most \(1/2\). Therefore there exists a deterministic signing such that \[ \left\|\sum_{i=1}^n\varepsilon_i a_i\right\|_\infty \leq\sqrt{2n\log(4d)}. \] This is a typical probabilistic-method argument: concentration proves the existence of a good deterministic combinatorial object. The same combination — a sub-Gaussian tail bound followed by a union bound over a well-chosen net — is what drives discrepancy bounds for random point sets, developed in Lecture 5.
7 Where we go next
Sub-Gaussian estimates are strongest when all fluctuations occur on a single quadratic scale. Products, squares, and many matrix quantities have heavier tails. Bernstein’s inequality and the \(\psi_1\) norm will extend the calculus to that setting, after which we can return to embeddings and random matrices.