Exercise 6.14: Random Sphere Packings

chapter 6

We will use the probabilistic method. Assume $θ_{1}, \dots, θ_{M}$ are i.i.d. $Unif (S^{d - 1})$ . Simple algebra yields the equivalency $\begin{array}{r} (1) & ‖ θ_{i} - θ_{j} ‖_{2} \leq \frac{1}{2} ⟺ ⟨ θ_{i}, θ_{j} ⟩ \geq \frac{7}{8} . \end{array}$

Denote $x = ⟨ θ_{i}, θ_{j} ⟩$ . It is possible to show $(x + 1) / 2 \sim Beta (\frac{d - 1}{2}, \frac{d - 1}{2})$ . Moreover, it holds that any $Beta (α, α)$ distributed random variable is sub-Gaussian with parameter $\frac{1}{4 (2 α + 1)}$ , implying $\begin{array}{r} (2) & P (‖ θ_{i} - θ_{j} ‖_{2} \leq \frac{1}{2}) \leq \exp {- \frac{4^{2}}{2} (\frac{1 + \frac{7}{8}}{2})^{2} d^{2}} = e^{- \frac{225}{32} d^{2}}, \end{array}$ 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{Σ}$ from the example $\begin{array}{r} (3) & \frac{1}{d} \hat{Σ} = \frac{1}{M} \sum_{i} θ_{i} θ_{i}^{⊤}, \end{array}$ and therefore the inequality in (c) reduces to $2 \leq ‖ \hat{Σ} ‖_{2} \leq ‖ \hat{Σ} - I ‖_{2} + ‖ I ‖_{2}$ , i.e., the probability of (c) being violated is upper bounded by $\begin{array}{r} (4) & P (‖ \hat{Σ} - I ‖_{2} \geq 1) \leq 2 d e^{- \frac{M}{4 d}} . \end{array}$

Putting everything together, the probability of conditions (a) and (c) being satisfied is lower bounded by $\begin{array}{r} (5) & 1 - \frac{M^{2}}{2} P (‖ θ_{1} - θ_{j} ‖_{2} \leq \frac{1}{2}) - P (‖ \frac{1}{M} \sum_{i} θ_{i} θ_{i}^{⊤} ‖_{2} > \frac{2}{d}) \geq 1 - \frac{1}{2} e^{2 c d - \frac{225}{32} d^{2}} - 2 d e^{- \frac{e^{c d}}{4 d}}, \end{array}$ where we substituted $M = e^{c d}$ . One can check that the r.h.s. is strictly larger than zero for $c = \frac{13}{10}$ and all $d \geq 1$ .

Published on 17 March 2021.