Exercise 6.14: Random Sphere Packings
We will use the probabilistic method. Assume \(\theta_1 , \ldots , \theta_M\) are i.i.d. \(\Unif(S^{d-1})\). Simple algebra yields the equivalency \begin{align} \| \theta_i - \theta_j \|_2 \leq \tfrac{1}{2} \iff \langle \theta_i , \theta_j \rangle \geq \tfrac{7}{8} \, . \end{align}
Denote \(x = \langle \theta_i, \theta_j \rangle\). It is possible to show \((x + 1) / 2 \sim \Beta(\frac{d - 1}{2}, \frac{d - 1}{2})\). Moreover, it holds that any \(\Beta(\alpha, \alpha)\) distributed random variable is sub-Gaussian with parameter \(\frac{1}{4(2\alpha + 1)}\), implying \begin{align} \P (\| \theta_i - \theta_j \|_2 \leq \tfrac{1}{2}) \leq \exp \biggl\lbrace - \frac{4^2}{2} \biggl( \frac{1 + \tfrac{7}{8}}{2} \biggr)^2 d^2 \biggr\rbrace = e^{-\frac{225}{32} d^2} \, , \end{align} which gives an upper bound on the probability of (a) being violated.
Moving to the condition (c), we use the result of Example 6.21 from the book. In particular, we see that for the covariance \(\hat{\Sigma}\) from the example \begin{align} \frac{1}{d} \hat{\Sigma} = \frac{1}{M} \sum_i \theta_i \theta_i^\top \, , \end{align} and therefore the inequality in (c) reduces to \(2 \leq \| \hat{\Sigma} \|_2 \leq \| \hat{\Sigma} - I \|_2 + \| I \|_2\), i.e., the probability of (c) being violated is upper bounded by \begin{align} \P (\| \hat{\Sigma} - I \|_2 \geq 1) \leq 2d e^{- \frac{M}{4d}} \, . \end{align}
Putting everything together, the probability of conditions (a) and (c) being satisfied is lower bounded by \begin{align} \textstyle 1 - \tfrac{M^2}{2} \P(\| \theta_1 - \theta_j \|_2 \leq \tfrac{1}{2} ) - \P (\| \tfrac{1}{M} \sum_i \theta_i \theta_i^\top \|_2 > \tfrac{2}{d}) \geq 1 - \tfrac{1}{2}e^{2cd - \frac{225}{32}d^2} - 2d e^{- \frac{e^{cd}}{4d}} \, , \end{align} where we substituted \(M = e^{cd}\). One can check that the r.h.s. is strictly larger than zero for \(c = \frac{13}{10}\) and all \(d \geq 1\).