A symmetrization-desymmetrization procedure for uniformly good approximation of expectations involving arbitrary sums of generalized U-statistics

Let Phi be a symmetric function, nondecreasing on [0, infinity) and satisfy ing a Delta (2) growth condition, (X-1, Y-1), (X-2, Y-2),...,(X-n, Y-n) be independent random vectors such that (for each 1 less than or equal to i le ss than or equal to n) either Y-i = X-i or Y-i is independent of all the ot her variates, and the marginal distributions of {X-i} and {Y-j} are otherwi se arbitrary. Let {f(ij)(x, y)}(1 less than or equal toi, j less than or eq ual ton) be any array of real valued measurable functions. We present a met hod of obtaining the order of magnitude of E Phi(Sigma (1 less than or equal toi, j less than or equal ton) f(ij)(X-i, Y-j)). The proof employs a double symmetrization, introducing independent copies { (X) over tildei, (Y) over tilde (j)} of {X-i, Y-j}, and moving from summand s of the form f(ij)(X-i. Y-j) to what we call f(ij)((s))(X-i, Y-j, (X) over tilde (i), (Y) over tilde (j)). Substitution of fixed constants (x) over t ilde (i) and (y) over tilde (j) far (X) over tilde (i) and (Y) over tilde ( j) results in f(ij)((s))(X-i, Y-j, (x) over tilde (i), (y) over tilde (j)), which equals f(ij)(X-i, Y-j) adjusted by a sum of quantities of first orde r separately in X-i and Y-j. Introducing further explicit first-order adjus tments, call them g(1ij)(X-i, (x) over tilde, (y) over tilde) and g(2ij)(Y- j, (x) over tilde, (y) over tilde), it is proved that E Phi(Sigma (1 less than or equal toi, j less than or equal ton)(X-i, Y-j, (x) over tilde (i), (y) over tilde (j)) - g(1ij)(X-i, (x) over tilde, (y) o ver tilde) - g(2ij)(Y-j, (x) over tilde, (y) over tilde))) less than or equ al to (alpha) E Phi(root Sigma (1 less than or equal toi, j less than or eq ual ton) (f(ij)((s))(X-i, Y-j, (x) over tilde (i), (y) over tilde (j)))(2)) approximate to (alpha) Phi (f((s)), X, Y, (x) over tilde, (y) over tilde) where the latter is an explicitly computable quantity. For any (x) over til de (0) and (y) over tilde (0) which come within a factor of two of minimizi ng Phi (f((s)), X, Y, (x) over tilde, (y) over tilde) it is shown that E Phi(Sigma (1 less than or equal toi,j less than or equal ton) f(ij)(X-i, Y-j)) approximate to (alpha) max {Phi (f((s)), X, Y, (x) over tilde (0), (y) over tilde (0)), E Phi(Sigma (1 less than or equal toi, j less than or equal to n) (f(ij)(X-i, (y) over tilde (0)(j)) + f(ij)((x) over tilde (0)(j), Y-j) - f(ij)((x) over tilde (0)(i), (y) over tilde (0)(j)) + g(1ij)(X-i, (x) over tilde (0)(i), (y) over tilde (0)(j)) + g(2ij)(Y-j, (x) over tilde (0)(i), (y) over tilde (0)(j))))}. which is computable (approximable) in terms of the underlying random variab les. These results extend to the expectation of Phi of a sum of functions o f k-components.