17
$\begingroup$

Three uniformly random points on the circle $x^2+y^2=1$ are the vertices of a triangle.

What is the probability that $(0,0)$ is inside the triangle's incircle?

(This a variation of the question "What is the probability that $(0,0)$ is inside the triangle?".)

A simulation with $10^8$ trials gives $P\approx 0.129963$. Is the probability exactly $0.13$? If so, this would be the weirdest geometrical probability I have ever seen.

My attempt:

Let $d=$ distance between the circles' centres, and let $r=$ radius of the triangle's incircle.

enter image description here

We are looking for $P(d<r)$.

Euler's triangle formula tells us that $d=\sqrt{1-2r}$.

So we are looking for $P(\sqrt{1-2r}<r)=P(r>\sqrt2-1)$. I do not know how to calculate this probability.

I know that $r=\sqrt{\frac{(s-a)(s-b)(s-c)}{s}}$ where $a,b,c$ are the side lengths of the triangle and $s=\frac{a+b+c}{2}$.

$\endgroup$
11
  • 4
    $\begingroup$ Dan, how do you find these questions? $\endgroup$
    – Sahaj
    Commented Jan 28 at 5:07
  • 4
    $\begingroup$ It appears to be your routine to go about every week investigating random geometry and making brilliant questions out of them. $\endgroup$
    – Sahaj
    Commented Jan 28 at 5:08
  • 2
    $\begingroup$ I would be very surprised if this nice-in-base-$10$ rational number was the answer. $\endgroup$ Commented Jan 28 at 14:45
  • 2
    $\begingroup$ I also simulated it using $10^8$ samples and obtained a $99.9999\%$ confidence interval of $$\hat{p}=0.129993\pm0.000165.$$ $\endgroup$ Commented Jan 28 at 15:01
  • 7
    $\begingroup$ There is also this formula $r/R=\cos A+\cos B + \cos C-1$ I find it more convenient. $\endgroup$
    – kabenyuk
    Commented Jan 28 at 15:43

3 Answers 3

14
$\begingroup$

By using the formula found by kabenyuk, we have:

$$\begin{align} \frac{r}{R}>\sqrt{2}-1&\iff\cos(A)+\cos(B)+\cos(C) \ge \sqrt{2} \\ &\iff \cos(A) +\cos(B)-\cos(A)\cos(B)+\sqrt{(1-\cos^2(A))(1-\cos^2(B))}\ge \sqrt 2 \tag{1} \end{align}$$

Let the point $C$ fixed on the circle, the points $A$ and $B$ move independently and uniformly over the cirle, then the two angles $(A,B)$ (by abusing the notation, angle are also denoted by the letters $A$ and $B$) independent and uniformly distributed over the area $\left[0,\pi\right]^2 \cap\{A+B \le\pi \}$.

Here is the region $\Omega$ that satisfies $(1)$, plotted with Mathematica

 RegionPlot[{Sqrt[(1 - Cos[A]^2) (1 - Cos[B]^2)] >= 
 Cos[A]*Cos[B] - Cos[A] - Cos[B] + Sqrt[2], A + B <= Pi}, {A, 0, 
 Pi}, {B, 0, Pi}]

enter image description here

From the graph, we observe that $(A,B)$ that satisfies $(1)$ satisfies automatically the condition $A+B \le \pi$. So, it suffices to solve $(1)$ with the constraint $ \{0\le A \le \pi\} \cap \{0\le B \le \pi\}$.

Denote $y = \cos(B)$ and solve the equation $$\cos(A) +y-\cos(A)y+\sqrt{(1-\cos^2(A))(1-y^2)}\ge \sqrt 2$$ with the constraints $0\le A \le \pi$ and $-1 \le y \le 1$:

Reduce[Sqrt[(1 - Cos[A]^2) (1 - y^2)] >= 
Cos[A]*y - Cos[A] - y + Sqrt[2] && 0 <= A <= Pi && -1 <= y <= 1, y]

We obtains a closed-form expression for $y$ in function of $A$: $$\begin{align} &f_1(A) \le y \le f_2 (A) \hspace{2cm} \text{for }A \in \left[\arccos(2\sqrt{2}-2),\frac{\pi}{2} \right]\\ &f_1(A) = \frac{1}{2} \left(\sqrt{2} - \cos(A) \color{red}{-} \sqrt{\frac{(2 - 2 \sqrt{2} + \cos(A)) (\cos(A) + \cos^2(A))}{(-1 + \cos(A))}}\right)\\ &f_2(A) = \frac{1}{2} \left(\sqrt{2} - \cos(A) \color{red}{+} \sqrt{\frac{(2 - 2 \sqrt{2} + \cos(A)) (\cos(A) + \cos^2(A))}{(-1 + \cos(A))}}\right) \end{align}$$

We deduce then $$\color{red}{\Omega = \{(A,B)| (A,B)\in \left[\arccos(2\sqrt{2}-2),\frac{\pi}{2} \right] \times [\arccos(f_2(A),\arccos(f_1(A) ] \}}$$

Let us check again graphically:

Plot[{ArcCos[f1[A]], ArcCos[f2[A]]}, {A, ArcCos[2 (-1 + Sqrt[2])], 
\[Pi]/2},PlotRange -> {{0, Pi}, {0, Pi}}, AspectRatio -> 1]

we obtain exactly the same graph as above

enter image description here

The probability is finally calculated with a single integral:

$$\color{red}{P = \frac{2}{\pi^2} \int_{\arccos(2\sqrt{2}-2)}^{\frac{\pi}{2}}\left( \arccos(f_1(A)-\arccos(f_2(A) \right)dA \approx 0.1299825992533093}$$

2/Pi^2*NIntegrate[ArcCos[f1[A]]-ArcCos[f2[A]],{A,ArcCos[2(-1 +Sqrt[2])],\[Pi]/2}]

where $$\begin{align} &\color{red}{f_1(A) = \frac{1}{2} \left(\sqrt{2} - \cos(A) - \sqrt{\frac{(2 - 2 \sqrt{2} + \cos(A)) (\cos(A) + \cos^2(A))}{(-1 + \cos(A))}}\right)}\\ &\color{red}{f_2(A) = \frac{1}{2} \left(\sqrt{2} - \cos(A) + \sqrt{\frac{(2 - 2 \sqrt{2} + \cos(A)) (\cos(A) + \cos^2(A))}{(-1 + \cos(A))}}\right)} \end{align}$$

$\endgroup$
4
  • $\begingroup$ Are you sure the distribution of angles $A$ and $B$ in $[0,\pi]$ is uniform? I guess that the probability density function should be increasing, not uniform. (My guess is supported by a quick simulation.) This would make a slight difference in the final answer. $\endgroup$
    – Dan
    Commented Jan 29 at 0:37
  • $\begingroup$ @Dan Yes, the distribution of the angles $\angle A$ (aka: $\angle CAB$) and $\angle B$ (aka: $\angle CBA$) is uniformly in $[0,\pi]$. If we make the point $C$ fixed on the circle, as the point $B$ is uniformly distributed on the cirle centered at $O$, the angle $\angle COB$ is uniformly distributed in $[0,2\pi]$. And because $\angle COB = 2\angle CAB$ ($=2\angle A$), we deduce then the angles $\angle A$ is uniformly distributed in $[0,\pi]$. $\endgroup$
    – NN2
    Commented Jan 29 at 0:50
  • $\begingroup$ I get it now. If we draw a graph with an $A$-axis and a $B$-axis, the combinations of $A$ and $B$ will uniformly fill the right triangle with vertices $(0,0), (0,\pi), (\pi,0)$ on this graph (as @Sangchul's answer describes). But if we look only at say $A$, the distribution of $A$ is not uniform in $[0,\pi]$; the density function of $A$ is decreasing (in my previous comment, I mistakenly wrote "increasing"). $\endgroup$
    – Dan
    Commented Jan 29 at 1:28
  • $\begingroup$ @Dan Yes, and with the constraint $0\le A + B \le \pi$ (as $ABC$ is a triangle), the two angles $(A,B)$ becomes uniformly distributed on the triangle $(0,0), (0,\pi)$ and $(\pi, 0)$. $\endgroup$
    – NN2
    Commented Jan 29 at 1:32
9
$\begingroup$

Edit : My first intention was to propose a graphical representation.

Meanwhile, I have discovered a solution (which has common points with the solution by NN2 but with a distinct path, and slightly simpler) :

Let $$\begin{cases}k&:=&\tfrac12(1-\sqrt{2})\approx -0.2071\\x_0&:=&\operatorname{asin}(\tfrac12(2-\sqrt{2}))\approx 0.2973\\x_1&:=&\operatorname{asin}(\tfrac12 \sqrt{2})=\tfrac{\pi}{4}\approx 0.7854\end{cases}.$$

and

$$f(x):=\operatorname{asin} \left(\frac{k}{\sin(x)}-\sin(x)\right)+\frac{\pi}{2}\tag{0}$$

The looked for probability can be given the simple expression :

$$\frac{8}{\pi^2}\int_{x_0}^{x_1} f(x) dx\approx 0.1299825992\tag{*}$$

Proof of (*) :

WLOG, we can assume that one of the points is $A=(1,0)$ and the two others are $B=(\cos u, \sin u)$, $C=(\cos v, \sin v)$.

We can assume (see figure below) that $u \in [0, \pi]$, and $v \in [\pi,2 \pi]$. indeed, cases where $\pi < v <u$ or $u<v<\pi$ do not contribute to the region of plane $(u,v)$ we are interested in.

Using the formula given by @kabenyuk

$$r/R=\cos A+\cos B + \cos C-1$$

which becomes, with $R=1$ and level line $r_0=\sqrt{2}-1$ :

$$r=\cos((v-u)/2)+\cos((2 \pi - v)/2)+\cos(u/2)-1 \ge r_0$$

Otherwise said, we are interested in level line

$$r=r(u,v)=(\cos(u/2)-\cos(v/2))+(\cos((u-v)/2)-1)=r_0\tag{**}$$

Therefore, in a $(u,v)$ coordinate system (see figure), region (R) is the interior of the largest of the represented level lines of the function described by $(**)$ for $r$ ranging from $r=r_0$ to its extreme value $r_{max}=\tfrac12$, achieved in the single point with coordinates $(u,v)=(\tfrac{2\pi}{3},\tfrac{4\pi}{3})$, which, in a natural way, corresponds to the equilateral triangle case.

But (**) can be written :

$$-2 \sin\left(\tfrac14(u+v)\right)\sin\left(\tfrac14(u-v)\right)-2\left(\sin\left(\tfrac14(u-v)\right)\right)^2=\sqrt{2}-1\tag{***}$$

Consider now the following change of variable which can be interpreted (in a reverse way) as a linear transformation $(L)$ :

$$\begin{cases}a&=&\tfrac14(u-v)\\b&=&\tfrac14(u+v)\end{cases},$$

allowing to write (***) under the factorized form :

$$-\sin a (\sin a + \sin b) = k \ \ \ \text{with} \ k = \frac{r_0}{2}=\frac{\sqrt{2}-1}{2}$$

$$\sin b = \sin a - \frac{k}{\sin a}$$

which gives (in order for variable $b$ to take positive values) :

$$b=\operatorname{asin} \left(\frac{k}{\sin(a)}-\sin(a)\right)+\frac{\pi}{2}$$

We have obtained in this way function $f$ given at the beginning in (0). With its twin function $-f$, the union of their curves, represented in blue and green resp. in figure 1, can clearly be interpreted as the image of the initial level curve by transformation (L). Therefore we have to multiply the integral of $f$ by $2$ (in order to account of $-f$), then by $8$, in order to recover the area of the initial shape. Why $8$ ? Because it is the inverse jacobian of linear transformation (L) (whose determinant is $1/8$). Therefore, we must multiply the area between the blue curve and the $u$-axis by $16$ in order to retrieve the initial area.

Now, how can we express the probability out of this relative area ? The area value obtained just above must be divided by the total area $2\pi^2$ (enclosed by black axes in the figure) under the assumptions of uniform distribution of angles $u,v$, ending the proof of formula (*).

Have a look at the SAGE program below giving some complementary information.

enter image description here

Fig. 1 : Representation in the $(u,v)$ plane. The small oval shape is the image of the big one (the largest of level lines) by linear transform $(L)$.

Remark : The identity about $r/R$ recalled by kabenyuk could have been replaced by the equivalent formula :

$$r/R=4 \sin(A/2)\sin(B/2)\sin(C/2)$$

SAGE program :

 var('x y t')
 x0=asin((2-sqrt(2))/2);x1=asin(sqrt(2)/2)
 k=(1-sqrt(2))/2
 f(x)=asin(k/sin(x)-sin(x))+pi/2 
 I0=sage.calculus.integration.numerical_integral(f,x0,x1,eps_abs=1e-15, eps_rel=1e-15);
 J0=I0[0]*8/(pi^2);show(J0.n(40)); # gives value 0.1299825992...
 e=cos(x/2)-cos(y/2)+cos((x-y)/2)-sqrt(2)
 g=point([[2*pi/3,4*pi/3],[x0,0],[x1,0]])
 g+=line([[pi,0],[0,0],[0,2*pi]],color='black')
 nll=5;# number of level lines
 for a in range(nll) :
    g+=implicit_plot(e-a/50,(x,0,pi),(y,-0.4,2*pi),color='red')
 g+=parametric_plot((t,f(t)),(t,x0,x1),plot_points=400,color='blue')
 g+=parametric_plot((t,-f(t)),(t,x0,x1),plot_points=400,color='green')           
 g
$\endgroup$
5
  • $\begingroup$ I'm getting $\frac{\left((x_1-x_0)\frac{\pi}{2}-I\right)}{8\pi^2}\approx 0.01739$. $\endgroup$
    – Dan
    Commented Jan 29 at 0:48
  • $\begingroup$ Sorry, it is $8\frac{\left((x_1-x_0)\frac{\pi}{2}+I\right)}{\pi^2}$ with $I=\int_{x_0}^{x_1} asin(k/\sin(x)-\sin(x))dx$ $\endgroup$
    – Jean Marie
    Commented Jan 29 at 8:46
  • $\begingroup$ Sorry, but now I'm getting $\frac{8}{\pi^2}I\approx 1.11307$. $\endgroup$
    – Dan
    Commented Jan 29 at 12:57
  • $\begingroup$ [Sorry again : It must be because I have taken $(x_1-x_0)$instead of its opposite but have you included this term in your calculation ?] But in fact, as I have just completely re-written my answer with justifications, it is probably better to restart from the simpler expression I just gave for the probability. $\endgroup$
    – Jean Marie
    Commented Jan 29 at 13:44
  • $\begingroup$ Thanks. Yes, it (*) is a relatively simple expression for the probability. $\endgroup$
    – Dan
    Commented Jan 29 at 14:32
8
$\begingroup$

Long Comment. It turns out that

$$\mathbf{P}(d<r) = 2\mathbf{P}(\cos U+\cos V>\cos(U+V)+\sqrt{2}), \tag{*} $$

where $U$ and $V$ are independent and uniformly distributed on $[0,\pi]$.

Derivation. The inradius $r$ is given by

$$ r = R(\cos A + \cos B + \cos C - 1) $$

where $R$ is the circumradius and $A$, $B$, $C$ are angles of the triangle. If the vertices are sampled uniformly at random from the unit circle, then $R = 1$ and $(A, B)$ are uniformly distributed on the triangle with vertices $(0, 0)$, $(0, \pi)$, and $(\pi, 0)$.

Now let $U$, $V$ be independent samples from $\mathcal{U}[0,\pi]$. Then the distribution of $(A, B)$ can be realized by the conditional distribution $(U, V \mid U + V < \pi)$. Hence

\begin{align*} \mathbf{P}(d < r) &= \mathbf{P}(\cos A + \cos B + \cos C > \sqrt{2}) \\ &= \mathbf{P}(\cos U + \cos V > \sqrt{2} + \cos(U + V) \mid U + V < \pi) \end{align*}

However, the identity

\begin{align*} \cos U + \cos V - \cos(U + V) - 1 = 4 \sin \frac{U}{2} \sin \frac{V}{2} \sin \frac{\pi-U-V}{2} \end{align*}

shows that $\cos U + \cos V > \sqrt{2} + \cos(U + V)$ entails the condition $U + V < \pi$. Hence we conclude the desired equality $\text{(*)}$. $\square$

Now, a numerical computation based on $\text{(*)}$ shows that

$$\mathbf{P}(d<r) \approx 0.1299825992533063755,$$

and I was not able to identify its closed form.


Numerical Method Used. Here is the outline of the numerical technique I used to approximate $\mathbf{P}(d<r)$.

First, let $\mathcal{C}$ denote the contour $\cos x + \cos y = \cos(x+y) + \sqrt{2}$ in the region $[0, \pi]^2$. As in @NN2's answer, we can visually confirm that $\mathcal{C}$ is a simple closed curve. Now,

  • Fix an point $(x_0, y_0)$ enclosed by $\mathcal{C}$. For example, we may choose $(x_0, y_0) = (1, 1)$ or $(x_0, y_0) = (\frac{\pi}{3}, \frac{\pi}{3})$.

  • Parametrize $\mathcal{C}$ by $(x, y) = (x_0, y_0) + f(t) (\cos t, \sin t)$ for $t \in \mathbb{R}/2\pi\mathbb{Z}$.

Parametrization

Then the area enclosed by $\mathcal{C}$ can be computed by the integral

$$ \text{Area} = \int_{0}^{2\pi} \frac{f(t)^2}{2} \, \mathrm{d}t. $$

Although computing the value of $f(t)$ is expensive, requiring some optimization techniques, it turns out that $\text{Area}$ is very well approximated by a simple "right-endpoint approximation"

$$ \text{Area} \approx \sum_{k=1}^{N} \frac{f(2\pi k/N)^2}{2} \cdot \frac{2\pi}{N} \tag{*} $$

Normally, right-endpoint approximation yields a poor approximation of the original integral and we often needs to use a formula in the Newton–Cotes family (which encompasses Trapezoidal rule, Simpson's rule, etc.). However, the fact that $f(t)$ is a smooth $2\pi$-periodic function makes everything different, rendering all the Newton–Cotes formulas essentially identical. In particular, this means that $\text{(*)}$ demonstrates super-polynomial speed of convergence. (This can also be proved using Fourier analysis.)

Below is a Mathematica code implementing $\text{(*)}$:

(* Defining f(t) *)
{x0, y0} = {1, 1};
f[t_] := (r /. 
    FindRoot[
        Cos[x0 + r Cos[t]] + Cos[y0 + r Sin[t]] == Cos[x0 + r Cos[t] + y0 + r Sin[t]] + Sqrt[2], 
        {r, Pi/6}, 
        WorkingPrecision -> 30
    ]);

(* Implementing the right-endpoint approximation *)
n = 180;
2/Pi Mean[Table[f[(2 Pi)/n k]^2, {k, n}]]
Clear[x0, y0, f, n];

Evaluation example

$\endgroup$
5
  • $\begingroup$ Thanks! If you don't mind, I have a few questions. (1) At the beginning, did you mean $U$ and $V$ are in $[0,2\pi]$ or $[0,\pi]$? It makes a difference, because of the $\cos(U+V)$ term. (2) After establishing (*), how did you numerically calculate the probability? It is the proportional area of the region enclosed by $\cos x+\cos y=\cos(x+y)+\sqrt2$ and the triangle with vertices $(0,0),(0,\pi),(\pi,0)$, but how to calculate that? (3) I noticed your approximation, and @NN2's, have a slight discrepancy: $0.12998259925330\color{red}{6}3755$ vs. $0.12998259925330\color{red}{9}3$. Is that a typo? $\endgroup$
    – Dan
    Commented Jan 28 at 22:03
  • $\begingroup$ Oh, I see how to numerically calculate the area now, by getting $y$ in terms of $x$, similar to @NN2's answer. $\endgroup$
    – Dan
    Commented Jan 28 at 22:42
  • 1
    $\begingroup$ @Dan maybe you have found the same formula as given in my Edit that I will explain tomorrow. $\endgroup$
    – Jean Marie
    Commented Jan 29 at 0:13
  • 1
    $\begingroup$ @Dan, (1) Indeed $2\pi$ was a typo. $[0,\pi]$ is the correct one. Sorry for the confusion! (2) Directly computing the resulting 2D integral is inefficient due to the discontinuous nature of the integrand. I parametrized the contour $\cos x+\cos y=\cos(x+y)+\sqrt{2}$ in the form $(x,y)=(x_0,y_0)+f(t)(\cos t,\sin t)$ for a suitable interior point $(x_0,y_0)$, and then numerically evaluated the integral $$\frac{2}{\pi^2}\int_{0}^{2\pi}\frac{f(t)^2}{2}\,\mathrm{d}t.$$ $\endgroup$ Commented Jan 29 at 1:46
  • 1
    $\begingroup$ @Dan, I added more details about the numerical method I used in my answer. $\endgroup$ Commented Jan 29 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .