Suppose we draw a independent random vector $X'$ uniformly from a unit hypercube, $[0, 1]^d$. Given similarly drawn vectors $X\_1 \dots X\_n$ we can define the following quantity


$\rho\_{\infty}(d, n):= \mathbb{E}\_{X', \mathbf{X}} \left[ min\_{i \in [1, n]}|X' - X\_i|\_{\infty} \right]$


Here $l\_{\infty}$ norm is used. I have been trying to show the following lower bound to $\rho\_{\infty}$ without success.


$\ln \rho\_{\infty}(d, n) \geq \ln \frac{d}{2(d+1)} - \frac{\ln n}{d}$


Does anyone have a hint or simple heuristic to prove this lower bound?



Lower bound on mean minimum distance($l_{\infty}$) between a test random vector $X'$ and vectors $X_1, \dots X_N$
Let $\rho:=\rho\_{\infty}(d,n)$ and $m:=\min\_{1\le i\le n}\|X'-X\_i\|\_\infty$. We want to show that
$$\rho\overset{\text{(?)}}\ge\frac d{2(d+1)}\,n^{-1/d}.\tag1$$


For $I:=[0,1]$, we have
$$\rho=\int\_I dt\,P(m>t)$$
and, for $t\in I$,
\begin{align}P(m>t)&=\int\_{I^d}P(X'\in dx)P(\min\_{1\le i\le n}\|x-X\_i\|\_\infty>t) \\
&=\int\_{I^d}P(X'\in dx)P(\|x-X\_1\|\_\infty>t)^n \\
&\ge\int\_{I^d}P(X'\in dx)(1-(2t)^d)^n=(1-(2t)^d)^n. 
\end{align}
So,
$$\rho\ge\int\_I dt\,(1-(2t)^d)^n\ge\int\_0^{n^{-1/d}/2} dt\,(1-n(2t)^d)
=\frac d{2(d+1)}\,n^{-1/d},$$
so that (1) follows.


