Three points are chosen on a circumference. Find the CDF of the max straight-line distance between each pair of points.

Question

Three points are chosen independently at random on a circumference with radius r. Find the CDF of the maximum straight-line distance between each pair of points.

I came up with this statement based on this original problem that asks about the approximate probability when the maximum straight-line distance is the radius $r$. I'm trying to make it more general.

First of all, I start by looking at only two points: $A$ and $B$. In this case it's easy to see that the two points and the center of the circumference form an isosceles triangle whose two-equal sides have length $r$ and the other side $AB$ is the straight-line distance $d$.

Based on that we notice that:

$$ \sin{{\alpha\over{2}}}={{d}\over{2r}} $$

So $$d=2r \sin{{\alpha\over{2}}}$$

And $$\alpha=2 \arcsin{{{d}\over{2r}}}$$

Hence, the probability that the maximum straight-line distance $D$ between $A$ and $B$ is less than $d$ is

$$P\{D \leq d\} = {{2\alpha}\over{2\pi}}={{\alpha}\over{\pi}}$$

where $D$ takes values between $0$ and $\pi$. Note that it's $2\alpha$ because in the figure we also need to account for placing $B$ to the left of $A$.

We now introduce the third point $C$.

Computing this depends on where $A$ and $B$ are placed. If $A$ and $B$ are in the same place, the probability that the $AC$ and $BC$ distances are both less than $d$ is the same as above

$${{2\alpha}\over{2\pi}}$$

However, as we chose $B$ away from $A$, this probability decreases linearly when the angle $\beta$, that is formed by the arc $A$ and $B$, increases.

This is where I'm not entirely sure whether I'm reasoning well. I try to use conditional probability to express what I described in the above paragraph.

Thus, the probability that we chose $C$ in a way that its distance to $A$ and $B$ is less than $d$ after having chosen $AB$ with distance $m$ less than $d$ is

$$ P\{AC \leq d, BC \leq d \mid AB = m \} = {{2\alpha - \beta}\over{2\pi}} $$

where $m \leq d$, and $\beta$ is the angle formed by $A$ and $B$ when they are at distance $m$, and $\alpha$ is the angle for distance $d$.

Now, assuming that I calculated $P\{AC \leq d, BC \leq d \mid AB = m \}$ correctly I still need to find $P\{AC \leq d, BC \leq d, AB \leq d\}$.

My attempt at finding $P\{AC \leq d, BC \leq d, AB \leq d\}$ is using:

$$ P\{AC \leq d, BC \leq d \mid AB \leq d \} = {{P\{AC \leq d, BC \leq d , AB \leq d\}}\over{P\{AB \leq d\}}} $$

And to find $P\{AC \leq d, BC \leq d \mid AB \leq d \}$ from $P\{AC \leq d, BC \leq d \mid AB = m \}$ I tried to integrate the latter for all values of $m$ up to $d$, but what I got didn't make much sense.

Answer 1

Let $a$ be half the angular distance between the first two points.

Let $b$ be the angular distance between their circular midpoint and the third point.

Then $a$ is uniformly distributed between 0 and $\pi/2$, and $b$ is uniformly distributed between 0 and $\pi$.

The maximum angular distance between the three points is $$\max(2a, \min(a+b, 2\pi-a-b)).$$

So the cdf for the angular distance $c$ can be calculated as $$P[c] = \int_0^\pi \int_0^{\pi/2} \chi [\max(2a, \min(a+b, 2\pi-a-b))<c]\dfrac{da}{\pi/2}\dfrac{db}{\pi}$$ $$ =\begin{cases} \ \ \dfrac{\phantom{+3c\pi}3c^2\phantom{+pi^2}}{4\pi^2}\ \text{ if } 0\le c \le 2\pi/3 \\ \dfrac{3c^2-3\pi c+\pi^2}{\pi^2} \text{ if } 2\pi/3 \le c \le \pi\\ \end{cases} $$

We can also get the cdf of the Euclidean distance $d$ by substituting $c=2\arcsin(\frac{d}{2r})$: $$P[d] =\begin{cases} \dfrac{\phantom{+3c\pi-+3c}3\arcsin^2(\frac{d}{2r})\phantom{+pi^2+pi^2}}{\pi^2} \text{ if }\ 0\le d \le \sqrt{3}r \\ \dfrac{12\arcsin^2(\frac{d}{2r})-6\pi\arcsin(\frac{d}{2r} )+\pi^2}{\pi^2} \text{ if } \sqrt{3}r \le d \le 2r\\ \end{cases}$$

I simulated this in Mathematica, with code in the comments. The attached graph shows the cdf from 5000 trials in red, vs the formula in blue.

Answer 2

I got there in the following manner. The trickiest parts were defining the nomenclature and figuring out that the function is piecewise.

Definitions

Point A = a point selected on a circle of radius r

Points B and C = additional points chosen at random on that circle

Point K = the center of that circle

AB = segment AB; similarly for AC and BC

d = arbitrarily chosen maximum segment length $0\le d\le 2r$

$\alpha_1$ = the angle AKB $\,\,\,-\pi \le \alpha_1 \le \pi$

$\alpha_2$ = the angle AKC $\,\,\,-\pi \le \alpha_2 \le \pi$

$\alpha_3$ = $\alpha_1-\alpha_2$ $\,\,\,-2\pi \le \alpha_3 \le 2\pi$

$\alpha_d = 2arcsin\frac d{2r}$ $\,\,\,0 \le \alpha_d \le \pi$

Angles are measured from AK, with positive angles clockwise and negative angles the reverse (or it could be vice-versa with no impact)

Figure 1 - Problem Diagram

(note: this diagram shows positive $\alpha_1$ and negative $\alpha_2$. The solution is robust for all combinations of $\alpha_1$ and $\alpha_2$ within the defined ranges).

Solution

We seek $P(AB,AC, BC <d)$. AB and AC are independent of one-another, but BC is dependent on AB and AC. So to answer the question we will need $P(AB < d)$, $P(AC < d)$, and $P(BC < d|AB, AC \lt d)$.

As shown in the question, $d = 2r \cdot \sin \frac{\alpha_d}{2}$. AB and AC are related to $\alpha_1$ and $\alpha_2$ by the same formula so $P(AB \lt d) = P(|\alpha_1| \lt \alpha_d)$ and $P(AC \lt d) = P(|\alpha_2| \lt \alpha_d)$.

Since B and C are chosen at random the PDFs for $\alpha_1$ and $\alpha_2$ are $f(\alpha)=\frac1{2\pi}$ with $-\pi \le \alpha \le \pi$.

Figure 2 - PDF for $\alpha_1$ and $\alpha_2$

From the PDF, $P(|\alpha_1| \lt \alpha_d) = \frac{\alpha_d}{\pi}$ and $P(|\alpha_2| \lt \alpha_d) = \frac{\alpha_d}{\pi}$

Given the ranges of $\alpha_1$ and $\alpha_2$ the range of $\alpha_3$ = $\alpha_1-\alpha_2$ is $-2\pi \le \alpha \le 2\pi$. The PDF of $\alpha_3$ is a triangle with a base on the x axis from $-2\pi$ to $2\pi$ and an apex at f(0) = $\frac1 {2\pi}$

Figure 3 - PDF for $\alpha_3$ (unconditional)

The below graph shows the length of BC for each $\alpha_3$ (y axis is units of r)

Figure 4 - BC length for each $\alpha_3$

However, we are interested in the conditional case $P(BC<d|AB,AC<d)$. Since AB and AC are constrained to be less than d, $|\alpha_1|$ and $|\alpha_2|$ are less than $\alpha_d$, so $\alpha_3$ can only range from $-2\alpha_d \lt \alpha3 \lt 2\alpha_d$.

Figure 5 - Conditional PDF for $\alpha_3$

If $\alpha_d \le \frac{2\pi}3$ then to find $P(BC<d|AB,AC<d)$ we integrate the PDF from $-\alpha_d$ to $\alpha_d$. Once $(2\pi-\alpha_d) \lt 2\alpha_d$ (this occurs when $\alpha_d > \frac{2\pi}3$) we also need to integrate the PDF from ($2\pi - \alpha_d$) to $2\alpha_d$ (and over the same area on the negative side) to capture the declining part of the curve in Figure 4.

For $\alpha_d \le \frac{2\pi}3$

$$P(BC<d|AB,AC<d)=2\cdot \int_0^{\alpha_d}\bigl(-\frac{x}{4\alpha_d^2} + \frac 1{2\alpha_d}\bigr)dx = \frac34$$

For $\alpha_d \ge \frac{2\pi}3$

$$ \begin{align}P(BC<d|AB,AC<d)&=\frac34 + 2\cdot \int_{2\pi-\alpha_d}^{2\alpha_d}\bigl(-\frac{x}{4\alpha_d^2} + \frac 1{2\alpha_d}\bigr)dx\\ \\&= \frac34 + \frac{(3\alpha_d-2\pi)^2}{4\alpha_d^2}\\\\&=\frac{3{\alpha_d}^2+(3\alpha_d-2\pi)^2}{4\alpha_d^2}\end{align}$$

So the probability of all segments being shorter than d is

For $\alpha_d \le \frac {2\pi}3$ $$P(AB, AC, BC < d) = \frac{\alpha_d}{\pi}\cdot \frac{\alpha_d}{\pi}\cdot \frac{3}{4} = \frac{3{\alpha_d}^2}{4\pi^2}$$

For $\alpha_d \ge \frac {2\pi}3$ $$P(AB, AC, BC < d) = \frac{\alpha_d}{\pi}\cdot \frac{\alpha_d}{\pi}\cdot (\frac{3{\alpha_d}^2+(3\alpha_d-2\pi)^2}{4\alpha_d^2})=\frac{3{\alpha_d}^2+(3\alpha_d-2\pi)^2}{4\pi^2}$$

$P(\alpha_1, \alpha_2, \alpha_3 < \alpha_d)$

Recall $d = 2r \cdot \sin \frac{\alpha_d}{2}$. For a circle of radius 1, $\alpha_d$ maps to d as follows

$$ \begin{array}{c|lcr} \alpha_d & \text{d} \\ \hline \frac\pi3 & 1.00 \\ \frac{2\pi}3 & 1.73 \\ \pi & 2.00 \end{array} $$