10
$\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$

2 Answers 2

4
$\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$
3
  • $\begingroup$ Thank you! But I'm still having trouble dealing with the integral. Any tools or techniques you can suggest? $\endgroup$ Commented Jul 10, 2018 at 16:17
  • $\begingroup$ I have added a suggestion as to what the next step could be. $\endgroup$ Commented Jul 11, 2018 at 23:54
  • $\begingroup$ I have added my motivation of this problem. Thank you! $\endgroup$ Commented Jul 16, 2018 at 18:21
2
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .