Polynomial Model Randomizations for $Q^{(m,n)}$ Rules

The method described in this section was initially developed by Haber ([3], 1969) for interpolatory rules and generalized by Genz ([2], 1998) for fully symmetric interpolatory rules. Define

$$e_m(f,{\bf z}) = f\{{\bf z}\} - M^{(m,n)}(f, {\bf z}),$$

for a point ${\bf z}\in U_n$. If $f({\bf z}) = {\bf z}^{{\bf k}}$ and $\vert{\bf k}\vert \leq 2m+1$, then $e_m(f,{\bf z}) = 0$. The expected value for $e_m(f,{\bf z})$ is

$$I(e_m(f,{\bf z})) = I(f\{{\bf z}\}) - I(M^{(m,n)}(f,{\bf z})) = I(f) - Q^{(m,n)}(f).$$

Therefore, if $N$ random points $\{{\bf z}_i\}$ are chosen uniformly from $U_n$, then the sum

$${\bar E}_N(f) = \frac{V_n}{N} \sum\limits_{i=1}^N e_m(f,{\bf z}_i)$$

is an unbiased degree $2m+1$ stochastic error estimate rule for $Q^{(m,n)}(f)$. An unbiased error estimate for ${\hat E}_N(f)$ is provided by the Monte Carlo standard error

$$S_N(f)= \Big(\frac{1}{N(N-1)} \sum_{k=1}^N(V_ne_m(f,{\bf z}_i)-{\bar E}_N(f))^2\Big)^\frac{1}{2}.$$

This randomization method provides an error estimate, along with an error estimate for the error estimate. This type of method is more commonly used with estimates for $I(f)$ in the form

$$r_m(f,{\bf z}) = V_n(f\{{\bf z}\} - M^{(m,n)}(f, {\bf z})) + Q^{(m,n)}(f).$$

If random points $\{{\bf z}\}$ are chosen uniformly from $U_n$, then $r_m(f,{\bf z})$ is an unbiased degree $2m+1$ stochastic rule for $I(f)$. This method for randomizing a polynomial rule is a type of ``control variates'' method (see Davis and Rabinowitz [1], p. 389) for reducing variance. In many cases the sum ${\bar E}_N(f) + Q^{(m,n)}(f)$ will be a better estimate for $I(f)$ than $Q^{(m,n)}(f)$. A simple heuristic for these cases is to compare of $S_N(f)$ with ${\bar E}_N(f)$. In those cases where $S_N(f)$ is smaller than ${\bar E}_N(f)$, ${\bar E}_N(f) + Q^{(m,n)}(f)$ should be a better estimate for $I(f)$ than $Q^{(m,n)}(f)$, and then $S_N(f)$ provides an error estimate for ${\bar E}_N(f) + Q^{(m,n)}(f)$. The primary extra computational cost for ${\bar E}_N(f)$, compared to the cost of computing $Q^{(m,n)}(f)$ alone, is the extra $2^nN$ $f$ values needed for the $N$ values of $f\{{\bf z}\}$, each of which require $2^n$ $f$ values. The use of these stochastic rules for large values of $n$ (e.g. $n > 15$) might be infeasible.