Let X and Y be points in the 4000-dimensional unit cube, picked at random with uniform distribution, which means from I what I understand that all locations in the cube are equally likely. $X \in [0,1]^{ 4000}$ and $Y \in [0,1]^{4000}$.

Why $ \|X −Y\|_{\infty}$ is very likely to be close to 1? I'm new to probability, so can somebody put it in simple words, maybe intuitive way to understand this?

So far, we have $ \|X −Y\|_{\infty}=\max_{i}|x_i-y_i|$. If this is close to 1, then one of the $x_{i}$ should be 1 (or 0) and $y_i$ = 0 (or 1). But why is this true?

  • 1
    $\begingroup$ The max there means you are taking the maximum of many independent random experiments. For any one of them, the expected distance is $E|X_i-Y_i|=1/3$ (verify it). But over many trials, it is not so difficult to see that the maximum distance will be close to 1. What's the probability that $X_i<0.01$ and $Y_i>0.99$? How long, on average, must you wait for such an event? $\endgroup$ – Aryeh Kontorovich Feb 18 '19 at 21:39

$\newcommand{\ep}{\varepsilon}$ Let $d_n:=\|X-Y\|_\infty$, where $X=(X_1,\dots,X_n)$ and $Y=(Y_1,\dots,Y_n)$ are independent random points each uniformly distributed in $[0,1]^n$, so that $X_1,\dots,X_n,Y_1,\dots,Y_n$ are independent random variables (r.v.'s), each uniformly distributed in $[0,1]$. Then for any fixed $\ep\in(0,1)$, using the condition that $X_1,\dots,X_n,Y_1,\dots,Y_n$ are independent and identically distributed, we have
\begin{equation} \begin{aligned} P(d_n<1-\ep)&=P(\max_{i\le n}|X_i-Y_i|<1-\ep) \\ &=P(|X_1-Y_1|<1-\ep,\dots,|X_n-Y_n|<1-\ep) \\ &=P(|X_1-Y_1|<1-\ep)\cdots P|X_n-Y_n|<1-\ep) \\ &=P(|X_1-Y_1|<1-\ep)^n\to0 \end{aligned} \tag{1} \end{equation} (as $n\to\infty$), since $P(|X_1-Y_1|<1-\ep)<1$. That is, $d_n\to1$ in probability.

More specifically, we have $P(|X_1-Y_1|<1-\ep)=1-\ep^2$. So, taking any real $c>0$ and then letting $\ep=\sqrt{c/ n}$, we see that for $n>c$ formula (1) implies \begin{equation*} P(n(1-d_n)^2>c) =P(d_n<1-\sqrt{c/ n})=(1-c/n)^n\to e^{-c}=P(Z>c), \end{equation*} where $Z$ is a r.v. with the standard exponential distribution; that is, $n(1-d_n)^2$ converges in distribution to $Z$. Informally, this can be written as $n(1-d_n)^2\approx Z$ and hence \begin{equation*} d_n\approx1-\sqrt{Z/n}\approx 1. \end{equation*}

| cite | improve this answer | |
  • $\begingroup$ Can you explain why $P(\max_{i\le n}|X_i-Y_i|<1-\epsilon) =(P(|X_1-Y_1|<1-\epsilon))^n\to0?$ $\endgroup$ – dxdydz Feb 18 '19 at 23:22
  • $\begingroup$ I have added details on that. $\endgroup$ – Iosif Pinelis Feb 19 '19 at 0:38

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