# Infinite norm of two randomly picked points [closed]

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?

• 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? – 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{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} (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*}$$
• Can you explain why $P(\max_{i\le n}|X_i-Y_i|<1-\epsilon) =(P(|X_1-Y_1|<1-\epsilon))^n\to0?$ – dxdydz Feb 18 '19 at 23:22