HDS

Exercise 6.14: Random Sphere Packings

chapter 6

We will use the probabilistic method. Assume θ1,,θM are i.i.d. Unif(Sd1). Simple algebra yields the equivalency (1)θiθj212θi,θj78.

Denote x=θi,θj. It is possible to show (x+1)/2Beta(d12,d12). Moreover, it holds that any Beta(α,α) distributed random variable is sub-Gaussian with parameter 14(2α+1), implying (2)P(θiθj212)exp{422(1+782)2d2}=e22532d2, 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 Σ^ from the example (3)1dΣ^=1Miθiθi, and therefore the inequality in (c) reduces to 2Σ^2Σ^I2+I2, i.e., the probability of (c) being violated is upper bounded by (4)P(Σ^I21)2deM4d.

Putting everything together, the probability of conditions (a) and (c) being satisfied is lower bounded by (5)1M22P(θ1θj212)P(1Miθiθi2>2d)112e2cd22532d22deecd4d, where we substituted M=ecd. One can check that the r.h.s. is strictly larger than zero for c=1310 and all d1.

Published on 17 March 2021.