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 →p1,→p2,→p3. 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 →p2−→p1, →p3−→p2, →p1−→p3,
Here is the key result, the probability that the center of the square is of the left of →p2−→p1 is exactly 12, this is because for each particular event that led to the center being on the left, there is a mirror event (i.e. when →p1 and →p2 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 →p2−→p1) × P(center on the left of →p3−→p2) × P(center on the left of →p1−→p3) + P(center on the right of →p2−→p1) × P(center on the right of →p3−→p2) × P(center on the right of →p1−→p3) = 14
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 →p1,→p2,→p3. 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 →p2−→p1, →p3−→p2, →p1−→p3,
Here is the key result, the probability that the center of the square is of the left of →p2−→p1 is exactly 12, this is because for each particular event that led to the center being on the left, there is a mirror event (i.e. when →p1 and →p2 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 →p2−→p1) × P(center on the left of →p3−→p2) × P(center on the left of →p1−→p3) + P(center on the right of →p2−→p1) × P(center on the right of →p3−→p2) × P(center on the right of →p1−→p3) = 14
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