Skip to main content
added 236 characters in body
Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

$\newcommand\ep\epsilon\newcommand{\Ga}{\Gamma}$Somehow, writing my previous answer, I forgot the fact that the random variable (r.v.) \begin{equation*} R:=\frac{X_1^2}{X_1^2+\dots+X_k^2} \end{equation*} has the beta distribution with parameters $1/2,(k-1)/2$, -- which follows because $X_1^2$ and $X_2^2+\dots+X_k^2$ are independent r.v.'s, $X_1^2$ with the gamma distribution with parameters 1/2,2 and $X_2^2+\dots+X_k^2$ with the gamma distribution with parameters $(k-1)/2,2$.

This fact makes it easy to bound \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big), \tag{10}\label{10} \end{equation*} where $C:=1/\ep^2>1$ and the $X_i$'s are iid standard normal r.v.'s.

Indeed, without loss of generality $k\ge2$. We have \begin{equation*} Q=P(R>1/C)=r_k J, \tag{20}\label{20} \end{equation*} where \begin{equation*} r_k:=\frac{\Ga(k/2)}{\Ga(1/2)\Ga((k-1)/2)} \end{equation*} and \begin{equation*} J:=\int_{1/C}^1 x^{-1/2}(1-x)^{(k-3)/2}\,dx. \end{equation*} By the log-convexity of the gamma function, \begin{equation*} r_k\le\frac1{\Ga(1/2)} \sqrt{\frac{\Ga((k+1)/2)}{\Ga((k-1)/2)}}=\sqrt{\frac{k-1}{2\pi}}. \end{equation*} An easy, even if not quite accurate, way to bound $J$ is as follows: \begin{equation*} J\le\int_{1/C}^1 (1/C)^{-1/2}(1-1/C)^{(k-3)/2}\,dx =C^{1/2}(1-1/C)^{(k-3)/2} \end{equation*} for $k\ge3$; the case $k=2$ is very easy.

Thus, for $k\ge3$, \begin{equation*} Q=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big) \le C^{1/2}\sqrt{\frac{k-1}{2\pi}}\,(1-1/C)^{(k-3)/2}. \tag{30}\label{30} \end{equation*}

So, as in the previous answer, we have an upper bound on $Q$ decreasing exponentially in $k$. However, in the latter case the base of the power with exponent $k$ is $(1-1/C)^{1/2}<\exp-\frac1{2C}$, which is strictly less than the corresponding base, $\exp-\frac1{2(1+\sqrt C)^2}$, in the previous answer. So, we now get a faster decreasing upper bound on $Q$.

$\newcommand\ep\epsilon\newcommand{\Ga}{\Gamma}$Somehow, writing my previous answer, I forgot that the random variable (r.v.) \begin{equation*} R:=\frac{X_1^2}{X_1^2+\dots+X_k^2} \end{equation*} has the beta distribution with parameters $1/2,(k-1)/2$, which makes it easy to bound \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big), \tag{10}\label{10} \end{equation*} where $C:=1/\ep^2>1$ and the $X_i$'s are iid standard normal r.v.'s.

Indeed, without loss of generality $k\ge2$. We have \begin{equation*} Q=P(R>1/C)=r_k J, \tag{20}\label{20} \end{equation*} where \begin{equation*} r_k:=\frac{\Ga(k/2)}{\Ga(1/2)\Ga((k-1)/2)} \end{equation*} and \begin{equation*} J:=\int_{1/C}^1 x^{-1/2}(1-x)^{(k-3)/2}\,dx. \end{equation*} By the log-convexity of the gamma function, \begin{equation*} r_k\le\frac1{\Ga(1/2)} \sqrt{\frac{\Ga((k+1)/2)}{\Ga((k-1)/2)}}=\sqrt{\frac{k-1}{2\pi}}. \end{equation*} An easy, even if not quite accurate, way to bound $J$ is as follows: \begin{equation*} J\le\int_{1/C}^1 (1/C)^{-1/2}(1-1/C)^{(k-3)/2}\,dx =C^{1/2}(1-1/C)^{(k-3)/2} \end{equation*} for $k\ge3$; the case $k=2$ is very easy.

Thus, for $k\ge3$, \begin{equation*} Q=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big) \le C^{1/2}\sqrt{\frac{k-1}{2\pi}}\,(1-1/C)^{(k-3)/2}. \tag{30}\label{30} \end{equation*}

So, as in the previous answer, we have an upper bound on $Q$ decreasing exponentially in $k$. However, in the latter case the base of the power with exponent $k$ is $(1-1/C)^{1/2}<\exp-\frac1{2C}$, which is strictly less than the corresponding base, $\exp-\frac1{2(1+\sqrt C)^2}$, in the previous answer. So, we now get a faster decreasing upper bound on $Q$.

$\newcommand\ep\epsilon\newcommand{\Ga}{\Gamma}$Somehow, writing my previous answer, I forgot the fact that the random variable (r.v.) \begin{equation*} R:=\frac{X_1^2}{X_1^2+\dots+X_k^2} \end{equation*} has the beta distribution with parameters $1/2,(k-1)/2$ -- which follows because $X_1^2$ and $X_2^2+\dots+X_k^2$ are independent r.v.'s, $X_1^2$ with the gamma distribution with parameters 1/2,2 and $X_2^2+\dots+X_k^2$ with the gamma distribution with parameters $(k-1)/2,2$.

This fact makes it easy to bound \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big), \tag{10}\label{10} \end{equation*} where $C:=1/\ep^2>1$ and the $X_i$'s are iid standard normal r.v.'s.

Indeed, without loss of generality $k\ge2$. We have \begin{equation*} Q=P(R>1/C)=r_k J, \tag{20}\label{20} \end{equation*} where \begin{equation*} r_k:=\frac{\Ga(k/2)}{\Ga(1/2)\Ga((k-1)/2)} \end{equation*} and \begin{equation*} J:=\int_{1/C}^1 x^{-1/2}(1-x)^{(k-3)/2}\,dx. \end{equation*} By the log-convexity of the gamma function, \begin{equation*} r_k\le\frac1{\Ga(1/2)} \sqrt{\frac{\Ga((k+1)/2)}{\Ga((k-1)/2)}}=\sqrt{\frac{k-1}{2\pi}}. \end{equation*} An easy, even if not quite accurate, way to bound $J$ is as follows: \begin{equation*} J\le\int_{1/C}^1 (1/C)^{-1/2}(1-1/C)^{(k-3)/2}\,dx =C^{1/2}(1-1/C)^{(k-3)/2} \end{equation*} for $k\ge3$; the case $k=2$ is very easy.

Thus, for $k\ge3$, \begin{equation*} Q=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big) \le C^{1/2}\sqrt{\frac{k-1}{2\pi}}\,(1-1/C)^{(k-3)/2}. \tag{30}\label{30} \end{equation*}

So, as in the previous answer, we have an upper bound on $Q$ decreasing exponentially in $k$. However, in the latter case the base of the power with exponent $k$ is $(1-1/C)^{1/2}<\exp-\frac1{2C}$, which is strictly less than the corresponding base, $\exp-\frac1{2(1+\sqrt C)^2}$, in the previous answer. So, we now get a faster decreasing upper bound on $Q$.

Source Link
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

$\newcommand\ep\epsilon\newcommand{\Ga}{\Gamma}$Somehow, writing my previous answer, I forgot that the random variable (r.v.) \begin{equation*} R:=\frac{X_1^2}{X_1^2+\dots+X_k^2} \end{equation*} has the beta distribution with parameters $1/2,(k-1)/2$, which makes it easy to bound \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big), \tag{10}\label{10} \end{equation*} where $C:=1/\ep^2>1$ and the $X_i$'s are iid standard normal r.v.'s.

Indeed, without loss of generality $k\ge2$. We have \begin{equation*} Q=P(R>1/C)=r_k J, \tag{20}\label{20} \end{equation*} where \begin{equation*} r_k:=\frac{\Ga(k/2)}{\Ga(1/2)\Ga((k-1)/2)} \end{equation*} and \begin{equation*} J:=\int_{1/C}^1 x^{-1/2}(1-x)^{(k-3)/2}\,dx. \end{equation*} By the log-convexity of the gamma function, \begin{equation*} r_k\le\frac1{\Ga(1/2)} \sqrt{\frac{\Ga((k+1)/2)}{\Ga((k-1)/2)}}=\sqrt{\frac{k-1}{2\pi}}. \end{equation*} An easy, even if not quite accurate, way to bound $J$ is as follows: \begin{equation*} J\le\int_{1/C}^1 (1/C)^{-1/2}(1-1/C)^{(k-3)/2}\,dx =C^{1/2}(1-1/C)^{(k-3)/2} \end{equation*} for $k\ge3$; the case $k=2$ is very easy.

Thus, for $k\ge3$, \begin{equation*} Q=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big) \le C^{1/2}\sqrt{\frac{k-1}{2\pi}}\,(1-1/C)^{(k-3)/2}. \tag{30}\label{30} \end{equation*}

So, as in the previous answer, we have an upper bound on $Q$ decreasing exponentially in $k$. However, in the latter case the base of the power with exponent $k$ is $(1-1/C)^{1/2}<\exp-\frac1{2C}$, which is strictly less than the corresponding base, $\exp-\frac1{2(1+\sqrt C)^2}$, in the previous answer. So, we now get a faster decreasing upper bound on $Q$.