Вычисление площади методом Монте-Карло

[Asker Tasker]

Здравствуйте. Поставлена следующая задача: задан некоторый набор прямоугольников, их объединение погружают в большой прямоугольник - и бросают в него N точек. Из них n попадут в объединение заданных прямоугольников - и мы приблизительно вычисляем площадь этого объединения, умножим число n/N на площадь большого прямоугольника.

Вопрос возник следующий. Можно ли как-то оценить точность вычисления на основе количества точек или количества бросаний? Видимо, точность будет означать вероятность того, что найденная величина соответствует настоящей площади. Интуитивно понятно, что если проводить бросание не один раз, а, например, сто, и усреднить полученные значения, то скорее всего это значение будет ближе к настоящему, чем значение, полученное после первого броска. Также, кажется, что если бросать не десять точек, а опять, например, сто, то найденное число больше должно соответствовать действительности, чем в случае десяти точек.

Есть ли какая-то формула для оценки точности или какой-то метод или что-то ещё? Заранее спасибо.

[ИСН]

Ну Вы же можете найти распределение возможных n при данном N, его сигму и всё такое прочее?

[ewert]

Asker Tasker в сообщении #593588 писал(а):

Есть ли какая-то формула для оценки точности

Эта стандартная статистическая задача вот какого сорта (кстати, прямоугольность внутренней области тут совершенно не при чём -- ровно с тем же успехом можно задавать область вообще любой системой неравенств).

Известно, что мы имеем дело со схемой Бернулли с некоторым неизвестным параметром $p$, который и надо, собственно, оценить по большой выборке; а также оценить и погрешность (говоря конкретнее -- дисперсию оценки по данной выборке).

Формально -- задачка занудна. Но практически (учитывая, что ожидаемое $p$ при разумной постановке задачи не слишком мало и не слишком близко к единице, при том что количество отсчётов велико) -- все оценки практически сводятся центральной предельной теоремой к соотв. оценкам для того нормального распределения, к которому сводится той теоремой усреднённое по многим отсчётам распределение Бернулли.

[Yu_K]

http://projecteuler.net/problem=212 напомнило ассоцитиативно...

[Joker_vD]

Если мы считаем интеграл $I=\int\limits_0^1 f(x)dx$, кидая $n$ точек на отрезок $[0,1]$, то погрешность будет меньше $\varepsilon$ при $n>\dfrac{9\max^2|f(x)|}{\varepsilon^2}$. При выводе, правда, используется правило трех сигм.

[Asker Tasker]

Всем спасибо.
Но с теорией вероятностей я дело имел лишь косвенно и отдалённо, так что "пошёл читать про центральную предельную теорему".

Joker_vD в сообщении #593702 писал(а):

Если мы считаем интеграл $I=\int\limits_0^1 f(x)dx$, кидая $n$ точек на отрезок $[0,1]$, то погрешность будет меньше $\varepsilon$ при $n>\dfrac{9\max^2|f(x)|}{\varepsilon^2}$. При выводе, правда, используется правило трех сигм.

А можно чуть подробнее, как мы оценку для n получаем?

ewert в сообщении #593623 писал(а):

Эта стандартная статистическая задача вот какого сорта (кстати, прямоугольность внутренней области тут совершенно не при чём -- ровно с тем же успехом можно задавать область вообще любой системой неравенств).

Я понимаю, но задача была поставлена именно в таком виде, как я написал, поэтому решил ничего не менять - и спрашивать как есть.

Yu_K в сообщении #593677 писал(а):

http://projecteuler.net/problem=212 напомнило ассоцитиативно...

Спасибо за ссылку. Не слышал раньше об этом проекте. Вроде бы интересно.