Skip to main content
MathOverflow

Return to Question

added 9 characters in body
Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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})$.

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 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})$.

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})$.

edited title
Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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

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 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})$.

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+1}$ from the other $x_i$'s?

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some $\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 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})$.

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?

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 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})$.

Source Link
dohmatob
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

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+1}$ from the other $x_i$'s?

Let $n$ and $d$ be large positive integers with $n \le d^\gamma$, for some $\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 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})$.