The average distance between points randomly placed in diagonally adjacent unit squares

The average distance between points randomly placed in certain geometrical forms appears in a wide range of contexts, e.g. in area sampling, experimental design, geology or remote sensing. (For me, it surprisingly popped up during my Master's thesis in the context of spatial regression models.) This post is concerned particularly with the following question:

What is the expected distance between two points, each placed randomly within a square that touches the other at a single corner, like same-colored fields on a chessboard?

Background

A well studied mathematical problem is the random distance between points within the same form (so-called line-picking). For a square, this comes to slightly more than half - namely approx. $0.521$ times - the length of one side, as Wikipedia informs us. 

Less well established is the case where points are placed in different forms. The simplest such setup are two squares of the same size placed side-by-side (like a1 and b1 on a chessboard). For simplicity, we will assume unit squares in all that follows (as in the one-square case, the results generalize by simply multiplying with the length of a side). Interestingly, the average distance is greater than the distance between the squares' centers of gravity, approx. $1.088$ (Alagar, 1976).

What if the squares are diagonal, like a1 and b2 on a chessboard? A solution to this problem is not as readily found in the literature; some work of one's own is required. A straightforward approach is to approximate the desired average distance via Monte Carlo simulation, as shown below in the animation.


Monte Carlo approximation (the first 10,000 steps)

With $n = 10^6$ Monte Carlo runs we get approx. $1.4736$, which is again slightly more than the distance between the centers of gravity (that would be $\sqrt{2} \approx 1.4142$). What about an analytical solution? 

For that, we need the probability density function (PDF) of the distance distribution. It was worked out and published in the 1940s by renowned Indian statistician Birendra Nath Ghosh (Ghosh, 19151). For the first moment of that PDF the author provides an approximate answer of $1.473$, but does not share the calculation beyond its starting point. I have fleshed out how to get to the answer below.

Derivation

Denote the random distance by $X$ and the desired expectation by $\mathrm{E}(X)$. The PDF of $X$ for the case at hand is provided by Ghosh (1951). Five different ranges must be considered. The desired first moment is found by solving: \[\begin{aligned}
    \mathrm{E}(X)
    &= \int_0^1 \frac{1}{2}X^4 \;\mathrm{d}X\\
    &+ \int_{1}^{\sqrt{2}} -\frac{3}{2}X^4 + 4X^3 - 2X^2 \;\mathrm{d}X\\
    &+ \int_{\sqrt{2}}^{2} \frac{1}{2}X^4 + 4X^3 + 2X^2 - 8X^2 \sqrt{X^2 - 1} + 4X^2\left[\cos^{-1}\left(\frac{1}{X}\right)-\sin^{-1}\left(\frac{1}{X}\right)\right] \;\mathrm{d}X\\
    &+ \int_{2}^{\sqrt{5}} \frac{3}{2}X^4 + 6X^2 - 8X^2 \sqrt{X^2 - 1} + 4X^2\left[\cos^{-1}\left(\frac{1}{X}\right)-\sin^{-1}\left(\frac{1}{X}\right)\right] \;\mathrm{d}X\\
    &+ \int_{\sqrt{5}}^{2\sqrt{2}} -\frac{1}{2}X^4 - 4X^2 + 4X^2 \sqrt{X^2-4} + 4X^2 \left[\sin^{-1}\left(\frac{2}{X}\right) - \cos^{-1}\left(\frac{2}{X}\right)\right] \;\mathrm{d}X
    \end{aligned}
    \] Solving first the simple polynomial parts and rewriting yields:\[\begin{aligned}
    \mathrm{E}(X)
    &= \frac{80}{3}\sqrt{5} - \frac{192}{5}\sqrt{2} - 1
    -8\left(\int_{\sqrt{2}}^2\phi_1(X)\;\mathrm{d}X + \int_2^{\sqrt{5}}\phi_1(X)\; \mathrm{d}X\right)\\
    &+ 4\left(\int_{\sqrt{5}}^{2\sqrt{2}} \phi_2(X)\;\mathrm{d}X
    + \int_{\sqrt{2}}^2\omega_1(X)\;\mathrm{d}X + \int_2^{\sqrt{5}}\omega_1(X)\;\mathrm{d}X + \int_{\sqrt{5}}^{2\sqrt{2}}\omega_2(X)\right)\;\mathrm{d}X\\[3mm]
    \text{with }\hspace{3mm}
    \phi_1(X) &= X^2\sqrt{X^2-1}\;\;,\;\;\phi_2(X) = X^2\sqrt{X^2-4}\\
    \omega_1(X) &= X^2\left[\cos^{-1}\left(\frac{1}{X}\right)-\sin^{-1}\left(\frac{1}{X}\right)\right]\;\;,\;\;
    \omega_2(X) = X^2 \left[\sin^{-1}\left(\frac{2}{X}\right) - \cos^{-1}\left(\frac{2}{X}\right)\right]
    \end{aligned}\] $\phi_1(X)$ and $\omega_1(X)$ can be solved on the combined subinterval $\left[\sqrt{2}\,,\sqrt{5}\right]$. Antiderivatives for $\int X^2\sqrt{X^2-m^2} \;\mathrm{d}X$ and $\int X^2\sin^{-1}\left(\frac{m}{X}\right) \;\mathrm{d}X$ as well as $\int X^2\cos^{-1}\left(\frac{m}{X}\right) \;\mathrm{d}X$ are also suggested by Ghosh (1951). This yields the partial solutions: \[\begin{aligned}
    8\int_{\sqrt{2}}^{\sqrt{5}}\phi_1(X) \;\mathrm{d}X &=
    18\sqrt{5} - 3\sqrt{2} + \ln\left(1+\sqrt{2}\right)-\ln\left(2+\sqrt{5}\right)\\
    4\int_{\sqrt{5}}^{2\sqrt{2}}\phi_2(X) \;\mathrm{d}X &=
    24\sqrt{2} - 3\sqrt{5} -8\ln\left(1 + \sqrt{2}\right)+8\ln\left(1+\sqrt{5}\right)-8\ln(2)\\
    4\int_{\sqrt{2}}^{\sqrt{5}}\omega_1(X) \;\mathrm{d}X &=
    \frac{4}{3}\left[\sqrt{2}-\ln\left(2+\sqrt{5}\right)+\ln\left(1+\sqrt{2}\right)\right]-\frac{8}{3}\sqrt{5}\\
    &\;\;+\frac{4}{3} \left[\sqrt{125}\left(\cos^{-1}\left(\frac{1}{\sqrt{5}}\right) - \sin^{-1}\left(\frac{1}{\sqrt{5}}\right)\right) - \sqrt{8}\left(\cos^{-1}\left(\frac{1}{\sqrt{2}}\right)-\sin^{-1}\left(\frac{1}{\sqrt{2}}\right)\right)\,\right]\\
    4\int_{\sqrt{5}}^{2\sqrt{2}} \omega_2(X) \;\mathrm{d}X &=
     \frac{32}{3}\left[\sqrt{2} + \ln\left(1+\sqrt{2}\right) -\ln\left(1+\sqrt{5}\right)+\ln(2)\right] -\frac{8}{3} \sqrt{5}\\
    &\;\;+\frac{4}{3}\left[\sqrt{125}\left(\cos^{-1}\left(\frac{2}{\sqrt{5}}\right) - \sin^{-1}\left(\frac{2}{\sqrt{5}}\right)\right) - 8\sqrt{8}\left(\cos^{-1}\left(\frac{1}{\sqrt{2}}\right) - \sin^{-1}\left(\frac{1}{\sqrt{2}}\right)\right)\,\right]
    \end{aligned}\] Combining and simplifying gives the desired expression: \[\mathrm{E}(X) \approx \frac{1}{3}\left[\sqrt{5}+9\ln\left(1+\sqrt{2}\right)-\ln\left(2+\sqrt{5}\right)+8\ln\left(\frac{2}{1+\sqrt{5}}\right)\right]+\frac{3}{5}\sqrt{2}-1 \approx \underline{\underline{1.47356}}\]

Implementation remarks

R code for the Monte Carlo approximation and for creating the animation can be downloaded from my GitHub page. The animation was created with the wonderful gganimate package.

Literature

V.S. Alagar, "The distribution of distance between random points," Journal of Applied Probability, vol.13, no.3, pp.558-566, 1976.

B. Ghosh, "Random distances within a rectangle and between two rectangles," Bulletin of the Calcutta Mathematical Society, vol.43, pp.17-24, 1951.

Kommentare

Kommentar veröffentlichen

Beliebte Posts aus diesem Blog

On the reversibility of Voronoi geomasking

Bild
In a previous blog post I have talked about "scrambling" geographic point data in an attempt to protect the units, to which these points pertain, from privacy violations. Besides the simple 'random perturbation' discussed there, a whole range of different methods have been suggested. One is Voronoi masking , introduced by Seidl et al. (2015).  Despite the comparatively good capacity of that method to preserve spatial patterns in masked data, its deterministic mechanism raises concerns about the possibility to reverse the procedure, revealing real locations. In this post, I explore the reversal potential of Voronoi geomasking. What is Voronoi masking? Seidl et al. (2015) describe the method (in its most vanilla version) as follows: For each point location, identified by planar geographic coordinates $(x_{i1}, x_{i2})$, its corresponding Voronoi polygon is computed. The point is then shifted onto the closest edge of said polygon along the shortest path. An example is...
Mehr anzeigen

Herfindahl-Hirschman-Index als Maß für die Diversität von Herkünften auf Gemeindeebene [deutsch]

Bild
In einem kürzlich erschienenen Sammelband präsentierte Prenzel (2024) eine Auswertung zur sog. kulturellen Diversität der deutschen Bevölkerung, operationalisiert als inverses Konzentrationsmaß ( Fraktionalisierung ) verschiedener Geburtsländer. Berechnet wurde das Maß mit Ergebnissen des Zensus 2011, die in diesem Fall jedoch räumlich nicht sehr tief gegliedert vorlagen.  Für den Zensus 2022 sind die erforderlichen Daten nun deutlich detaillierter auf Ebene der Gemeinden verfügbar. Es soll daher im Folgenden eine kurze Replikation der Auswertung von Prenzel mit neueren Daten und höherer räumlicher Auflösung gezeigt werden. Außerdem werden weitere Analysen angerissen, die durch die höhere räumliche Auflösung erst möglich werden. Konzentrationsmaß 'Fraktionalisierung' Es ist naheliegend, "Diversität" als Gegenbegriff zu Homogenität zu verstehen. Zur Quantifizierung bieten sich daher Konzentrationsmaße an. Die von Prenzel (2024, S.78) verwendete Kennzahl der 'Frak...
Mehr anzeigen

Derivation of the expected nearest neighbor distance in a homogeneous Poisson process

The average distance between nearest neighbors, randomly placed in $m$-dimensional real space $\mathbb{R}^m$, is a common test statistic to assess levels of clustering or avoidance (for an introduction see Getis & Ord, 1992). It is used from geostatistics to population ecology and particle physics. Though the theoretical value used in inference is well known, its derivation is skipped over in pretty much every textbook on the subject. The value in question is $\frac{1}{2} \sqrt{\frac{1}{\lambda}}$, with $\lambda$ the intensity (no. of events per unit of space) of the assumed underlying point process. The derivation is shown below. Background The $G$-function (not to be confused with others of the same name ) is a distance-based measure in the analysis of point processes. More specifically, it is the distribution function of distances between nearest neighbors . (For details, see e.g. the introductory overview by FU Berlin .) Empirically, it is defined as \[\hat{G}(r) = \frac{1}{n} ...
Mehr anzeigen