online advertising

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 $ \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