Abstract Generated abstract
This paper studies admissibility of Monte Carlo cubature procedures for square integrable functions, using variance domination as the criterion within a specified class of unbiased randomized procedures. For procedures based on determinant ratios associated with a finite orthonormal bounded system, it examines the distribution whose density is proportional to the squared determinant. The main result shows that this procedure is inadmissible when the underlying system is regular, by constructing a perturbed symmetric density that reduces variance for some functions without increasing it for others. In contrast, for a particular nonregular Haar-type system generated by dyadic partitions, the same procedure is proved admissible in the class considered, and is noted to dominate the ordinary independent sampling Monte Carlo rule.
Full Text
UDC 518.432
MATHEMATICS
S. M. ERMAKOV
ON THE ADMISSIBILITY OF PROCEDURES OF THE MONTE CARLO METHOD
(Presented by Academician Yu. V. Linnik on March 18, 1966)
Let \(\mathcal D\) be a domain of unit volume in \(k\)-dimensional Euclidean space; \(R=\mathcal D\times \mathcal D\times\cdots\times\mathcal D\)—the Cartesian product of \(\mathcal D\) with itself \(n+1\) times; \(\Xi=(x_0,\ldots,x_n)\), \(x_i\in\mathcal D\), \(i=0,\ldots,n\), and
\[ K[f]=\sum_{i=0}^{n} A_i f(x_i), \]
where \(f\) is a function from a given class \(F\) of functions defined and integrable in \(\mathcal D\), and \(A_i=A_i(\Xi)\) are determined by specifying a set \(Q\) of cubature sums \(K[f]\).
Suppose that \(\Xi\) is chosen in \(R\) at random in accordance with a distribution function \(h(\Xi)\), which, for any \(f\) from \(F\), with the given \(A_i(\Xi)\), satisfies the conditions:
A. The mean value \(E_hK[f]\) of the random variable \(K[f]\) satisfies the equality
\[ E_hK[f]=\int_{\mathcal D} f(x)\,dx. \]
B. The variance \(D_hK[f]\) of the random variable \(K[f]\) is finite.
If \(H\) is the given class of functions \(h\) satisfying conditions A and B, then \(p=(K[f],h)\) will be called a procedure of the Monte Carlo method (M.C.M.) for \(F\) in the class of procedures \(P=(Q,H)\). If \(p'=(K'[f],h')\) \((p'\in P)\) is such that \(D_{h'}K'[f]\leq D_hK[f]\) for any \(f\) from \(F\), and in \(F\) there is an \(\tilde f\) for which \(D_{h'}K'[\tilde f]<D_hK[\tilde f]\), then we shall say that \(p'\) dominates \(p\) in \(P\) for \(F\). We shall call \(p\) inadmissible in \(P\) for \(F\) if in \(P\) there exists a \(p'\) dominating \(p\) for \(F\), and admissible in the opposite case.
Clearly, the investigation of the admissibility of M.C.M. procedures and the construction of admissible M.C.M. procedures for various \(P\) and \(F\) is of considerable interest.
Let us consider a certain concrete class of M.C.M. procedures for \(f\in L_2\)-functions integrable with square in \(\mathcal D\). Define \(K[f]\) by the equality \(K[f]=\Delta(f;\Xi)/\Delta(1;\Xi)\), where \(\Delta(f;\Xi)=\det\|f(x_i),\varphi_1(x_i),\ldots,\varphi_n(x_i)\|_0^n\), and \(\varphi_0(x)\equiv 1,\varphi_1(x),\ldots,\varphi_n(x)\) is a finite sequence of orthonormal and almost everywhere bounded functions in \(\mathcal D\), and we shall assume that \(Q\) consists of the single element \(K[f]\). Define \(H\) as the set of distribution functions \(h(\Xi)\) for which conditions A and B are fulfilled and there exists a probability density function, symmetric with respect to the variables \(x_0,x_1,\ldots,x_n\). We shall call the sequence \(\{\varphi_i(x)\}_0^n\) regular in \(\mathcal D\) if \(\varphi_j(x)\) are linearly independent on any measurable set \(d\) such that \(d\subset\mathcal D\) and \(\operatorname{mes} d\ne 0\), and irregular otherwise. In \((^1)\) it was shown that the function \(W(\Xi)\), defined by the equality
\[ dW(\Xi)=\frac{1}{(n+1)!}\Delta^2(1;\Xi)\,d\Xi, \]
belongs to \(H\). Below the admissibility of \((K[f],W)\) will be investigated.
Theorem 1. If \(\{\varphi_j(x)\}_0^n\) is regular in \(\mathcal D\), then the M.C.M. procedure \((K[f],W)\) is inadmissible in \(P\) for \(L_2\).
Indeed, set
\[ d\widetilde h(\Xi)=\left(1+\beta\sum_{p<q}\psi(x_p)\psi(x_q)\right)dW(\Xi), \]
where \(p,q=0,1,\ldots,n\); \(\psi(x)\) is an almost everywhere bounded function in \(\mathfrak D\), which is orthogonal to all products \(\varphi_r(x)\varphi_s(x)\) for \(r,s=0,1,\ldots,n\), and \(\beta>0\) is a constant satisfying the condition
\(1+\beta\sum_{p<q}\psi(x_p)\psi(x_q)\geq 0\) for almost all \(\Xi\) in \(R\). Direct calculations show that condition A is satisfied for \(\widetilde h\) and
\[ D_{\widetilde h}K[f]=D_WK[f]-\beta\sum_{j=1}^n \left(\int_{\mathfrak D} f(x)\psi(x)\varphi_j(x)\,dx\right)^2, \]
which proves the theorem.
For the special case of a nonregular sequence \(\{\varphi_j(x)\}_0^n\) (a sequence of Haar functions), \((K[f],W)\) turns out to be admissible in \(P\) for \(L^2_{\mathfrak D}\). We define the functions \(\varphi_j(x)\) in \(\mathfrak D\) as follows. Partition \(\mathfrak D\) into \(2^m\) subdomains \(d(m,i_m)\), \(i_m=1,2,\ldots,2^m\), of equal measure in such a way that, as \(m\to\infty\), the diameter of \(d(m,i_m)\) tends to zero. Define the domains \(d(s,i_s)\) \((0\leq s<m,\ i_s=1,\ldots,2^s)\) by the equality
\(d(s,i_s)=d(s+1,2i_s-1)\cup d(s+1,2i_s)\), and put
\[ \chi_{i_s}^{s}(x)= \begin{cases} 2^{s/2}, & x\in d(s+1,2i_s-1),\\ -2^{s/2}, & x\in d(s+1,2i_s),\\ 0, & x\notin d(s,i_s), \end{cases} \qquad j=2^s+i_s-1, \]
\[ \varphi_0(x)\equiv 1,\qquad \varphi_j(x)=\chi_{i_s}^{s}(x)\quad (j=1,\ldots,2^m-1). \tag{1} \]
Fix some \(m_0\), and let \(n=2^{m_0}-1\).
Theorem 2. For \(\{\varphi_j(x)\}_0^n\), defined by equalities (1), the p.m.M.-C. \((K[f],W)\) is admissible in \(P\) for \(L^2_{\mathfrak D}\).
The main stages of the proof are as follows. In our case
\[ K[f]=\frac{1}{n+1}\sum_{i=0}^n f(x_i) \]
and the determinant \(\Delta(1;\Xi)\) is equal to zero if \(x_i\) and \(x_j\) for \(i\ne j\) belong to one and the same \(d(m_0,i_{m_0})\), and is constant if all \(x_i\) belong to distinct \(d(m_0,i_{m_0})\). For \(n=1\), any \(h\in H\) can be defined by the equality
\[ dh(\Xi)=\sum_{i,j=0}^{\infty} a_{i,j}\varphi_i(x_0)\varphi_j(x_1)\,d\Xi. \]
Denote
\[ \alpha_j=\int_{\mathfrak D} f(x)\varphi_j(x)\,dx \]
and express \(D_hK[f]\) through \(a_{i,j}\) and \(\alpha_j\). Taking into account that \(K[f]\) is defined only for \(\Delta(1;\Xi)\ne 0\) and condition A, we obtain
\[ D_hK[f]=D_WK[f]+\sum_{r,s=0}^{\infty}{}' b_{r,s}\alpha_r\alpha_s, \]
where the prime on the summation sign means that the terms corresponding to \(r=s\) are absent from the sum, while \(b_{r,s}\) are expressed linearly in terms of \(a_{i,j}\). Obviously, in \(L^2_{\mathfrak D}\) there will be a function \(\widetilde f\) for which \(D_hK[\widetilde f]>D_WK[\widetilde f]\), which proves the theorem for \(n=1\). The general case reduces to the case \(n=1\), if \(\widetilde f\) is sought among functions different from zero only in one of the domains \(d(m_0-1,i_{m_0-1})\). As was noted in (2), the indicated procedure dominates the “ordinary” p.m.M.-C.
\[ \left(\frac{1}{n+1}\sum_{i=0}^n f(x_i),\,l\right), \qquad \text{where } dl=d\Xi. \]
The author expresses gratitude to A. M. Kagan for valuable comments during discussion of the work.
Leningrad Shipbuilding Institute
Received
4 III 1966
CITED LITERATURE
- S. M. Ermakov, V. G. Zolotukhin, Probability Theory and Its Applications, 5, No. 4 (1960).
- I. M. Gel'fand, A. S. Frolov, N. N. Chentsov, Izv. Vyssh. Uchebn. Zaved., Ser. Mat., No. 5 (6), 32 (1958).