Extending simulation uses of antithetic variables: partially monotone functions, random permutations, and random subsets (Q811980)

Assume that \((I_1,\dots,I_n)\) is one of equally likely \(n!\) permutations of \(1,\dots,n\) and let \(v_1<v_2<\dots<v_n\) be some fixed numbers. Consider their permutation \(V=(v_{I_1},\dots,v_{I_n})\) together with two ``antithetic permutations'': \(V_1=(v_{I_n},\dots,v_{I_1})\) and \(V_2=(v_{n+1-I_1},\dots,v_{n+1-I_n})\). It is shown that for any pair of Schur convex (or concave) functions \(f\) and \(g\) defined on permutations of \(\{v_i\}\), \(\text{Cov}(g(V),f(V_i))\leq 0\) for \(i=1,2\). This fact can be used in Monte-Carlo estimation of \(\mathbf{E}g(V)\): instead of common estimate \(\hat g=B^{-1}\sum_{k=1}^B V^{(k)}\) by i.i.d. copies \(V^{(k)}\) of \( V\) one can use \(\hat g^A=B^{-1}\sum_{k=1}^{B/2} (V^{(k)}+V^{(k)}_i)\), (\(i=1,2\)). Then \(\operatorname {Var}\widehat g\geq \operatorname {Var}\widehat g^A\). Analogous results are obtained for the use of antithetic variables for Monte-Carlo integration of partially monotone functions on \([0,1]^n\) and for expectations of functions from random sets.