Skip to main content
MathOverflow

Return to Answer

added 4 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.8k
  • 8
  • 107
  • 229

$\newcommand\ep\epsilon $In the clever answer by Fedor Petrov, it was shown that \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big)\le C/k, \tag{1}\label{1} \end{equation*} where $C:=1/\ep^2>0$ and the $X_i$'s are any iid random variables.

Let us show that for the standard normal $X_i$'s as in the OP, the upper bound $C/k$ in \eqref{1} can be replaced by a bound decreasing exponentially in $k$.

For $C\le1$, $Q=0$. So, without loss of generality (wlog) $C>1$. Also, wlog $k\ge2$. For \begin{equation*} c:=C-1>0, \tag{2}\label{2} \end{equation*} any $x\in [0,\sqrt{(k-1)/c}\,]$, and $$h:=\frac{k-1-cx^2}{4(k-1)},$$ we have \begin{equation*} Q=P\Big(\sum_{i=2}^k X_i^2<cX_1^2\Big)\le Q_1+Q_2, \tag{3}\label{3} \end{equation*} where \begin{equation*} Q_1:=P(X_1^2\ge x^2)\le e^{-x^2/2}=:R_1 \tag{4}\label{4} \end{equation*} and \begin{equation*} \begin{aligned} Q_2&:=P\Big(\sum_{i=2}^k X_i^2<cx^2\Big) \\ &=P\Big(\sum_{i=2}^k(1-X_i^2)>k-1-cx^2\Big) \\ &\le\exp\{-h(k-1-cx^2)+(k-1)\ln Ee^{h(1-X_1^2)}\} \\ &=\exp\{-h(k-1-cx^2)+(k-1)(h-\tfrac12\,\ln(1+2h))\} \\ &\le\exp\{-h(k-1-cx^2)+2(k-1)h^2\} \\ &=\exp-\frac{(k-1-cx^2)^2}{8(k-1)}=:R_2. \end{aligned} \tag{5}\label{5} \end{equation*} Choosing now $x$ to be the positive root of the equation $R_1=R_2$, from \eqref{3}, \eqref{4}, and \eqref{5} we get \begin{equation} Q\le 2\exp-\frac{k-1}{(1+\sqrt C)^2}, \tag{6}\label{6} \end{equation}\begin{equation} Q\le 2\exp-\frac{k-1}{2(1+\sqrt C)^2}, \tag{6}\label{6} \end{equation} which is the promised bound, decreasing exponentially in $k$.

One may also note that typically $k$ and $C$ will be large, and then the exponent in the bound in \eqref{6} will be about $-k/C$$-k/(2C)$ -- compare this with the bound in \eqref{1}.

$\newcommand\ep\epsilon $In the clever answer by Fedor Petrov, it was shown that \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big)\le C/k, \tag{1}\label{1} \end{equation*} where $C:=1/\ep^2>0$ and the $X_i$'s are any iid random variables.

Let us show that for the standard normal $X_i$'s as in the OP, the upper bound $C/k$ in \eqref{1} can be replaced by a bound decreasing exponentially in $k$.

For $C\le1$, $Q=0$. So, without loss of generality (wlog) $C>1$. Also, wlog $k\ge2$. For \begin{equation*} c:=C-1>0, \tag{2}\label{2} \end{equation*} any $x\in [0,\sqrt{(k-1)/c}\,]$, and $$h:=\frac{k-1-cx^2}{4(k-1)},$$ we have \begin{equation*} Q=P\Big(\sum_{i=2}^k X_i^2<cX_1^2\Big)\le Q_1+Q_2, \tag{3}\label{3} \end{equation*} where \begin{equation*} Q_1:=P(X_1^2\ge x^2)\le e^{-x^2/2}=:R_1 \tag{4}\label{4} \end{equation*} and \begin{equation*} \begin{aligned} Q_2&:=P\Big(\sum_{i=2}^k X_i^2<cx^2\Big) \\ &=P\Big(\sum_{i=2}^k(1-X_i^2)>k-1-cx^2\Big) \\ &\le\exp\{-h(k-1-cx^2)+(k-1)\ln Ee^{h(1-X_1^2)}\} \\ &=\exp\{-h(k-1-cx^2)+(k-1)(h-\tfrac12\,\ln(1+2h))\} \\ &\le\exp\{-h(k-1-cx^2)+2(k-1)h^2\} \\ &=\exp-\frac{(k-1-cx^2)^2}{8(k-1)}=:R_2. \end{aligned} \tag{5}\label{5} \end{equation*} Choosing now $x$ to be the positive root of the equation $R_1=R_2$, from \eqref{3}, \eqref{4}, and \eqref{5} we get \begin{equation} Q\le 2\exp-\frac{k-1}{(1+\sqrt C)^2}, \tag{6}\label{6} \end{equation} which is the promised bound, decreasing exponentially in $k$.

One may also note that typically $k$ and $C$ will be large, and then the exponent in the bound in \eqref{6} will be about $-k/C$ -- compare this with the bound in \eqref{1}.

$\newcommand\ep\epsilon $In the clever answer by Fedor Petrov, it was shown that \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big)\le C/k, \tag{1}\label{1} \end{equation*} where $C:=1/\ep^2>0$ and the $X_i$'s are any iid random variables.

Let us show that for the standard normal $X_i$'s as in the OP, the upper bound $C/k$ in \eqref{1} can be replaced by a bound decreasing exponentially in $k$.

For $C\le1$, $Q=0$. So, without loss of generality (wlog) $C>1$. Also, wlog $k\ge2$. For \begin{equation*} c:=C-1>0, \tag{2}\label{2} \end{equation*} any $x\in [0,\sqrt{(k-1)/c}\,]$, and $$h:=\frac{k-1-cx^2}{4(k-1)},$$ we have \begin{equation*} Q=P\Big(\sum_{i=2}^k X_i^2<cX_1^2\Big)\le Q_1+Q_2, \tag{3}\label{3} \end{equation*} where \begin{equation*} Q_1:=P(X_1^2\ge x^2)\le e^{-x^2/2}=:R_1 \tag{4}\label{4} \end{equation*} and \begin{equation*} \begin{aligned} Q_2&:=P\Big(\sum_{i=2}^k X_i^2<cx^2\Big) \\ &=P\Big(\sum_{i=2}^k(1-X_i^2)>k-1-cx^2\Big) \\ &\le\exp\{-h(k-1-cx^2)+(k-1)\ln Ee^{h(1-X_1^2)}\} \\ &=\exp\{-h(k-1-cx^2)+(k-1)(h-\tfrac12\,\ln(1+2h))\} \\ &\le\exp\{-h(k-1-cx^2)+2(k-1)h^2\} \\ &=\exp-\frac{(k-1-cx^2)^2}{8(k-1)}=:R_2. \end{aligned} \tag{5}\label{5} \end{equation*} Choosing now $x$ to be the positive root of the equation $R_1=R_2$, from \eqref{3}, \eqref{4}, and \eqref{5} we get \begin{equation} Q\le 2\exp-\frac{k-1}{2(1+\sqrt C)^2}, \tag{6}\label{6} \end{equation} which is the promised bound, decreasing exponentially in $k$.

One may also note that typically $k$ and $C$ will be large, and then the exponent in the bound in \eqref{6} will be about $-k/(2C)$ -- compare this with the bound in \eqref{1}.

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

$\newcommand\ep\epsilon $In the clever answer by Fedor Petrov, it was shown that \begin{equation*} Q:=P\Big(\frac{X_1^2+\dots+X_k^2}{X_1^2}<C\Big)\le C/k, \tag{1}\label{1} \end{equation*} where $C:=1/\ep^2>0$ and the $X_i$'s are any iid random variables.

Let us show that for the standard normal $X_i$'s as in the OP, the upper bound $C/k$ in \eqref{1} can be replaced by a bound decreasing exponentially in $k$.

For $C\le1$, $Q=0$. So, without loss of generality (wlog) $C>1$. Also, wlog $k\ge2$. For \begin{equation*} c:=C-1>0, \tag{2}\label{2} \end{equation*} any $x\in [0,\sqrt{(k-1)/c}\,]$, and $$h:=\frac{k-1-cx^2}{4(k-1)},$$ we have \begin{equation*} Q=P\Big(\sum_{i=2}^k X_i^2<cX_1^2\Big)\le Q_1+Q_2, \tag{3}\label{3} \end{equation*} where \begin{equation*} Q_1:=P(X_1^2\ge x^2)\le e^{-x^2/2}=:R_1 \tag{4}\label{4} \end{equation*} and \begin{equation*} \begin{aligned} Q_2&:=P\Big(\sum_{i=2}^k X_i^2<cx^2\Big) \\ &=P\Big(\sum_{i=2}^k(1-X_i^2)>k-1-cx^2\Big) \\ &\le\exp\{-h(k-1-cx^2)+(k-1)\ln Ee^{h(1-X_1^2)}\} \\ &=\exp\{-h(k-1-cx^2)+(k-1)(h-\tfrac12\,\ln(1+2h))\} \\ &\le\exp\{-h(k-1-cx^2)+2(k-1)h^2\} \\ &=\exp-\frac{(k-1-cx^2)^2}{8(k-1)}=:R_2. \end{aligned} \tag{5}\label{5} \end{equation*} Choosing now $x$ to be the positive root of the equation $R_1=R_2$, from \eqref{3}, \eqref{4}, and \eqref{5} we get \begin{equation} Q\le 2\exp-\frac{k-1}{(1+\sqrt C)^2}, \tag{6}\label{6} \end{equation} which is the promised bound, decreasing exponentially in $k$.

One may also note that typically $k$ and $C$ will be large, and then the exponent in the bound in \eqref{6} will be about $-k/C$ -- compare this with the bound in \eqref{1}.