For $x_1,...,x_n$ iid random on sphere of radius $\sqrt{d}$ in $R^d$, what is a good upper-bound on min distance of $x_{n}$ from the other $x_i$'s?

Question

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some absolute constant $\gamma>0$; i.e., $n$ is at most polynomial in $d$. Let $x_1,\ldots,x_n,x_{n+1}$ be drawn iid from the uniform distribution on the sphere $S_{d-1}(\sqrt{d})$ of radius $\sqrt{d}$ in $\mathbb R^d$, and consider the random variable $\Delta(n,d) := \min_{1 \le i \le n}\|x_{n+1}-x_i\|$. Let $\alpha \in (0,1)$.

Question. What is a good upper-bound for $\Delta(n,d)$, perhaps valid with probability at least $\alpha$ ?

One would expect $\Delta(n,d)=o(\sqrt{d})$, i.e., $\Delta(n,d)/\sqrt{d} \to 0$ in the limit $d \to \infty$ w.h.p.

A crude (and possibly very bad) estimate

Because the sphere $S_{d-1}(\sqrt{d})$ can be covered with $N_d(\varepsilon) \le (\sqrt{d}/\varepsilon)^d$ (euclidean) balls of radius $\varepsilon$, it is clear that $\Delta(n,d) \le \sqrt{d}/n^{1/d} \asymp \sqrt{d}$ with probability tending to $1$ with $d$. However, this bound is very far from my target, namely $o(\sqrt{d})$.

Answer 1

$\newcommand{\De}{\Delta}\newcommand{\R}{\mathbb R}\newcommand{\ga}{\gamma}\newcommand{\Ga}{\Gamma}$This is to provide a detalization on Will Sawin's comment. Specifically, let us show that the best upper bound on $\De:=\De(n,d)$ is $\sim\sqrt{2d}$ (as $d\to\infty$ and $d^\ga\ge n\to\infty$).

Indeed, for real $m>0$, let \begin{equation*} p:=P(\De>m)=P(\min_{1\le i\le n}\|x_{n+1}-x_i\|>m). \tag{1}\label{1} \end{equation*} We want to choose $m$ so that $p$ be bounded away from $0$. In other words, writing \begin{equation*} p=e^{-u}, \end{equation*} we want to choose $m$ so that $$u=O(1).$$

Let $e_1:=(1,0,\dots,0)\in\R^d$. Note that $x_1/\sqrt d$ equals $G/\|G\|$ in distribution, where $G=(G_1,\dots,G_n)$ is a standard Gaussian random vector in $\R^d$. So, by spherical symmetry, \begin{equation*} \begin{aligned} e^{-u}=p&=P(\min_{1\le i\le n}\|\sqrt d\, e_1-x_i\|>m) \\ &=P(\|\sqrt d\, e_1-x_1\|>m)^n \\ &=P\Big(1-\frac{e_1\cdot x_1}{\sqrt d}>\frac{m^2}{2d}\Big)^n \\ &=P\Big(1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big)^n \\ \end{aligned} \end{equation*} where $e_1:=(1,0,\dots,0)\in\R^d$ and $\cdot$ is the dot product. So, \begin{equation*} P\Big(1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big)=e^{-u/n}=1-(1+o(1))\frac un. \tag{2}\label{2} \end{equation*} If $m\ge\sqrt{2d}$, then $P\big(1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\big)\le P(G_1<0)=1/2$, which contradicts \eqref{2} for all large enough $n$. So, without loss of generality, \begin{equation*} 0< m<\sqrt{2d} \tag{3}\label{3} \end{equation*} and hence \begin{equation*} \begin{aligned} &P\Big(1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ &=P\Big(G_1<0,1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ &+P\Big(G_1>0,1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big) \\ &=P(G_1<0)+P\Big(G_1>0,1-\frac{|G_1|}{\|G\|}>\frac{m^2}{2d}\Big) \\ & =\frac12+\frac12\,P\Big(1-\frac{|G_1|}{\|G\|}>\frac{m^2}{2d}\Big). \end{aligned} \end{equation*} So, \begin{equation*} P\Big(1-\frac{G_1}{\|G\|}>\frac{m^2}{2d}\Big)=\frac12+\frac12\,P(Y>z), \end{equation*} where \begin{equation*} Y:=1-\frac{G_1^2}{\|G\|^2},\quad z:=1-\Big(1-\frac{m^2}{2d}\Big)^2. \tag{4}\label{4} \end{equation*} So, in view of \eqref{2}, $P(Y>z)=1-(2+o(1))\frac un$, that is,
\begin{equation*} P(Y\le z)\sim\frac{2u}n\ge\frac{2u}{d^\ga}. \tag{5}\label{5} \end{equation*} Next, $Y$ has the beta distribution with parameters $\frac{d-1}2,\frac12$. So, for \begin{equation*} c_d:=\frac{\Ga(d/2)}{\Ga(1/2)\Ga((d-1)/2)}\sim\sqrt{\frac{d}{2\pi}}, \tag{6}\label{6} \end{equation*} we have \begin{equation*} \begin{aligned} P(Y\le z)&=c_d \int_0^z y^{(d-3)/2}(1-y)^{-1/2}\,dy \\ &\le c_d z^{(d-3)/2}\int_0^z (1-y)^{-1/2}\,dy \\ &\le 2c_d z^{(d-1)/2}. \end{aligned} \tag{7}\label{7} \end{equation*} By \eqref{4}, \eqref{3}, \eqref{7}, \eqref{5}, and \eqref{6}, \begin{equation*} 1\ge z^{(d-1)/2}\gtrsim\frac{u\sqrt{2\pi}}{d^{\ga+1/2}}, \end{equation*} which implies $z\to1$.

Thus, by \eqref{4}, $m\sim\sqrt{2d}$, as claimed.