We now setup some additional notation. Let \(A_i\)  denote the set \(B_d{\mu (S^i),\frac{1}{K^{1/d}}} \backslash { \cup _{j=0,j \ne i}^n B_d{\mu (S^j),\frac{1}{K^{1/d}}}}\)  i.e. the region in the ball \(B_d(\mu (S^i)\)  which is not contained in any of the other balls.
Let \(B_{ij}\)  denote the region of intersection between \(B_d{\mu (S^i),\frac{1}{K^{1/d}}}\)  and \(B_d{\mu (S^j),\frac{1}{K^{1/d}}}\)  where \(i\ne j\)  and \(i\)  and \(j\)  go from 0 to \(n\) . Note that set \(B_{ij}\)  is constituted of two spherical caps. By construction the centers of the intersecting spheres are at least \(\frac{1}{2n}\)  apart.
To study the properties of such a set, we define cap as the region in a \(d\)  dimensional sphere of radius \(\frac{1}{K^{1/d}}\)  which intersects with another sphere of the same radius but with centers being apart by \(1/2n\) .
From known results [1]}, the volume of cap is asymptotic to \(\text{Vol}{B_d{0,\frac{1}{K^{1/d}}}}{1-\Phi {\frac{\sqrt{d}}{2n}}}\)  as \(d \rightarrow \infty \) 
where \(\Phi \)  is the cumulative distribution function of a standard normal random variable. We therefore have that \( \lim _{d \rightarrow \infty } \text{Vol(\textbf {cap})} \sim \lim _{d \rightarrow \infty }\text{Vol}{B_d{0,\frac{1}{K^{1/d}}}}{1-\Phi {\frac{\sqrt{d}}{2n}}} = 0\) .
Furthermore, using Assumption REF , we have \(¶{(S) \in \text{cap}} \le K \text{Vol(\textbf {cap})}\sim K\text{Vol}{B_d{0,\frac{1}{K^{1/d}}}}{1-\Phi {\frac{\sqrt{d}}{n}}} \le K {\frac{1}{K^{1/d}}}^d{1-\Phi {\frac{\sqrt{d}}{n}}} = {1-\Phi {\frac{\sqrt{d}}{n}}}\)  as \(d\rightarrow \infty \) .
Since \(\Phi (t) = \mathbb {P}_{g \sim (0,1)}[g \le t]\) , we have that \(1 - \Phi (t) = \mathbb {P}_{g \sim (0,1)}[g > t] \le \frac{e^{-t^2/2}}{\sqrt{2\pi }t} \)  where the last inequality follows from standard bounds on tails of normal distribution (See Proposition 2.1.2 in [2]}). Therefore, we have \(¶{(S) \in \textbf {cap}} \lesssim \frac{ne^{-d/4n^2}}{\sqrt{d}}\) . For constant \(\epsilon >0\) , choosing \(d \gtrsim 4n^2\ln {{n/\epsilon }}\)  ensures that \(¶{(S) \in \textbf {cap}} \le \frac{\epsilon }{2n}\)  for large enough \(n\)  (to be specified later). Since \(B_{ij}\)  is made up of two conjoined caps, this gives us that for any \(j=0\)  to \(n\)  and \(i\ne j\) , we have that \(¶{(S^i)\in B_{ij}} \le \frac{\epsilon }{n}\) .
Finally, we look at \(A_i\) 's by removing the mass of all \(B_{ij}\) 's, and using a union bound, we get that \(¶{(S^i) \in A_i} = ¶{(S^i) \in B_d{\mu (S^i),\frac{1}{K^{1/d}}}} - ¶{ (S^i) \in \cup _{j=0,j\ne i}^n B_{ij}} \ge 1-4\alpha ^2 - \sum _{j=0,j\ne i}^{n} ¶{(S^i) \in B_{ij}} \ge 1-4\alpha ^2 -\epsilon \ge \frac{1}{2}-4\alpha ^2 \)  where the last inequality holds for \(\epsilon \le \frac{1}{2}\) . We now evaluate how large \(n\)  we need for this regime of \(\epsilon \) : recall that we set \(d\gtrsim 4n^2\ln {{n/\epsilon }}\) , this gives
\(\frac{ne^{-d/4n^2}}{\sqrt{d}} \le \frac{\epsilon }{2n\sqrt{ \ln {{n/\epsilon }}}}\) . We want the right hand side to be at most \(\frac{\epsilon }{2n}\)  for \(\epsilon \le 1/2\) . Plugging in this worst-case value of \(\epsilon \) , we get the condition \(\ln {(2n)} \ge 1\)  which holds for any \(n\ge 1.4\)  and therefore is valid by our assumption of \(n\) .
