Skip to main content
2 of 2
added 1 character in body
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Let $\vec{x},\vec{y}$ be two random $d$-dimensional vectors chosen uniformly and independently from $[0,1]^d$. That is, $x_1,\ldots,x_d,y_1,\ldots,y_d$ are all uniform random samples of the uniform distribution over $[0,1]$. Then $$ \mathbb{E}[\|\vec{x}-\vec{y}\|^2] = \mathbb{E}\left[\sum_{i=1}^d (x_i-y_i)^2\right] = \sum_{i=1}^d \mathbb{E}[(x_i-y_i)]^2 = d \operatorname*{\mathbb{E}}_{x,y \sim [0,1]} [(x-y)^2]. $$ Let $C = \mathbb{E}[(x-y)^2]$. Then the expected squared distance of two points in $[0,1]^d$ is $Cd$.

It is not hard to calculate $C$ explicitly: $$ C = \mathbb{E}[((x-1/2) - (y-1/2))^2] = \mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[(x-1/2)(y-1/2)] + \mathbb{E}[(y-1/2)^2] = \\ 2\mathbb{E}[(x-1/2)^2] + 2\mathbb{E}[x-1/2] \mathbb{E}[y-1/2] = 2\mathbb{E}[(x-1/2)^2] = \\ 2\int_0^1 (x-1/2)^2 \, dx = 2\int_0^1 x^2-x+\frac{1}{4} \, dx = 2\left(\frac{1}{3} - \frac{1}{2} + \frac{1}{4}\right) = \frac{1}{6}. $$

Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512