Problem:
Given a square, we sample three points at random uniformly on the sides of the square. What is the probability that triangle defined by that three points enclose the center of the square?
Solution:
Denote the points as $ \vec{p_1}, \vec{p_2}, \vec{p_3} $. The center of the square is enclosed by the triangle defined by these three points if and only if the center is on the same side of $ \vec{p_2}-\vec{p_1} $, $ \vec{p_3}-\vec{p_2} $, $ \vec{p_1}-\vec{p_3} $,
Here is the key result, the probability that the center of the square is of the left of $ \vec{p_2}-\vec{p_1} $ is exactly $ \frac{1}{2} $, this is because for each particular event that led to the center being on the left, there is a mirror event (i.e. when $ \vec{p_1} $ and $ \vec{p_2} $ are reversed) such that the center being on the right.
With that, we can write out the probability as follow
P(enclose) = P(center on the left of $ \vec{p_2}-\vec{p_1} $) $ \times $ P(center on the left of $ \vec{p_3}-\vec{p_2} $) $ \times $ P(center on the left of $ \vec{p_1}-\vec{p_3} $) $ +
$ P(center on the right of $ \vec{p_2}-\vec{p_1} $) $ \times $ P(center on the right of $ \vec{p_3}-\vec{p_2} $) $ \times $ P(center on the right of $ \vec{p_1}-\vec{p_3} $) = $ \frac{1}{4} $
The following simple Monte Carlos simulation proves that I am correct with the value of the probability.
Given a square, we sample three points at random uniformly on the sides of the square. What is the probability that triangle defined by that three points enclose the center of the square?
Solution:
Denote the points as $ \vec{p_1}, \vec{p_2}, \vec{p_3} $. The center of the square is enclosed by the triangle defined by these three points if and only if the center is on the same side of $ \vec{p_2}-\vec{p_1} $, $ \vec{p_3}-\vec{p_2} $, $ \vec{p_1}-\vec{p_3} $,
Here is the key result, the probability that the center of the square is of the left of $ \vec{p_2}-\vec{p_1} $ is exactly $ \frac{1}{2} $, this is because for each particular event that led to the center being on the left, there is a mirror event (i.e. when $ \vec{p_1} $ and $ \vec{p_2} $ are reversed) such that the center being on the right.
With that, we can write out the probability as follow
P(enclose) = P(center on the left of $ \vec{p_2}-\vec{p_1} $) $ \times $ P(center on the left of $ \vec{p_3}-\vec{p_2} $) $ \times $ P(center on the left of $ \vec{p_1}-\vec{p_3} $) $ +
$ P(center on the right of $ \vec{p_2}-\vec{p_1} $) $ \times $ P(center on the right of $ \vec{p_3}-\vec{p_2} $) $ \times $ P(center on the right of $ \vec{p_1}-\vec{p_3} $) = $ \frac{1}{4} $
The following simple Monte Carlos simulation proves that I am correct with the value of the probability.
namespace ManagedWorkspace { using System; static class Program { static void Main(string[] args) { Random random = new Random(0); int numerator = 0; int denominator = 0; for (int i = 0; i < 1000000; i++) { double x1, y1, x2, y2, x3, y3; GeneratePoint(random, out x1, out y1); GeneratePoint(random, out x2, out y2); GeneratePoint(random, out x3, out y3); double cross1 = x1 * y2 - x2 * y1; double cross2 = x2 * y3 - x3 * y2; double cross3 = x3 * y1 - x1 * y3; if ((cross1 > 0 && cross2 > 0 && cross3 > 0) || (cross1 < 0 && cross2 < 0 && cross3 < 0)) { numerator++; } denominator++; } Console.WriteLine(numerator + "/" + denominator); } private static void GeneratePoint(Random random, out double x1, out double y1) { int edge = random.Next(4); switch (edge) { case 0: y1 = -1; x1 = random.NextDouble() * 2 - 1; return; case 1: x1 = 1; y1 = random.NextDouble() * 2 - 1; return; case 2: y1 = 1; x1 = random.NextDouble() * 2 - 1; return; case 3: x1 = -1; y1 = random.NextDouble() * 2 - 1; return; default: throw new InvalidOperationException("Should not happen"); } } } }
No comments:
Post a Comment