3
$\begingroup$

How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?

Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-dimensional cube , $x=(x(1),...x(d))$ the generic point has its -th component $x(i)$ chosen uniformly at random in$ [0,1] $independently of other components and points.

$\Theta(d)$ represent the largest possible distance is d.

I try to reconduct this problem to Bertrand Paradox but i dont think is right. Maybe I that show that $E(||x−y||2)=Θ(d)$ , because is a hint but i dont know how.

i m following this path: https://stats.stackexchange.com/questions/22488/probability-that-uniformly-random-points-in-a-rectangle-have-euclidean-distance

but is different to my point.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Try solving the case when $d=1$ first. Then use the linearity of expectation. $\endgroup$ – Apass.Jack Nov 30 '18 at 17:05
1
$\begingroup$

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] + \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}. $$

$\endgroup$
  • $\begingroup$ Why in C calculation, the expectation became (x-1/2)(y-1/2) ? You take middle point in [0,1] ? thanks for you answer $\endgroup$ – theantomc Dec 1 '18 at 11:15
  • $\begingroup$ Here $1/2$ is the expectation of $x$. $\endgroup$ – Yuval Filmus Dec 1 '18 at 15:53
  • $\begingroup$ you simple apply $\int_{0}^{1} x = 1/2$. And after we apply the linearity on the expectation? Because i don't caught why after we simplify the expression for reach the $2E(x-1/2)^2$ $\endgroup$ – theantomc Dec 1 '18 at 16:10
  • $\begingroup$ Give it a few more hours. $\endgroup$ – Yuval Filmus Dec 1 '18 at 16:13
  • $\begingroup$ see this on "uniform distribution" For a random variable following this distribution, the expected value is then m1 = (a + b)/2 en.wikipedia.org/wiki/Uniform_distribution_(continuous) $\endgroup$ – vzn Dec 2 '18 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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