In cartesian plane, $N$ points are randomly generated within a unit square defined by points $(0,0) (0,1) (1,1) (1,0)$, with uniform distribution. What is the mathematical expectation of the average distance of all distances between all points (distances between the point and the same point (which are obviously $0$) are excluded from the calculation of the average).

There are actually two versions of this question:

  1. Distance is defined as Euclidian.
  2. Distance is defined as Manhattan.

The context of this question is some performance benchmarking in computer science, which are of practical nature and far from pure mathemathics, so I am not going the bother the reader with these details.

  • 1
    $\begingroup$ About the first part, Euclidean distance: presumably all the points are independent to each other, then this $N$ point version is equivalent to just two-points, since you're taking unweighted average of all the expectations. $\endgroup$ – Lee David Chung Lin Feb 14 at 13:40
  • $\begingroup$ For Euclidean distance, I get $$\int_0^1\int_0^1\int_0^1\int_0^1\sqrt{(x-w)^2+(y-z)^2}\mathrm{d}w\mathrm{d}x\mathrm{d}y\mathrm{d}z$$ Is there an easy way to do this? $\endgroup$ – saulspatz Feb 14 at 14:08
  • $\begingroup$ Simulation with $10^6$ trials gave $0.52138263$ for Euclidean distance. For Manhattan distance, the average distance is twice the average horizontal distance, so it's easy. $\endgroup$ – saulspatz Feb 14 at 14:22

You're looking for

$$\Bbb E\left(\frac{1}{\binom N2}\sum_{1\leqslant i < j \leqslant N} d(P_i,P_j)\right);$$

By linearity of expectation, that would be

$$\frac1{\binom N2}\sum_{1\leqslant i < j \leqslant N} \Bbb E\big(d(P_i,P_j)\big).$$

By (assumed) independence of the distribution of the points $P_i$, $\Bbb E\big(d(P_i,P_j)\big)$ is the same for all pairs $i\neq j$. Do you think you can take it from here?

  • $\begingroup$ Small comment. Shouldn't it be $j \leq N$ and not $j \leq 4$ under the sigma? $\endgroup$ – roundsquare Feb 15 at 23:49
  • 1
    $\begingroup$ Absolutely! Holdover mistake from before. Thanks for pointing it out. $\endgroup$ – Fimpellizieri Feb 16 at 4:09

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.