Exercise 3.11: Concentration on the Euclidean Ball
(a)
If \(a \in A\) and \(b \in (A^\e)^\c\), then \(\norm{a - b}\ge \e\) and \(\norm{a},\norm{b} \le 1\). Hence, \begin{equation} \norm{a - b}^2 = \norm{a}^2 + \norm{b}^2 - 2 \lra{a, b} \ge \e^2, \end{equation} so \begin{equation} \norm{a + b}^2 = \norm{a}^2 + \norm{b}^2 + 2 \lra{a, b} \le 2 = 2\norm{a}^2 + 2\norm{b}^2 - \e^2 \le 4 - \e^4. \end{equation} Therefore, \begin{equation} \frac12 \norm{a + b} \le \sqrt{1 - \tfrac14 \e^4} \le 1 - \tfrac18 \e^2. \end{equation}
(b)
Use the Brunn–Minkowski inequality in the form (3.45) from the book with \(\lambda = \frac12\): \begin{equation} \vol(A)^{1/2}\vol((A^\e)^\c)^{1/2} \le \vol(\tfrac12 A + \tfrac12 (A^\e)^\c). \end{equation} If \(x \in \tfrac12 A + \tfrac12 (A^\e)^\c\), then \(\norm{a} \le 1 - \frac18 \e^2\) by (a). Hence, \begin{equation} \vol(\tfrac12 A + \tfrac12 (A^\e)^\c) \le (1 - \tfrac18 \e^2)^{n}, \end{equation} which means that \begin{equation} \vol(A)\vol((A^\e)^\c) \le (1 - \tfrac18 \e^2)^{2n}. \end{equation}
(c)
By (b) and \(\P(A) \ge \frac12\), we have \begin{equation} 1 - \P(A^\e) = \P((A^\e)^\c) \le 2 (1 - \tfrac18 \e^2)^{2n} \le 2 e^{-\tfrac14 n \e^2}, \end{equation} so \begin{equation} \alpha_{\P, B_2^n, \norm{\vardot}_2}(\e) \le 2 e^{-\tfrac14 n \e^2}. \end{equation}