9
$\begingroup$

What is the order of the following expectation with respect to $n$?: $$\mathbb{E}(\min_{1\leq i\leq n}|z_i|^2)$$ where $$(z_1,...,z_n)^T\sim N(0,I+11^T), 1=(1,1,...,1)^T$$

I know that when $z_i$ are i.i.d., the order is $1/n^2$. However, my simulation shows that when $z$ has a correlation structure as the above, the order seems to be $1/n$. Can anyone give a rigorous argument?

This question arises from a simple problem. Given $n+1$ i.i.d. standard normal random variables, what is the expected value of the squared distance between two closest samples?

A more general problem is to calculate the rate of: $$\mathbb{E}(\min_{1\leq i\leq n}|z_i|^p)$$ for all positive integer $p$.

$\endgroup$
3
$\begingroup$

$\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\si}{\sigma} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\om}{\omega} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\Var}{\operatorname{\mathsf Var}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} \newcommand{\eD}{\overset{\text{D}}\to} \newcommand{\D}{\overset{\text{D}}=} \newcommand{\tsi}{\tilde\si}$

We may write $z_i=U_i+V$ for $i\in[n]:=\{1,\dots,n\}$, where $U_1,\dots,U_n,V$ are iid standard normal random variables. Let $\Phi$ and $\phi$ denote the standard normal cdf and pdf, respectively. Then for \begin{equation} m:=\min_{1\le i\le n}|z_i|^2 \end{equation} and any real $s>0$ we have \begin{align*} \P(m>s^2)&=\P(|U_i+V|>s\ \forall i\in [n]) \\ &=\int_\R dv\,\phi(v)\,\P(|U_i+v|>s\ \forall i\in [n]) \\ &=\int_\R dv\,\phi(v)g(s,v)^n, \end{align*} where \begin{equation} g(s,v):=\bar\Phi(s-v)+\bar\Phi(s+v)[\in(0,1)] \end{equation} and $\bar\Phi:=1-\Phi$. Hence,
\begin{align*} \E m&=\int_0^\infty2s\,ds\,\P(m>s^2) \\ &=\int_0^\infty2s\,ds\,\int_\R dv\,\phi(v)g(s,v)^n \\ &=4\int_0^\infty s\,ds\,\int_0^\infty dv\,\phi(v)g(s,v)^n. \end{align*}

I think this expression for $\E m$ is amenable to bounding and asymptotic analysis, for which, unfortunately, I do not have time at this point. Hopefully, someone else (or maybe I) can do this later.

The following plot of the values $n\E m(n)$ (where $m(n):=m$) suggests that $m$ is indeed on the order of $1/n$:

enter image description here

Added: The next step could be as follows. For $t\in(0,1)$, let \begin{equation} G(t):=\int_0^\infty s\,ds\,\int_0^\infty dv\,\phi(v)\ii{g(s,v)>1-t}. \end{equation} Clearly, the function $G$ is increasing. It should be not hard to see that $(1-t)^nG(t)\to0$ as $t\uparrow1$. Then, integrating by parts, we will have \begin{equation} \E m/4=\int_0^\infty s\,ds\,\int_0^\infty dv\,\phi(v)g(s,v)^n =\int_0^1(1-t)^n\,dG(t)=n\int_0^1(1-t)^{n-1}\,G(t)\,dt. \end{equation} So, it appears that, to obtain the asymptotics of $\E m$ as $n\to\infty$, it suffices to find that of $G(t)$ as $t\downarrow0$. This will take some extra effort. I think MO users (me included) may be more inclined to take on this task if you could let us know the motivation behind your question, the context in which it arises.

$\endgroup$
  • $\begingroup$ Thank you! But I'm still having trouble dealing with the integral. Any tools or techniques you can suggest? $\endgroup$ – neverevernever Jul 10 '18 at 16:17
  • $\begingroup$ I have added a suggestion as to what the next step could be. $\endgroup$ – Iosif Pinelis Jul 11 '18 at 23:54
  • $\begingroup$ I have added my motivation of this problem. Thank you! $\endgroup$ – neverevernever Jul 16 '18 at 18:21
0
$\begingroup$

This is a follow-up to Iosif Pinelis's answer, which gives an intermediate lower bound $c \tfrac{1}{n \log^2 n}$. I suspect this can be improved to $\tfrac{c}{n}$ by using more advanced tools by someone more experienced.

As pointed out in Iosif's answer, $z_i = U_i + V$ for i.i.d. standard Gaussian $U_1, \ldots, U_n, V$. Write $\Phi$ for the CDF of the standard Garussian, and let $a = \Phi^{-1}(1 - \tfrac{1}{n})$. If $|v| > a + 1$, then $$\mathbb{P}(|v + U_i| < 1) \le \Phi(1 - |v|) \le \Phi(-a) = \tfrac{1}{n} .$$ Therefore, $$\mathbb{P}(\min_{1\le i\le n} |v + U_i| > 1) \ge (1 - \tfrac{1}{n})^n \ge \tfrac{1}{e} .$$ It follows that $$\mathbb{E} \min_{1\le i\le n} |v + U_i|^2 \ge \mathbb{P}(\min_{1\le i\le n} |v + U_i| \ge 1) \ge \tfrac{1}{e} .$$ Furthermore, $$\mathbb{P}(|V| > a + 1) = 2 \Phi(-a - 1) .$$ By conditioning, we conclude that $$ \mathbb{E} \min_{1\le i\le n} |V + U_i|^2 \ge \tfrac{2}{e} \Phi(\Phi^{-1}(\tfrac{1}{n}) - 1) .$$ This is almost $\tfrac{c}{n}$: there is a logarithmic correction. If I remember correctly, the right-hand side of the above estimate is greater than $c\tfrac{1}{n \log^2 n}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.