Определение площади сложной фигуры с помощью теории вероятностей

Давайте параметры генератора случайных чисел — вид распределения, дисперсию и т.д. — оценим :)

А пример с кругом, мне кажется, не показывает верхней границы ошибки никак. Он претендует на наглядность, но я бы взял радикально другой: область заполнена прямоугольными треугольниками заданной единичной площади, занимающими всю высоту и расположенными в ряд. Это нам дает два профита: исключительно простая функция принадлежности к фигуре и большая неравномерность плотности.

Погрешность должна быть в разы больше и сходится метод будет много дольше.

А вообще, погрешность обратно пропорциональна корню из количества испытаний. Но тут не надо забывать, что для генерации точки мы дважды напрягаем генератор.

Считаем, что генератор случайных чисел идеален — точки равномерно распределены по квадратам и независимы друг от друга.

Пусть площадь фигуры S, площадь большого квадрата, в который бросаются точки, S0, и s = S/S0. С вероятностью s точка попадает внутрь фигуры, с вероятностью 1-s — вовне. Рассмотрим случайную величину, равную 1, если точка попала внутрь фигуры, и 0 иначе; по определению её матожидание равно s, а дисперсия s(1-s).

Пусть бросается N точек. Алгоритм выдаёт в качестве оценки площади среднее значение N независимых случайных величин, описанных в предыдущем абзаце. По центральной предельной теореме при больших N это среднее значение распределено примерно как нормальная случайная величина с матожиданием s и дисперсией s(1-s)/N.

Ясно, что поскольку алгоритм случайный, ему в принципе может фатально не повезти, если все точки случайно окажутся в странных местах, но такое событие исключительно маловероятно. Будем для определённости считать, что события с вероятностью <1% на практике не происходят; число, естественно, можно менять. По формуле вероятности для нормальной случайной величины при больших N отклонение результата, выданного алгоритмом, от правильного значения s по модулю не превосходит

InverseErf(0.995)*sqrt(s(1-s)/N)

в синтаксисе Mathematica, который можно использовать на wolframalpha.com; 0.995, потому что с вероятностью 0.005 отклонение будет больше по модулю и положительно и с вероятностью 0.005 отклонение будет больше по модулю и отрицательно — в сумме получается 1%, на который мы договорились забить. Учитывая, что InverseErf(0.995) примерно равно 2, это даёт возможную абсолютную погрешность метода.

А ещё лучше вместо генератора случайных чисел (который может быть неравномерен) использовать проход по циклу (for x=0 to width step delta for y=0 to height step delta). На него точно можно надеяться.