High-Dim Geometry & Concentration

Concentration of measure quantifies how fast random quantities cluster around their mean, while high-dimensional geometry reveals counter-intuitive facts about $\mathbb{R}^d$. Three core inequalities: Markov (non-negative $X$, $a>0$): $P(X \ge a) \le \frac{\mathbb{E}[X]}{a}$;Chebyshev ($k>0$): $P(|X-\mu| \ge k\sigma) \le \frac{1}{k^2}$;Hoeffding (independent $X_i \in [0,1]$): $P(\bar{X}_n - \mu \ge t) \le e^{-2nt^2}$, decaying exponentially in $n$. Thin shell intuition: the $d$-ball volume scales as $r^d$, and a ball of radius $1-\frac{1}{d}$ holds only about $(1-\frac{1}{d})^d \approx e^{-1} \approx 37\%$ of the volume — roughly 63% lies in a shell of thickness $O(1/d)$; random unit vectors $u,v \in \mathbb{R}^d$ have dot-product variance about $1/d$, i.e. magnitude $O(1/\sqrt{d})$ — high-dimensional vectors are nearly pairwise orthogonal, which is exactly why attention divides by $\sqrt{d_k}$.

proving generalization bounds (ERM uniform convergence, PAC), random projections (Johnson-Lindenstrauss), high-dimensional initialization and gradient variance analysis, differential privacy mechanisms; interview questions like "prove Hoeffding" and "what happens in high dimensions" come from here.

Chebyshev only needs the second moment but is loose ($1/k^2$) and cannot answer how fast convergence in $n$ happens; exponential bounds such as Hoeffding give a provable $e^{-2nt^2}$ decay under independence and boundedness, turning "convergence in probability" into an actionable rate. Markov has the weakest assumptions (non-negativity plus a first moment) and is the source of Chebyshev and all sharper concentration inequalities.

State Markov, Chebyshev and Hoeffding, with the conditions each requires?

Derive Chebyshev from Markov? Why is Chebyshev tighter?

Why does Hoeffding decay exponentially? Which one is used in ERM/PAC generalization bounds?

What is the thin shell phenomenon? Why does the volume of a high-dimensional unit ball concentrate near the shell?

Why are high-dimensional random unit vectors nearly orthogonal? Dot-product magnitude? Link to attention scaling?