Assume space is uniformly filled with random points placed by a spatial Poisson process of a given intensity $\rho$. I try to move from the origin to some remote point (which we can take to be directly along the x-axis), but can only move between points closer than unit distance. The resulting optimal trajectory will have a total length $D$ larger than the actual distance $d$ to the target point. What is the distribution or expectation of $D/d$?

enter image description here

Clearly, if $\rho$ is too small we are below the continuum percolation threshold and I will not get anywhere. So let us assume $\rho$ is large enough.

If I look at the first step, the distance I will manage along the x-axis will be the largest x-coordinate of the points in the unit sphere. It is not that hard to calculate the maximum order statistic for a given number of points $n\sim (4\pi/3)\rho$: the distribution is $f(x)=(3/4)(1-x^2)$, the cdf is $F(x)=(3x-x^3+2)/4$, the distribution of the maximum is $f_{(n)}(x)=(3n/4^n)(3x-x^3+2)^{n-1}(1-x^2)$. The expectation is a messy polynomial but asymptotes towards 1, with $E[f_{(5)}]>1/2$ and $E[f_{(109)}]>0.9$.

However, (1) the number of points is actually a random variable, and (2) on the next step I also have a lateral deviation dependent on the y- and z-coordinates of the point that needs to be removed eventually.

Empirically, the distribution of $D/d$ looks like it approaches a Gaussian as I increase $d$, although it looks like the kurtosis is a bit high.

Any thoughts of how to characterise the distribution as a function of $d$ and $\rho$? Or just a better way of estimating the expectation than running lots of Monte Carlo simulations?

  • 1
    $\begingroup$ There's always a certain probability that there's no such path. If you count that as $D=\infty$, the expectation would be infinite. Alternatively, you could consider the distribution of $D$ conditional on there being a path. $\endgroup$
    – joriki
    Jan 24, 2020 at 11:59
  • $\begingroup$ Yes, conditioning on there being a path seems reasonable. $\endgroup$ Jan 24, 2020 at 12:07


You must log in to answer this question.

Browse other questions tagged .