Variance reduction улучшает скорость 1/sqrt(N)?

Для обычных independent Monte Carlo estimators асимптотическая скорость остаётся 1/sqrt(N). Variance reduction уменьшает константу дисперсии, поэтому при том же числе samples ошибка может быть намного меньше.

Когда помогает importance sampling?

Он помогает, когда proposal density q(x) размещает samples там, где вклад f(x) максимален, а веса f(x)/q(x) не слишком сильно колеблются. Плохой proposal может наоборот увеличить variance.

Интегрирование Monte Carlo и variance reduction

Monte Carlo integration оценивает интеграл как среднее по случайным samples, поэтому типичная ошибка убывает как 1/sqrt(N). Симулятор сравнивает три unbiased estimators для одномерного интеграла: plain uniform sampling, importance sampling с q(x), похожей на экспоненциальную envelope, и stratified sampling, который принудительно покрывает подынтервалы. График convergence показывает absolute error versus N, а standard-error readouts показывают, как variance reduction меняет множитель перед той же асимптотической скоростью.

Для кого: Numerical methods, uncertainty quantification, statistics, computational physics, data science и курсы scientific computing.

Ключевые понятия

Monte Carlo integration
Variance reduction
Importance sampling
Stratified sampling
Standard error
Convergence rate

Все три estimator unbiased для этого одномерного интеграла, но их variance различается. Importance sampling помогает, когда q(x) похожа на форму integrand; stratification уменьшает случайное скучивание, заставляя samples покрывать весь interval.

Графики

Как это работает

Monte Carlo integration заменяет интеграл средним: I=∫_0^1 f(x)dx≈(1/N)Σf(U_i), где U_i равномерны. Ошибка обычного MC убывает примерно как 1/√N. Importance sampling берёт samples из density q(x) и использует веса f(x)/q(x), чтобы чаще попадать в важные области. Stratified sampling делит interval на strata и берёт samples внутри каждого, уменьшая случайные пустоты и скучивание. Оба метода обычно уменьшают variance constant, а не меняют сам асимптотический закон.

Основные формулы

Plain MC: I ≈ (1/N) Σ f(U_i), U_i ~ Uniform(0,1)

Importance: I = E_q[f(X)/q(X)], stratified: sample внутри каждого interval

Часто задаваемые вопросы

Variance reduction улучшает скорость 1/sqrt(N)?: Для обычных independent Monte Carlo estimators асимптотическая скорость остаётся 1/sqrt(N). Variance reduction уменьшает константу дисперсии, поэтому при том же числе samples ошибка может быть намного меньше.
Когда помогает importance sampling?: Он помогает, когда proposal density q(x) размещает samples там, где вклад f(x) максимален, а веса f(x)/q(x) не слишком сильно колеблются. Плохой proposal может наоборот увеличить variance.

Другие симуляторы в этой категории — или все 84.

Вся категория →

НовоеУниверситет / научные

Геометрия PCA / SVD

Ковариационный эллипс и SVD-понижение размерности: главные компоненты, explained variance и ошибка rank-1 reconstruction.

Запустить симулятор

НовоеУниверситет / научные

Оптимизаторы градиентного спуска

Сравнение SGD, momentum и Adam на 2D loss landscape: learning rate, curvature, устойчивость и траектории итераций.

Запустить симулятор

НовоеУниверситет / научные

EM-алгоритм для Gaussian mixture

Expectation-maximization для двух гауссовых компонент: responsibilities, E/M steps, likelihood и covariance ellipses.

Запустить симулятор

НовоеУниверситет / научные

Margin в support vector machine

Схема hard/soft-margin SVM: C penalty, hinge loss, support vectors, decision boundary и полосы margin.

Запустить симулятор

НовоеУниверситет / научные

Bayesian updating и conjugate priors

Beta-binomial обновление: prior/posterior curves, posterior predictive probability и credible intervals.

Запустить симулятор

НовоеУниверситет / научные

Смешивание Markov chain

Трёхсостоячная Markov chain: transition matrix, stationary distribution, total variation distance, detailed balance и spectral gap.

Запустить симулятор

Интегрирование Monte Carlo и variance reduction

Графики

Как это работает

Основные формулы

Часто задаваемые вопросы

Ещё из «Визуализация математики»

Геометрия PCA / SVD

Оптимизаторы градиентного спуска

EM-алгоритм для Gaussian mixture

Margin в support vector machine

Bayesian updating и conjugate priors

Смешивание Markov chain

Интегрирование Monte Carlo и variance reduction

Графики

Как это работает

Основные формулы

Часто задаваемые вопросы