online advertising
Loading [MathJax]/jax/output/HTML-CSS/jax.js

Thursday, December 17, 2015

Probability of enclosing the center

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 p2p1p3p2p1p3,

Here is the key result, the probability that the center of the square is of the left of p2p1 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 p2p1) × P(center on the left of p3p2) × P(center on the left of p1p3) + P(center on the right of p2p1) × P(center on the right of p3p2) × P(center on the right of p1p3) = 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