Suppose you have an equilateral triangle. You pick three random points, one along each of its three edges, uniformly along the length of each edge — that is, each point along each edge has the same probability of being selected.
With those three randomly selected points, you can form a new triangle inside the original one. What is the probability that the center of the larger triangle also lies inside the smaller one?
Let's assume that the original triangle is the equilateral triangle with side lengths whose center is at the origin of the $xy$-plane. Thus the vertices of the original triangle are at $A(-1/2, -\sqrt{3}/4)$, $B(0,\sqrt{3}/4)$, and $C(1/2, -\sqrt{3}/4).$ Let's say that $t, u, v \sim U(0,1)$ are i.i.d. uniformly distributed, then the random points along the edges of \Delta ABC can be modeled as \begin{align*} X &= \left(t - \frac{1}{2}, -\frac{\sqrt{3}}{4}\right) \\ Y &= \left(-\frac{1-u}{2}, \frac{\sqrt{3}(2u-1)}{4}\right) \\ Z &= \left(\frac{1-v}{2}, \frac{\sqrt{3}(2v-1)}{4} \right).\end{align*}
If we wanted to just brute force our way into the solution, we could just use the test that $O = (0,0) \in \Delta XYZ$ if and only if $$A_{\Delta OXY} + A_{\Delta OXZ} + A_{\Delta OYZ} = A_{\Delta XYZ}.$$ However, we can also create the appropriate integral to calculate the theoretical answer. In this case, we will actually do both to make sure both are roughly on the right track.
Let's first focus on the siutation when $t \in \left[0,\frac{1}{2}\right],$ or equivalently when $X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \}.$ In this case, we can drawn a line from $X$ through the origin $O$ and see that if $O$ is in the $\Delta XYZ$ then we must have $Z = (z_1, z_2)$ located such that $$\frac{\sqrt{3}}{4} z_1 + \left( t - \frac{1}{2}\right) z_2 \geq 0.$$ Therefore, in terms of $t$ and $v,$ we have \begin{align*} 0 & \leq \frac{\sqrt{3}}{4} \frac{1-v}{2} + \left(t-\frac{1}{2}\right) \frac{\sqrt{3} (2v-1)}{4}\\ &= \frac{\sqrt{3}}{8} \Big( 1- v + (2t-1) (2v - 1) \Big)\\ &= \frac{\sqrt{3}}{8} \left( (4t-3) v + 2(1 - t)\right),\end{align*} or equivalently $$v \leq \frac{2(1-t)}{3-4t}.$$ See the figure below for context.
Similarly, we can draw a line from $Y$ through the origin $O$ and see that if $O$ is in the triangle $\Delta XYZ$ then we must have $Z = (z_1, z_2)$ located such that $$\frac{\sqrt{3}}{4} (2u-1) z_1 + \frac{1-u}{2} z_2 \geq 0.$$ Therefore, in terms of $u$ and $v,$ we have $$\begin{align*} 0 &\leq \frac{\sqrt{3} (2u-1)}{4} \frac{1-v}{2} + \frac{1-u}{2} \frac{\sqrt{3} (2v-1)}{4} \\ &= \frac{\sqrt{3}}{8} \Big( (2u-1) (1-v) + (1-u) (2v-1) \Big) \\ &= \frac{\sqrt{3}}{8} \Big( (3u - 2) + (3 - 4u) v \Big),\end{align*}$$ or equivalently $$v \geq \frac{2 - 3u}{3-4u}.$$ Since we naturally have $v \in [0,1],$ we see that if $t \in \left[ 0, \frac{1}{2} \right]$ and $u \in [0,1]$ that O is in the triangle $\Delta XYZ$ if and only if $$v \in \left[ 0 \vee \frac{2-3u}{3-4u}, \frac{2(1-t)}{3-4t} \right].$$ So \begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} &= \int_0^{\frac{1}{2}} \int_0^1 \frac{2(1-t)}{3-4t} - \max \{ 0, \frac{2-3u}{3-4u} \} \,du \,dt \\ &= \int_0^{\frac{1}{2}} \left(\frac{2(1-t)}{3-4t} - \int_0^{\frac{2}{3}} \frac{2-3u}{3-4u} \,du\right) \,\, dt.\end{align*} Using partial fractions, we get $$\int_0^{\frac{2}{3}} \frac{2-3u}{3-4u} \,du = \int_0^{\frac{2}{3}} \frac{3}{4} - \frac{1}{4(3-4u)} \,du = \left[ \frac{3}{4} u + \frac{1}{16} \ln \left| 3 - 4u \right| \right]^{\frac{2}{3}}_0 = \frac{1}{2} - \frac{1}{8} \ln 3.$$ So, again by applying the partial fractions technique we get that the probability is \begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} &= \int_0^{\frac{1}{2}} \frac{2(1-t)}{3-4t} - \frac{1}{2} + \frac{1}{8} \ln 3 \,dt \\ &= \int_0^{\frac{1}{2}} \frac{1}{2} + \frac{1}{2(3-4t)} - \frac{1}{2} + \frac{1}{8} \ln 3 \,dt\\ &= \left[ -\frac{1}{8} \ln \left| 3 - 4t \right| + \frac{t}{8} \ln 3 \right]^{\frac{1}{2}}_0 = \frac{3 \ln 3}{16}.\end{align*}
From symmetry (by switching the restrictions of $Y$ and $Z$ whenever $t \in \left[\frac{1}{2}, 1\right]$), we see that $$\mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_+ \times \{ -\frac{\sqrt{3}}{4} \} \right\} = \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_- \times \{ -\frac{\sqrt{3}}{4} \} \right\} = \frac{3 \ln 3}{16},$$ so we are left with the probability that the origin is in the randomly selected triangle $\Delta XYZ$ as \begin{align*}\mathbb{P} \left\{ O \in \Delta XYZ \right\} &= \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_-\times \{ -\frac{\sqrt{3}}{4} \} \right\} + \mathbb{P} \left\{ O \in \Delta XYZ \Big| X \in \mathbb{R}_+ \times \{ -\frac{\sqrt{3}}{4} \} \right\}\\ &= \frac{3 \ln 3}{8} \approx 0.41197960825.... .\end{align*}
As indicated, we can also use brute force to arrive at / verify this conclusion using the short python script shown below.
import numpy as np
from numpy.random import uniform
def area_triangle(A, B, C):
cross = (B[0] - A[0]) * (C[1] - A[1]) - (C[0] - A[0]) * (B[1] - A[1])
return 0.5 * np.abs(cross)
num_samples = 1000
num_runs = 1000
O = np.array([0.,0.])
success = np.zeros(shape=(num_samples, num_runs))
for k in range(num_runs):
U = uniform(size=(num_samples, 3))
for i in range(num_samples):
u = U[i,:]
X = np.array([-0.5, -0.25*np.sqrt(3)]) + u[0] * np.array([ 1.0, 0.0])
Y = np.array([-0.5, -0.25*np.sqrt(3)]) + u[1] * np.array([ 0.5, 0.5 * np.sqrt(3)])
Z = np.array([ 0.5, -0.25*np.sqrt(3)]) + u[2] * np.array([-0.5, 0.5 * np.sqrt(3)])
a1 = area_triangle(O, X, Y)
a2 = area_triangle(O, X, Z)
a3 = area_triangle(O, Y, Z)
a = area_triangle(X, Y, Z)
if np.abs(a - a1 - a2 - a3) < 1e-6:
success[i,k] += 1
print('Over %d successive tests, each using %d samples, the probability of having the origin within ' % (num_runs, num_samples))
print('the random triangle is %f with SEM of %f.' % (success.mean(), success.mean(axis=0).std()/np.sqrt(num_runs)))
print('This compares favorably to the theoretical answer 3 * ln(3) / 8 = %f' % (3. * np.log(3) / 8.))
No comments:
Post a Comment