Community hub
0 subscribers7 pages, 0 posts
Recent from talks
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Welcome to the community hub built to collect knowledge and have discussions related to Control variates.
Nothing was collected or created yet.
Control variates
View on Wikipediafrom Wikipedia
The control variates method is a variance reduction technique used in Monte Carlo methods. It exploits information about the errors in estimates of known quantities to reduce the error of an estimate of an unknown quantity.[1] [2][3]
Underlying principle
[edit]Let the unknown parameter of interest be , and assume we have a statistic such that the expected value of m is μ: , i.e. m is an unbiased estimator for μ. Suppose we calculate another statistic such that is a known value. Then
![{\displaystyle \mathbb {E} \left[m\right]=\mu }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a20f602ef5e52ccac3808a48f0a14c600b36fb1c)
![{\displaystyle \mathbb {E} \left[t\right]=\tau }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1903b64e792a1455fedd92d54d668fa9a23a5967)
is also an unbiased estimator for for any choice of the coefficient . The variance of the resulting estimator is
By differentiating the above expression with respect to , it can be shown that choosing the optimal coefficient
minimizes the variance of . (Note that this coefficient is the same as the coefficient obtained from a linear regression.) With this choice,
![{\displaystyle {\begin{aligned}{\textrm {Var}}\left(m^{\star }\right)&={\textrm {Var}}\left(m\right)-{\frac {\left[{\textrm {Cov}}\left(m,t\right)\right]^{2}}{{\textrm {Var}}\left(t\right)}}\\&=\left(1-\rho _{m,t}^{2}\right){\textrm {Var}}\left(m\right)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3399b00e688aae740a79cd98214602547b8f7b51)
where
is the correlation coefficient of and . The greater the value of , the greater the variance reduction achieved.
In the case that , , and/or are unknown, they can be estimated across the Monte Carlo replicates. This is equivalent to solving a certain least squares system; therefore this technique is also known as regression sampling.
When the expectation of the control variable, , is not known analytically, it is still possible to increase the precision in estimating (for a given fixed simulation budget), provided that the two conditions are met: 1) evaluating is significantly cheaper than computing ; 2) the magnitude of the correlation coefficient is close to unity. [3]
Example
[edit]We would like to estimate
using Monte Carlo integration. This integral is the expected value of , where
and U follows a uniform distribution [0, 1]. Using a sample of size n denote the points in the sample as . Then the estimate is given by
Now we introduce as a control variate with a known expected value and combine the two into a new estimate
![{\displaystyle \mathbb {E} \left[g\left(U\right)\right]=\int _{0}^{1}(1+x)\,\mathrm {d} x={\tfrac {3}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/63e77fbb5d0fec9232e81a7b53bfada99a2cee8e)
Using realizations and an estimated optimal coefficient we obtain the following results
| Estimate | Variance | |
| Classical estimate | 0.69475 | 0.01947 |
| Control variates | 0.69295 | 0.00060 |
The variance was significantly reduced after using the control variates technique. (The exact result is .)
See also
[edit] | This article needs additional citations for verification. (August 2011) |
Notes
[edit]- ^ Lemieux, C. (2017). "Control Variates". Wiley StatsRef: Statistics Reference Online. pp. 1–8. doi:10.1002/9781118445112.stat07947. ISBN 9781118445112.
- ^ Glasserman, P. (2004). Monte Carlo Methods in Financial Engineering. New York: Springer. ISBN 0-387-00451-3 (p. 185)
- ^ a b Botev, Z.; Ridder, A. (2017). "Variance Reduction". Wiley StatsRef: Statistics Reference Online. pp. 1–6. doi:10.1002/9781118445112.stat07975. hdl:1959.4/unsworks_50616. ISBN 9781118445112.
References
[edit]- Ross, Sheldon M. (2002) Simulation 3rd edition ISBN 978-0-12-598053-1
- Averill M. Law & W. David Kelton (2000), Simulation Modeling and Analysis, 3rd edition. ISBN 0-07-116537-1
- S. P. Meyn (2007) Control Techniques for Complex Networks, Cambridge University Press. ISBN 978-0-521-88441-9. Downloadable draft (Section 11.4: Control variates and shadow functions)
Control variates
View on Grokipediafrom Grokipedia
Control variates is a variance reduction technique used in Monte Carlo simulation to improve the efficiency of estimators by adjusting them with auxiliary random variables, known as control variates, whose expectations are known exactly.[1][2] This method exploits the correlation between the target variable and the control variate to reduce the overall variance of the simulation output, allowing for more accurate estimates with fewer computational resources.[3][1]
The core idea behind control variates involves rewriting the expectation of interest, , as , where is the control variate with a computable expectation , and the variance of is smaller than that of due to correlation between and .[1] In practice, the estimator is formed as , where is a coefficient chosen to minimize variance, optimally set to .[2] This optimal choice yields a reduced variance of , where is the correlation between and , potentially achieving substantial reductions if is close to 1.[3][2]
The method was first rigorously formalized in the 1980s by Lavenberg and Welch, building on earlier variance reduction ideas in Monte Carlo simulations from the 1950s.[4] Control variates are particularly effective when a simpler or "crude" version of the problem has an explicit solution, such as in financial modeling where Black-Scholes formulas serve as controls for option pricing.[2] The technique extends to multiple control variates by solving a system of linear equations for the optimal coefficients, further enhancing variance reduction.[2] It also connects to other Monte Carlo methods, including conditional Monte Carlo (where the control effectively sets ), antithetic variates, stratification, and even nonparametric maximum likelihood estimation in constrained settings.[3] Applications span numerical integration, terminating simulations, and optimization problems, with empirical examples showing variance drops of over 40% in cases like Asian option valuation.[1][3]
This table summarizes the variance reduction, highlighting how control variates concentrate the error distribution around the true value , with errors typically under 0.001 versus up to 0.01 for the crude method in repeated simulations of size 1500.
Introduction
Definition and Motivation
Monte Carlo methods provide a sampling-based approach to estimate expectations of the form , where is a random variable, by generating independent samples and averaging the function values . This crude estimator converges to the true value by the law of large numbers, but its variance, which determines the estimation error, scales as with sample size , often requiring large for precision.[5] Control variates constitute a post-processing variance reduction technique in Monte Carlo simulation, wherein the crude estimator is adjusted using an auxiliary random variable—termed the control variate—that correlates with the target quantity and possesses a known expectation. Specifically, if approximates and is the control variate with known, the adjusted estimator takes the form , where the coefficient is chosen to minimize variance while preserving unbiasedness. This method leverages the correlation to refine estimates without additional sampling overhead.[2] The primary motivation for control variates arises from the limitations of crude Monte Carlo, particularly its high variance in challenging scenarios such as rare event simulation or high-dimensional integration, where probabilities are small or dependencies amplify uncertainty, necessitating impractically large sample sizes for reliable accuracy. By exploiting negative correlation between the estimator and control variate, the technique can achieve a variance reduction factor of up to , where is the correlation coefficient, potentially decreasing the required samples by orders of magnitude when is close to 1. This efficiency gain is especially valuable in fields like finance and physics, where computational costs are high.[1][2]Historical Development
The Monte Carlo method, foundational to simulation techniques including variance reduction strategies like control variates, was introduced by Nicholas Metropolis and Stanislaw Ulam in their seminal 1949 paper, which outlined probabilistic approaches to solving complex physical problems such as neutron diffusion.[6] Control variates emerged shortly thereafter in the early 1950s as part of broader efforts to enhance computational efficiency in Monte Carlo simulations, particularly at Los Alamos National Laboratory where early nuclear physics applications demanded reduced variance in estimates.[7] Herman Kahn and A. W. Marshall played pivotal roles in pioneering control variates during this period, applying them to neutron transport simulations to minimize sample sizes while maintaining accuracy; their 1953 paper formalized key aspects of the technique, including derivations for optimal coefficients that remain influential today.[8] By the 1960s, the method gained theoretical rigor through comprehensive treatments in statistical literature, notably in John Hammersley and David Handscomb's 1964 textbook Monte Carlo Methods, which systematically described control variates alongside other variance reduction tools and emphasized their practical implementation in multidimensional integrals.[9] Control variates saw widespread adoption in the 1970s and 1980s across physics and emerging financial modeling, where simulations of stochastic processes benefited from its ease of integration with existing Monte Carlo frameworks, as highlighted in Reuven Rubinstein's 1981 book Simulation and the Monte Carlo Method.[3] In the 2000s, extensions to quasi-Monte Carlo integration revitalized the technique for high-dimensional problems, with statisticians like Christiane Lemieux contributing key advancements in combining control variates with low-discrepancy sequences to achieve superior variance reduction in computational finance and statistics.[10]Theoretical Foundations
Monte Carlo Methods Overview
Monte Carlo methods are computational algorithms that rely on repeated random sampling to obtain numerical results, particularly for approximating expectations in probability distributions. The core idea involves estimating the expected value , where is a random variable with a known distribution and is a function, by generating independent and identically distributed (i.i.d.) samples from the distribution of and computing the sample average . This estimator is unbiased, meaning , and its variance is , which decreases as the number of samples increases.[11] These methods are particularly valuable for evaluating high-dimensional integrals and performing simulations where analytical solutions are intractable, such as in particle physics for modeling neutron diffusion during the Manhattan Project or in statistical mechanics for estimating thermodynamic properties. In finance, Monte Carlo simulations are widely applied to price complex derivatives, assess risk through value-at-risk calculations, and model stochastic processes like asset price paths under the Black-Scholes framework. By leveraging random sampling, these techniques handle the "curse of dimensionality" more effectively than deterministic quadrature methods, which suffer from exponential growth in computational cost with increasing dimensions.[11] The reliability of Monte Carlo estimates stems from fundamental results in probability theory. The law of large numbers guarantees that, as , the sample average converges almost surely to the true expectation , ensuring consistency of the method. Additionally, the central limit theorem implies that, for large , the distribution of is approximately normal with mean zero and variance , enabling the construction of asymptotic confidence intervals to quantify estimation uncertainty. Despite these strengths, plain Monte Carlo integration exhibits slow convergence, with the standard error scaling as due to the inherent variance of the estimator, which can make it computationally expensive for high-precision requirements and thus motivates the development of variance reduction techniques.Control Variate Estimator
The control variate estimator is a variance reduction technique applied to the standard Monte Carlo estimator for approximating the expectation , where is a random variable whose expectation is the target quantity. Given a control variate with known expectation , the adjusted estimator takes the form where is a coefficient chosen to minimize the variance of . This construction builds on the plain Monte Carlo estimator by incorporating the control adjustment to exploit known information about .[9] The unbiasedness of the control variate estimator follows directly from the linearity of expectation. Specifically, since by assumption. Thus, the adjustment term has zero expectation, preserving the unbiasedness of the original estimator for any fixed value of . This property holds regardless of the choice of , making the method robust as a post-sampling correction in Monte Carlo simulations.[9] The effectiveness of the control variate estimator in reducing variance hinges on the existence of nonzero covariance between and , i.e., . When and are correlated, the adjustment can systematically offset errors in the Monte Carlo estimate of , leading to lower variability in compared to the unadjusted . The coefficient is selected to achieve this minimum variance reduction, with the degree of improvement scaling with the strength of the correlation.[9]Mathematical Derivation
Bias and Unbiasedness
The control variate estimator takes the form , where is the crude Monte Carlo sample mean estimating , is the sample mean of the control variate observations , is a coefficient, and is the known exact expectation of the control variate .[12] The bias of this estimator is derived as follows: Since the crude Monte Carlo estimator is unbiased () and the control variate mean is known exactly (), it follows that . This holds for any fixed coefficient , confirming that the control variate approach preserves unbiasedness under these conditions.[13][12] Unbiasedness requires the exact value of to be known in advance, often from analytical solutions or prior computations. If must be estimated, such as from an independent pilot sample, the resulting estimator remains unbiased, though variance reduction may be compromised if the pilot is small. In contrast, estimating via regression on the same primary sample introduces a small bias of order , where is the simulation size; this is generally negligible relative to the standard error for sufficiently large . Compared to crude Monte Carlo, the control variate method maintains zero bias while targeting variance reduction, and in scenarios with approximate (e.g., from refined models), any induced bias is often minimal and outweighed by efficiency gains.[14][13]Optimal Coefficient and Variance Formula
The variance of the control variate estimator , where is the original Monte Carlo estimator of interest, is the sample mean of the control variate observations with known expectation , is given by This expression follows from the bilinearity of variance and covariance under the independence of samples in Monte Carlo simulation.[15] To minimize , differentiate the variance with respect to and set the derivative to zero: yielding the optimal coefficient Substituting back into the variance formula gives the minimized variance where is the correlation coefficient between and . The term represents the fraction of the variance in explained by , so the variance reduction factor is , which can achieve up to 100% reduction (i.e., zero variance) when , indicating perfect correlation.[15] In the asymptotic regime with large sample size , the central limit theorem implies that the standardized control variate estimator converges in distribution to a normal random variable with reduced variance: where is the true parameter and is the variance of a single observation underlying . This leads to narrower confidence intervals compared to the original estimator, enhancing the precision of Monte Carlo approximations.Practical Implementation
Selecting Appropriate Control Variates
Selecting appropriate control variates is crucial for achieving effective variance reduction in Monte Carlo simulations, as the method's success hinges on the choice of the control function relative to the target quantity with unknown expectation. Ideal control variates exhibit a high absolute correlation between and , approaching 1 to maximize the reduction factor in the estimator's variance.[16][17] Additionally, the control should have low variance to avoid amplifying noise in the adjusted estimator, while remaining computationally inexpensive relative to evaluating , ensuring the overall simulation efficiency is not compromised.[16][17] Most importantly, the expectation must be exactly known, as any uncertainty here would introduce bias or require separate estimation that could offset gains.[18] Practical strategies for identifying suitable controls often involve approximating the target with simpler functions that share similar behavior but admit analytical expectations. For instance, polynomial approximations, such as those derived from Taylor series expansions of the integrand, can serve as effective controls when the full function is complex.[17] In simulation contexts, auxiliary outputs from the same random process—such as energy computations in physics-based Monte Carlo models—provide natural candidates, leveraging inherent correlations without additional sampling costs.[16] Controls drawn from known solutions to related or simplified problems further enhance applicability, prioritizing those that closely mimic the target's variability while maintaining tractable expectations.[17] For scenarios demanding greater precision, multiple control variates can be employed by extending to a vector and determining the coefficient vector through linear regression on simulation outputs, which generalizes the single-variate case to minimize multivariate variance.[18] However, this approach requires caution due to potential multicollinearity among the controls, where high inter-correlations can lead to an ill-conditioned covariance matrix, inflating estimation errors in and diminishing overall variance reduction.[19] Techniques like ridge regression may be applied to stabilize coefficient estimation in such cases by introducing regularization to the design matrix.[19] Common pitfalls in selection include relying on controls with weak correlations, where typically yields negligible variance reduction, often less than 25% improvement, making the added complexity unjustified.[17] Another frequent error is overlooking the exact knowledge of , as approximations here can bias the estimator or necessitate costly preliminary runs, eroding the method's advantages.[16] Practitioners should thus validate candidate controls empirically through pilot simulations to confirm correlation strength and computational feasibility before full deployment.[18]Parameter Estimation Techniques
In practice, the optimal control variate coefficient , given by where is the target quantity and is the control variate, must be estimated from simulation data since the true covariance and variance are unknown.[20] Sample estimates are commonly used, computing the sample covariance as and the sample variance as , where and are the sample means, is the number of simulation runs, and the denominator provides an unbiased estimate.[21] The estimated coefficient is then , which is plugged into the control variate estimator , assuming the expectation is known.[2] This approach is consistent and asymptotically efficient as , though it introduces minor estimation error for finite .[20] An equivalent method frames the estimation as a linear regression problem with an intercept, where the model is , and the ordinary least-squares slope on the original or (equivalently) demeaned data is .[20] This coincides with the sample covariance ratio, avoiding the need to estimate an intercept separately when is known.[22] This perspective extends naturally to multiple control variates, solving a system of normal equations for the coefficient vector via sample covariances.[2] The regression approach is particularly useful in software implementations, as it leverages standard statistical routines for computation.[20] When the control variate mean is unknown and must be estimated from the same simulation data as , the standard unbiased estimator simplifies to , offering no variance reduction.[20] To achieve variance reduction while maintaining unbiasedness, an independent pilot sample can be used to estimate and separately, with these fixed values then applied to a larger main sample. Alternatively, biased methods such as approximate or biased control variates can be employed, where the control mean is approximated, introducing controlled bias but potentially lower mean squared error if the approximation error is small relative to sampling variability.[23][20] For stable estimates of , especially with correlated simulation outputs, batching divides the runs into non-overlapping batches (with ), computes batch means for and , and estimates from these aggregated points, improving the reliability of the covariance calculation at the cost of a small efficiency loss factor approximately .[21] Batching, originally proposed for variance estimation in steady-state simulations, ensures the sample covariance matrix is positive definite and allows valid t-distribution confidence intervals for the output with degrees of freedom.[21] Additionally, the bootstrap can quantify uncertainty in by resampling the simulation pairs with replacement, computing over bootstrap replicates, and deriving empirical standard errors or confidence intervals, which is valuable for assessing the robustness of variance reduction in finite samples.[2] These techniques collectively enhance the practical applicability of control variates by mitigating estimation variability.[20]Examples
Basic Integral Approximation
A fundamental application of control variates arises in approximating the integral , which can be estimated using Monte Carlo simulation with uniform sampling on [0,1]. Generate independent samples for , and define the crude estimator as the sample mean , where . The variance of each is , so the variance of is approximately . To apply control variates, select , whose expectation is known analytically. The controlled estimator is , where and is chosen to minimize the variance (as detailed in the sections on the control variate estimator and optimal coefficient). The optimal coefficient is , with and , yielding . In practice, estimate from the sample covariance divided by the sample variance of . For illustration, consider samples. The crude estimator has variance approximately , corresponding to a standard error of about . Using the optimal , the variance of each controlled term is , so the variance of (adjusted for the known mean of ) is approximately , a reduction by a factor of about 32. In a typical simulation, the sample estimate of will be close to , say , yielding with a 95% confidence interval of roughly , demonstrating tighter error bounds compared to the crude interval .| Method | Variance of Estimator (n=1500) | Standard Error | Example 95% CI Width |
|---|---|---|---|
| Crude MC | ≈ 1.303 × 10^{-5} | ≈ 0.00361 | ≈ 0.0071 |
| Control Variate | ≈ 4.047 × 10^{-7} | ≈ 0.000636 | ≈ 0.0013 |