Skip to main content
added 27 characters in body
Source Link
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows that the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$), which in turn (by the Archimedean projection property) has the same distribution as the first coordinate of a point draw uniformly in the unit ball in $\mathbb R^{n-1}$. Thus, $P(U_1 > \delta)$ is the probability that a random point in the unit ball in $\mathbb R^{n-2}$ lies in on given side of an equatorial hyperplane, we have for every unit-vector $z$,

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since Temme (1992) that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows that the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$), which in turn (by the Archimedean projection property) has the same distribution as the first coordinate of a point draw uniformly in the unit ball in $\mathbb R^{n-1}$. Thus, $P(U_1 > \delta)$ is the probability that a random point in the unit ball in $\mathbb R^{n-2}$ lies in on given side of an equatorial hyperplane, we have

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since Temme (1992) that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows that the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$), which in turn (by the Archimedean projection property) has the same distribution as the first coordinate of a point draw uniformly in the unit ball in $\mathbb R^{n-1}$. Thus, $P(U_1 > \delta)$ is the probability that a random point in the unit ball in $\mathbb R^{n-2}$ lies in on given side of an equatorial hyperplane, we have for every unit-vector $z$,

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since Temme (1992) that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

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

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows by symmetry that for every unit vector $z \in \mathbb R^d$, the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$), which in turn (by the Archimedean projection property) has the same distribution as the first coordinate of a point draw uniformly in the unit ball in $\mathbb R^{n-1}$. Noting thatThus, $P(U_1 > \delta)$ is the probability that a random point onin the unit ball in $n$-sphere$\mathbb R^{n-2}$ lies in on given side of an equatorial hyperplane, we have

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since [TemmeTemme (1992)][1] that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows by symmetry that for every unit vector $z \in \mathbb R^d$, the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$). Noting that $P(U_1 > \delta)$ is the probability that a random point on the unit $n$-sphere lies in on given side of an equatorial hyperplane, we have

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since [Temme (1992)][1] that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows that the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$), which in turn (by the Archimedean projection property) has the same distribution as the first coordinate of a point draw uniformly in the unit ball in $\mathbb R^{n-1}$. Thus, $P(U_1 > \delta)$ is the probability that a random point in the unit ball in $\mathbb R^{n-2}$ lies in on given side of an equatorial hyperplane, we have

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since Temme (1992) that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$

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

Here is my solution without the reduction trick to $1$D gaussian.


Let $U := X/\|X\|$. Since $U$ is uniformly distributed on the unit $n$-sphere, it follows by symmetry that for every unit vector $z \in \mathbb R^d$, the random variable $U^Tz$ has the same distribution as $U_1$ (the first coordinate of the random vector $U$). Noting that $P(U_1 > \delta)$ is the probability that a random point on the unit $n$-sphere lies in on given side of an equatorial hyperplane, we have

$$ \begin{split} P(|U^Tz| > \delta) &= P(|U_1| > \delta)= 2P(U_1 > \delta) = 1-I\left(\delta;\frac{1}{2}, \frac{n-1}{2}\right)\\ &= I\left(1-\delta;\frac{n-1}{2},\frac{1}{2}\right), \end{split} \tag{2} $$

where $I(t; a, b)$ is the normalized incomplete beta function, defined by $I_t(t; a, b) := B(t;a,b) / B(1; a, b)$, with $B(t; a, b):= \int_{0}^t s^{a-1}(1-s)^{b-1}ds$.

Theorem ($U^Tz$ is sub-exponential! ). Let $U$ be uniformly distributed on the unit $n$-sphere and let $z$ be a fixed vector on this sphere. If $n$ is large enough, then for every $\delta \in [0, 1]$, it holds that $$ P(|U^Tz| > \delta) \le e^{-\frac{n-1}{4}\delta}. \tag{3} $$

Proof. Let $p = I(1-\delta; 1/2, (n-1)/2)$. It is known since [Temme (1992)][1] that for $p \in (0, 1)$ and large $a > 0$, the solution of the equation $p = I(t; a,b)$ is given (approximately) by

$$ t=t_p(a, b) \approx e^{-(1/a)Q_{1-p}(\Gamma(b,1))}, \tag{4} $$

where $Q_{1-p}(\Gamma(b,1))$ is the $1-p$ quantile of the unit-scale gamma distribution with shape parameter $b$. Now by standard concentration results (e.g see Boucheron et al. textbook),

$$ Q_{1-p}(\Gamma(b,1)) \le \log(1/p) + \sqrt{2b\log(1/p)}. \tag{5} $$

In particular, for $a=(n-1)/2$ and $b=1/2$ we get

$$ Q_{1-p}(\Gamma(1/2,1)) \le \log(1/p) + \sqrt{\log(1/p)} \le 2\log(1/p). \tag{6} $$

Putting (2), (4), and (6) together and using the basic inequality $e^{-t} \ge 1-t\;\forall t > -1$, we see that $$ \begin{split} 1-\delta &\ge t_{2p}\left((n-1)/2,1/2\right) \ge e^{-\frac{2Q_{1-2p}(\Gamma(1/2,1))}{n-1}} \ge e^{-\frac{2}{n-1}\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}\\ & \ge 1 - \frac{2\left(\log\left(\frac{1}{2p}\right) + \sqrt{\log\left(\frac{1}{2p}\right)}\right)}{n-1} \ge 1-\frac{4\log\left(\frac{1}{2p}\right)}{n-1}, \end{split} $$

from which (3) follows upon combining with (2). $\quad\quad\Box$