Когда применять вероятностный алгоритм и метод Монте-Карло?

Вероятностный алгоритм использует случайный выбор как часть вычисления. Один запуск может дать приближение или небольшой риск ошибки, поэтому результат описывают не только…

Вероятностный алгоритм использует случайный выбор как часть вычисления. Один запуск может дать приближение или небольшой риск ошибки, поэтому результат описывают не только значением, но и вероятностью, доверительным интервалом либо гарантией после повторений. Случайность не освобождает от анализа.

Идея Монте-Карло

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

Закон больших чисел

При росте числа независимых наблюдений выборочная доля приближается к истинной вероятности. Типичный масштаб случайной ошибки уменьшается примерно как 1/√N, поэтому для десятикратного улучшения точности может потребоваться примерно в сто раз больше испытаний.

Воспроизводимость

Генератор псевдослучайных чисел детерминирован начальным seed. Фиксированный seed полезен для повторения теста, но одна последовательность не показывает устойчивость. Для оценки разброса проводят серию запусков с разными seed и сохраняют параметры эксперимента.

Монте-Карло и Лас-Вегас

Алгоритм Монте-Карло обычно ограничивает время, но допускает вероятность неточного ответа. Алгоритм Лас-Вегас всегда возвращает корректный ответ, а случайным является время работы. При классификации нужно смотреть на гарантию результата, а не просто на наличие генератора случайных чисел.

Проверка эксперимента

Сравните оценку на N, 4N и 16N испытаниях, измерьте разброс нескольких серий и сопоставьте с известным тестовым значением. Укажите модель распределения точек и источник систематического смещения. Такой отчёт превращает случайный запуск в проверяемый вычислительный эксперимент.

Случайность не отменяет измеримость

Для оценки π генерируют точки в единичном квадрате и считают долю попавших в четверть круга. Фиксированный seed делает эксперимент воспроизводимым, но не улучшает статистическую точность. Погрешность Монте-Карло обычно убывает примерно как 1/√n: чтобы получить в десять раз меньший шум, требуется примерно в сто раз больше испытаний.

from random import Random

def estimate_pi(samples: int, seed: int) -> float:
    random = Random(seed)
    inside = 0
    for _ in range(samples):
        x, y = random.random(), random.random()
        inside += x * x + y * y <= 1
    return 4 * inside / samples

print(estimate_pi(100_000, seed=2026))

Один запуск не показывает разброс. Нужны независимые серии с разными seed, среднее и оценка вариативности. Генератор псевдослучаен и не подходит автоматически для криптографических задач.

Практика: эксперимент с доверительным диапазоном

Для размеров 100, 1000, 10 000 и 100 000 выполните по двадцать независимых оценок π. Для каждого размера посчитайте среднее, минимум, максимум и стандартное отклонение. Постройте таблицу зависимости разброса от √n и сформулируйте вывод. Затем оцените площадь другой фигуры, для которой известен точный ответ, чтобы проверить отсутствие систематической ошибки модели и условия попадания.