Proof. The definition (3.2) yields

(4.3) \begin{align} {Var}\bigl [{U_n(f;\,{\mathcal{D}})}\bigr ]& =\sum _{\substack{1\leqslant i_1\lt \ldots \lt i_\ell \leqslant n\\i_{k+1}-i_k\leqslant d_k}} \sum _{\substack{1\leqslant j_1\lt \ldots \lt j_\ell \leqslant n\\j_{k+1}-j_k\leqslant d_k}} {Cov}\bigl ({f\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr ),f\bigl ({X_{j_1},\ldots,X_{j_\ell }}\bigr )}\bigr ) . \end{align}

Let $d_*$ be the largest finite $d_j$ in the constraint $\mathcal{D}$ , i.e.,

(4.4) \begin{align} d_*\,:\!=\,\max _j \big\{{d_j\,:\,d_j\lt \infty }\big\}. \end{align}

The constraints imply that for each block $B_q$ and all indices $k\in B_q$ , coarsely,

(4.5) \begin{align} 0\leqslant i_k-i_{\beta _q}\leqslant d_*\ell \qquad \text{and} \qquad 0\leqslant j_k-j_{\beta _q}\leqslant d_*\ell . \end{align}

It follows that if $|i_{\beta _r}-j_{\beta _s}|\gt d_*\ell +m$ for all $r,s\in [b]$ , then $|i_\alpha -j_\beta |\gt m$ for all $\alpha,\beta \in [\ell ]$ . Since $(X_i)_1^\infty$ is $m$ -dependent, this implies that the two random vectors $ ({X_{i_1},\ldots,X_{i_\ell }} )$ and $ ({X_{j_1},\ldots,X_{j_\ell }} )$ are independent, and thus the corresponding term in (4.3) vanishes.

Consequently, we only have to consider terms in the sum in (4.3) such that

(4.6) \begin{align} |i_{\beta _r}-j_{\beta _s}|\leqslant d_*\ell +m \end{align}

for some $r,s\in [b]$ . For each of the $O(1)$ choices of $r$ and $s$ , we can choose $i_{\beta _1},\ldots,i_{\beta _b}$ in at most $n^b$ ways; then $j_{\beta _s}$ in $O(1)$ ways such that (4.6) holds; then the remaining $j_{\beta _q}$ in $O\big(n^{b-1}\big)$ ways; then, finally, all remaining $i_k$ and $j_k$ in $O(1)$ ways because of (4.5). Consequently, the number of non-vanishing terms in (4.3) is $O\big(n^{2b-1}\big)$ . Moreover, each term is $O(1)$ by (3.6) and the Cauchy–Schwarz inequality, and thus (4.1) follows.

For (4.2), we note that $U_n(f;\,{\mathcal{D}})-U_{n-1}(f;\,{\mathcal{D}})$ is the sum in (3.2) with the extra restriction $i_\ell =n$ . Hence, its variance can be expanded as in (4.3), with the extra restrictions $i_\ell =j_\ell =n$ . We then argue as above, but note that (4.5) and $i_\ell =n$ imply that there are only $O(1)$ choices of $i_b$ , and hence $O\big(n^{b-1}\big)$ choices of $i_1,\ldots,i_b$ . We thus obtain $O \big({n^{2b-2}} \big)$ non-vanishing terms in the sum, and (4.2) follows.

The argument for the exactly constrained $U_n(f;\,{{\mathcal{D}}{=}})$ is the same (and slightly simpler). (Alternatively, we could do this case first, and then use (3.4) to obtain the results for $U_n(f;\,{\mathcal{D}})$ .)

Proof. For each block $B_q=\{{\beta _q,\ldots,\beta _{q+1}-1}\}$ defined by $\mathcal{D}$ , let

(4.11) \begin{align} \ell _q&\,:\!=\,|B_q|=\beta _{q+1}-\beta _q, \end{align}

(4.12) \begin{align} t_{qr}&\,:\!=\,\sum _{j=1}^{r-1}d_{\beta _q+j-1}, \qquad r=1,\ldots,\ell _q, \end{align}

(4.13) \begin{align} u_q&\,:\!=\,t_{q,\ell _q}=\sum _{j=1}^{\beta _{q+1}-\beta _q-1}d_{\beta _q+j-1}, \end{align}

(4.14) \begin{align} v_q&\,:\!=\,\sum _{k\lt q}u_k . \end{align}

Note that $t_{q1}=0$ for every $q$ and that $t_{qr},u_q\lt \infty$ . (We stop the summation in (4.13) just before the next infinite $d_j$ , which occurs for $j=\beta _{q+1}-1$ provided $q\lt b$ .) Note also that

(4.15) \begin{align} u_b+v_b=\sum _{k\leqslant b} u_k=D. \end{align}

We then rewrite (3.3) as follows, letting $k_q\,:\!=\,i_{\beta _q}$ and grouping the arguments of $f$ according to the blocks of $\mathcal{D}$ (using an obvious notation for this):

(4.16) \begin{align} U_n(f;\,{{\mathcal{D}}{=}}) &= \sum _{\substack{1\leqslant k_1\lt k_2\lt \ldots \lt k_b\leqslant n-u_{b},\\ k_{q+1}\gt k_q+u_q}} f\Bigl ({\big(X_{k_1+t_{1r}}\big)_{r=1}^{\ell _1},\ldots,\big(X_{k_b+t_{br}}\big)_{r=1}^{\ell _b} }\Bigr ) . \end{align}

Change summation variables by $k_q=j_q+v_q$ . Then, recalling (4.14)–(4.15), (4.16) yields

(4.17) \begin{align} U_n(f;\,{{\mathcal{D}}{=}}) = \sum _{1\leqslant j_1\lt j_2\lt j_b\leqslant n-D} f\Bigl ({\big(X_{j_1+v_1+t_{1r}}\big)_{r=1}^{\ell _1},\ldots,\big(X_{j_b+v_b+t_{br}}\big)_{r=1}^{\ell _b} }\Bigr ) . \end{align}

Define, for $y_i=(y_{ik})_{k=1}^M\in{\mathcal{S}}^M$ ,

(4.18) \begin{align} g(y_1,\ldots,y_b) =f\Bigl ({\big(y_{1,v_1+t_{1r}+1}\big)_{r=1}^{\ell _1},\ldots,\big(y_{b,v_b+t_{br}+1}\big)_{r=1}^{\ell _b} }\Bigr ). \end{align}

(Note that $v_j+t_{jr}+1\leqslant v_j + u_j +1 \leqslant D+1\leqslant M$ .) We have $Y_j=(X_{j+k-1})_{k=1}^M$ , and thus (4.18) yields

(4.19) \begin{align} g\big(Y_{j_1},\ldots,Y_{j_b}\big) =f\Bigl ({\big(X_{j_1+v_1+t_{1r}}\big)_{r=1}^{\ell _1},\ldots,\big(X_{j_b+v_b+t_{br}}\big)_{r=1}^{\ell _b}}\Bigr ) . \end{align}

Consequently, (4.9) follows from (4.17) and (4.19).

Furthermore, (4.10) follows from (4.19) and ( ${A}_2$ ).

Proof. First, letting $g_{{{\mathcal{D}}{=}}}$ be as in Lemma 4.2, we have by (4.9)

(4.22) \begin{align} U_n(f;\,{{\mathcal{D}}{=}} ;\,(X_i) )-U_{n}\bigl ({g_{{{\mathcal{D}}{=}}};\,(Y_i) }\bigr ) &= U_{n-D}\bigl ({g_{{{\mathcal{D}}{=}}}}\bigr )-U_{n}\bigl ({g_{{{\mathcal{D}}{=}}}}\bigr ) \notag \\& =-\sum _{k=1}^q\Bigl ({ U_{n-k+1}\bigl ({g_{{{\mathcal{D}}{=}}}}\bigr )-U_{n-k}\bigl ({g_{{{\mathcal{D}}{=}}}}\bigr )}\Bigr ) . \end{align}

Thus (4.21) follows by (4.2) in Lemma 4.1 applied to $g_{{{\mathcal{D}}{=}}}$ , the trivial constraint ${\mathcal{D}}_\infty$ (i.e., no constraint), and $(Y_i)_1^\infty$ .

Next, we recall (3.4) and define

(4.23) \begin{align} g_{{\mathcal{D}}}= \sum _{{\mathcal{D}}^{\prime}} g_{{{\mathcal{D}}^{\prime}{=}}}, \end{align}

again summing over all constraints ${\mathcal{D}}^{\prime}$ satisfying (3.5). This is a finite sum, and by (3.4) and (4.23),

(4.24) \begin{align} U_n(f;\,{\mathcal{D}} ;\,(X_i) )-U_{n}\bigl ({g_{{\mathcal{D}}};\,(Y_i) }\bigr ) = \sum _{{\mathcal{D}}^{\prime}} \bigl ({U_n(f;\,{{\mathcal{D}}^{\prime}{=}} ;\,(X_i) )-U_{n}\bigl ({g_{{{\mathcal{D}}^{\prime}{=}}};\,(Y_i) }\bigr )}\bigr );\, \end{align}

thus (4.20) follows from (4.21).

Proof. We can express the type of constrained $U$ -statistic in (4.25) as a combination of constrained $U$ -statistics of the previous type by the following inclusion–exclusion argument:

(4.27) \begin{align} U_n(f;\,\gt m) &=\sum _{1\leqslant i_1\lt \ldots \lt i_\ell \leqslant n} f\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr ) \prod _{j=1}^{\ell -1}\boldsymbol{1}\{{i_{j+1}-i_j\gt m}\} \notag \\ &=\sum _{1\leqslant i_1\lt \ldots \lt i_\ell \leqslant n} f\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr ) \prod _{j=1}^{\ell -1}\Bigl ({1-\boldsymbol{1}\{{i_{j+1}-i_j\leqslant m}\}}\Bigr ) \notag \\ &=\sum _{J\subseteq [\ell -1]}({-}1)^{|J|}\sum _{1\leqslant i_1\lt \ldots \lt i_\ell \leqslant n} f\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr ) \prod _{j\in J}\boldsymbol{1}\{{i_{j+1}-i_j\leqslant m}\} \notag \\ &=\sum _{J\subseteq [\ell -1]}({-}1)^{|J|}U_n(f;\,{\mathcal{D}}_J), \end{align}

where we sum over the $2^{\ell -1}$ subsets $J$ of $[{\ell -1}]$ , and use the constraints

(4.28) \begin{align} {\mathcal{D}}_J\,:\!=\,(d_{Jj})_{j=1}^{\ell -1} \qquad \text{with} \qquad d_{Jj}= \begin{cases} m,&j\in J,\\ \infty,& j\notin J. \end{cases} \end{align}

We have $b({\mathcal{D}}_{J})=\ell -|J|$ , and thus $b({\mathcal{D}}_J)\lt \ell$ unless $J=\emptyset$ . Moreover, ${\mathcal{D}}_\emptyset =(\infty,\ldots,\infty )={\mathcal{D}}_\infty$ , and this means no constraint, so $U_n(f;\,{\mathcal{D}}_\emptyset )=U_n(f)$ , the unconstrained $U$ -statistic. Consequently, by (4.27) and Lemma 4.1,

(4.29) \begin{align} {Var}\bigl ({U_n(f)-U_n(f;\,\gt m)}\bigr ) ={Var}\Bigl ({\sum _{J\neq \emptyset }({-}1)^{|J|-1}U_n(f;\,{\mathcal{D}}_J)}\Bigr ) =O\bigl ({n^{2\ell -3}}\bigr ), \end{align}

which proves the estimate (4.26).

Proof of Theorem 3.1. Consider first the unconstrained case. We take expectations in (3.1). The sum in (3.1) has $\binom{n}{\ell }$ terms. We consider first the terms that satisfy the restriction $i_{j+1}\gt i_j+m$ for every $j\in [{\ell -1}]$ (i.e., the terms in (4.25)). As noted above, in each such term, the variables $X_{j_1},\ldots,X_{j_\ell }$ are independent. Hence, let $(\widehat{X}_i)_1^\ell$ be an independent sequence of random variables in $\mathcal{S}$ , each with the same distribution as $X_1$ (and thus as each $X_j$ ), and define

(5.1) \begin{equation} \mu \,:\!=\,{\mathbb{E}} f(\widehat{X}_1,\ldots,\widehat{X}_\ell ). \end{equation}

Then

(5.2) \begin{align} \mu ={\mathbb{E}} f\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr ) \end{align}

for every sequence of indices $i_1,\ldots,i_\ell$ with $i_{j+1}\gt i_j+m$ for all $j\in [{\ell -1}]$ . Moreover, the number of terms in (3.1) that do not satisfy these constraints is $O ({n^{{\ell -1}}} )$ , and their expectations are uniformly $O(1)$ as a consequence of (3.6). Thus, (3.7) follows from (3.1).

Next, consider the exactly constrained case. We use Lemma 4.2 and then apply the unconstrained case just treated to $g$ and $(Y_i)$ ; this yields

(5.3) \begin{align} {\mathbb{E}} U_n\bigl ({f;\,{{\mathcal{D}}{=}}}\bigr ) ={\mathbb{E}} U_{n-D}\bigl ({g;\,(Y_i) }\bigr ) =\binom{n-D}{b}{\mathbb{E}} g(\widehat{Y}_1,\ldots,\widehat{Y}_b)+ O\bigl ({n^{b-1}}\bigr ) \end{align}

with $\widehat{Y}_1,\ldots,\widehat{Y}_b\overset{d}{=} Y_1$ independent. Using (4.19), and the notation there, this yields (3.9) with

(5.4) \begin{align} \mu _{{{\mathcal{D}}{=}}}\,:\!=\,{\mathbb{E}} g\big(Y_{j_1},\ldots,Y_{j_b}\big) ={\mathbb{E}} f\bigl ({\big(X_{j_1+v_1+t_{1r}}\big)_{r=1}^{\ell _1},\ldots,\big(X_{j_b+v_b+t_{br}}\big)_{r=1}^{\ell _b}}\bigr ), \end{align}

for any sequence $j_1,\ldots,j_b$ with $j_{k+1}-j_k\geqslant m+M$ for all $k\in [b-1]$ . (Note that $(Y_i)_1^\infty$ is $(m+M-1)$ -dependent.)

Finally, the constrained case (3.8) follows by (3.9) and the decomposition (3.4), with

(5.5) \begin{align} \mu _{{\mathcal{D}}}\,:\!=\,\sum _{{\mathcal{D}}^{\prime}}\mu _{{{\mathcal{D}}^{\prime}{=}}}, \end{align}

summing over all ${\mathcal{D}}^{\prime}$ satisfying (3.5).

In the independent case $m=0$ , the results above simplify. First, for the unconstrained case, the formula for $\mu$ in (3.10) is a special case of (5.2). Similarly, in the exactly unconstrained case, (5.4) yields the formula for $\mu _{{\mathcal{D}}{=}}$ in (3.10). Finally, (3.10) shows that $\mu _{{\mathcal{D}}{=}}$ does not depend on $\mathcal{D}$ , and thus all terms in the sum in (5.5) are equal to $\mu$ . Furthermore, it follows from (3.5) that the number of terms in the sum is $\prod _{d_j\lt \infty }d_j$ , and (3.11) follows.

Alternatively, in the independent case, all terms in the sums in (3.1), (3.2), and (3.3) have the same expectation $\mu$ given by (3.10), and the result follows by counting the number of terms. In particular, exactly,

(5.6) \begin{align}{\mathbb{E}} U_n(f)=\binom n\ell \mu \end{align}

and, with $D$ given by (4.7),

(5.7) \begin{align}{\mathbb{E}} U_n(f;\,{{\mathcal{D}}{=}})=\binom{n-D}{b} \mu . \end{align}

Proof of Theorem 3.3. We first note that by Lemma 4.4, it suffices to prove (3.18)–(3.19) for $U_n(f;\,\gt m)$ . (This uses standard arguments with Minkowski’s inequality and the Cramér–Slutsky theorem [Reference Gut25, Theorem 5.11.4], respectively; we omit the details. The same arguments are used several times below without comment.)

As remarked above, the variables inside each term in the sum in (4.25) are independent; this enables us to use Hoeffding’s decomposition for the independent case, which (in the present, asymmetric case) we define as follows.

As in Section 5, let $(\widehat{X}_i)_1^\ell$ be an independent sequence of random variables in $\mathcal{S}$ , each with the same distribution as $X_1$ . Recall $\mu$ defined in (5.1), and, for $i=1,\ldots,\ell$ , define the function $f_i$ as the one-variable projection

(6.1) \begin{align} f_i(x)\,:\!=\, &{\mathbb{E}} f\bigl ({\widehat{X}_1,\ldots,\widehat{X}_{i-1},x,\widehat{X}_{i+1},\ldots,\widehat{X}_\ell }\bigr )-\mu . \end{align}

Equivalently,

(6.2) \begin{align} f_i(\widehat{X}_i) =&{\mathbb{E}} \bigl ({f(\widehat{X}_1,\ldots,\widehat{X}_\ell )\mid \widehat{X}_i}\bigr )-\mu . \end{align}

(In general, $f_i$ is defined only ${\mathcal{L}}(\widehat{X}_i)$ -almost everywhere (a.e.), but it does not matter which version we choose.) Define also the residual function

(6.3) \begin{align} f_*(x_1,\ldots,x_d) &\,:\!=\, f(x_1,\ldots,x_d) - \mu - \sum _{j=1}^\ell f_j(x_j). \end{align}

Note that the variables $f_i(X_j)$ are centered by (5.1) and (6.2):

(6.4) \begin{align} {\mathbb{E}} f_i(X_j)={\mathbb{E}} f_i(\widehat{X}_i)=0. \end{align}

Furthermore, ( ${A}_2$ ) implies that $f_i(\widehat{X}_i)$ , and thus each $f_i(X_j)$ , is square integrable.

The essential property of $f_*$ is that, as an immediate consequence of the definitions and (6.4), its one-variable projections vanish:

(6.5) \begin{align}{\mathbb{E}} \bigl ({f_*(\widehat{X}_1,\ldots,\widehat{X}_\ell )\mid \widehat{X}_i=x}\bigr ) ={\mathbb{E}} f_*\bigl ({\widehat{X}_1,\ldots,\widehat{X}_{i-1},x,\widehat{X}_{i+1},\ldots,\widehat{X}_\ell }\bigr ) =0 . \end{align}

We assume from now on for simplicity that $\mu =0$ ; the general case follows by replacing $f$ by $f-\mu$ . Then (4.25) and (6.3) yield, by counting the terms where $i_j=k$ for given $j$ and $k$ ,

(6.6) \begin{align} U_n(f;\,\gt m) &= \sum _{\substack{1\leqslant i_1\lt \ldots \lt i_\ell \leqslant n\\i_{j+1}-i_j\gt m}} \Bigl ({\sum _{j=1}^\ell f_j(X_{i_j})+ f_*\bigl ({X_{i_1},\ldots,X_{i_\ell }}\bigr )}\Bigr ) \notag \\& =\sum _{j=1}^\ell \sum _{k=1}^n \binom{k-1-(j-1)m}{j-1}\binom{n-k-(\ell -j)m}{\ell -j} f_j(X_k) +U_n(f_*;\,\gt m) . \end{align}

Let us first dispose of the last term in (6.6). Let $i_1\lt \ldots \lt i_\ell$ and $j_1\lt \ldots \lt j_\ell$ be two sets of indices such that the constraints $i_{k+1}-i_k\gt m$ and $j_{k+1}-j_k\gt m$ in (4.25) hold. First, as in the proof of Lemma 4.1, if also $|i_\alpha -j_\beta |\gt m$ for all $\alpha,\beta \in [\ell ]$ , then all $X_{i_\alpha }$ and $X_{j_\beta }$ are independent; thus $f_*(X_{i_1},\ldots,X_{i_\ell })$ and $f_*(X_{j_1},\ldots,X_{j_\ell })$ are independent, and

(6.7) \begin{align} {\mathbb{E}}\bigl [{f_*(X_{i_1},\ldots,X_{i_\ell })f_*(X_{j_1},\ldots,X_{j_\ell })}\bigr ] ={\mathbb{E}} f_*(X_{i_1},\ldots,X_{i_\ell }){\mathbb{E}} f_*(X_{j_1},\ldots,X_{j_\ell }) =0. \end{align}

Moreover, suppose that $|i_\alpha -j_\beta |\gt m$ for all but one pair $(\alpha,\beta )\in [\ell ]^2$ , say for $(\alpha,\beta )\neq (\alpha _0,\beta _0)$ . Then the pair $(X_{i_{\alpha _0}},X_{j_{\beta _0}})$ is independent of all the variables $\{{X_{i_\alpha }\,:\,\alpha \neq \alpha _0}\}$ and $\{{X_{j_\beta }\,:\,\beta \neq \beta _0}\}$ , and all these are mutually independent. Hence, recalling (6.5), a.s.

(6.8) \begin{align} &{\mathbb{E}}\bigl [{f_*(X_{i_1},\ldots,X_{i_\ell })f_*(X_{j_1},\ldots,X_{j_\ell }) \mid X_{i_{\alpha _0}},X_{j_{\beta _0}}}\bigr ] \\\notag & \qquad ={\mathbb{E}}\bigl [{ f_*({X_{i_1},\ldots,X_{i_\ell }})\mid X_{i_{\alpha _0}}}\bigr ]{\mathbb{E}} \bigl [{f_*(X_{j_1},\ldots,X_{j_\ell })\mid X_{j_{\beta _0}}}\bigr ] =0. \end{align}

Thus, taking the expectation, we find that unconditionally

(6.9) \begin{align} {\mathbb{E}}\bigl [{f_*(X_{i_1},\ldots,X_{i_\ell })f_*(X_{j_1},\ldots,X_{j_\ell })}\bigr ] =0. \end{align}

Consequently, if we expand ${Var} [{U_n(f_*;\,\gt m)} ]$ in analogy with (4.3), then all terms where $|i_\alpha -j_\beta |\leqslant m$ for at most one pair $(\alpha,\beta )$ will vanish. The number of remaining terms, i.e., those with at least two such pairs $(\alpha,\beta )$ , is $O(n^{2\ell -2})$ , and each term is $O(1)$ , by ( ${A}_2$ ) and the Cauchy–Schwarz inequality. Consequently,

(6.10) \begin{align} {Var}\bigl [{U_n(f_*;\,\gt m)}\bigr ] =O\bigl ({n^{2\ell -2}}\bigr ). \end{align}

Hence, we may ignore the final term $U_n(f_*;\,\gt m)$ in (6.6).

We turn to the main terms in (6.6), i.e., the double sum; we denote it by $\widehat{U}_n$ and write it as

(6.11) \begin{align} \widehat{U}_n=\sum _{j=1}^\ell \sum _{k=1}^n a_{j,k,n}f_j(X_k), \end{align}

where we thus define

(6.12) \begin{align} a_{j,k,n}&\,:\!=\, \binom{k-1-(j-1)m}{j-1}\binom{n-k-(\ell -j)m}{\ell -j} \notag \\&\phantom \,:\!=\,\frac{1}{(j-1)!\,(\ell -j)!} k^{j-1}(n-k)^{\ell -j} + O(n^{\ell -2}), \end{align}

where the $O$ is uniform over all $k\leqslant n$ and $j\leqslant \ell$ . For $j=1,\ldots,\ell$ , define the polynomial functions

(6.13) \begin{align} \psi _j(x)\,:\!=\,\frac{1}{(j-1)!\,(\ell -j)!} x^{j-1}(1-x)^{\ell -j}, \qquad x\in \mathbb{R}. \end{align}

Then (6.12) yields, again uniformly for all $k\leqslant n$ and $j\leqslant \ell$ ,

(6.14) \begin{align} a_{j,k,n}=n^{\ell -1}\psi _j(k/n)+O\bigl ({n^{\ell -2}}\bigr ) . \end{align}

The expansion (6.11) yields

(6.15) \begin{align} {Var}\ \widehat{U}_n = \sum _{i=1}^\ell \sum _{j=1}^\ell \sum _{k=1}^n \sum _{q=1}^na_{i,k,n}a_{j,q,n}{Cov}\bigl [{f_i(X_k),f_j(X_q)}\bigr ], \end{align}

where all terms with $|k-q|\gt m$ vanish because the sequence $(X_i)$ is $m$ -dependent. Hence, with $r_-\,:\!=\,\max \{{-r,0}\}$ and $r_+\,:\!=\,\max \{{r,0}\}$ ,

(6.16) \begin{align} {Var}\ \widehat{U}_n = \sum _{i=1}^\ell \sum _{j=1}^\ell \sum _{r=-m}^m \sum _{k=1+r_-}^{n-r_+}a_{i,k,n}a_{j,k+r,n}{Cov}\bigl [{f_i(X_k),f_j(X_{k+r})}\bigr ] . \end{align}

The covariance in (6.16) is independent of $k$ ; we thus define, for any $k\gt r_-$ ,

(6.17) \begin{align} \gamma _{i,j,r}\,:\!=\,{Cov}\bigl [{f_i(X_k),f_j(X_{k+r})}\bigr ] \end{align}

and obtain

(6.18) \begin{align} {Var}\ \widehat{U}_n = \sum _{i=1}^\ell \sum _{j=1}^\ell \sum _{r=-m}^m\gamma _{i,j,r} \sum _{k=1+r_-}^{n-r_+}a_{i,k,n}a_{j,k+r,n}. \end{align}

Furthermore, by (6.14),

(6.19) \begin{align} n^{2-2\ell } \sum _{k=1+r_-}^{n-r_+}a_{i,k,n}a_{j,k+r,n} &= \sum _{k=1+r_-}^{n-r_+} \bigl ({\psi _i(k/n)+O\big(n^{-1}\big)}\bigr )\bigl ({\psi _j(k/n)+O\big(n^{-1}\big)}\bigr ) \notag \\& = \sum _{k=1+r_-}^{n-r_+} \bigl ({\psi _i(k/n)\psi _j(k/n)+O\big(n^{-1}\big)}\bigr ) \notag \\& = \sum _{k=1}^{n} \psi _i(k/n)\psi _j(k/n)+O(1) \notag \\& = \int _0^n \psi _i(x/n)\psi _j(x/n)\,{d} x+O(1) \notag \\& = n\int _0^1 \psi _i(t)\psi _j(t)\,{d} t+O(1) . \end{align}

Consequently, (6.18) yields

(6.20) \begin{align} n^{1-2\ell } {Var}\ \widehat{U}_n = \sum _{i=1}^\ell \sum _{j=1}^\ell \sum _{r=-m}^m\gamma _{i,j,r} \int _0^1\psi _i(t)\psi _j(t)\,{d} t +O\bigl ({n^{-1}}\bigr ). \end{align}

Since (4.26), (6.6), and (6.10) yield

(6.21) \begin{align} {Var}\bigl [{ U_n(f)-\widehat{U}_n}\bigr ] = O\bigl ({n^{2\ell -2}}\bigr ), \end{align}

the result (3.18) follows from (6.20), with

(6.22) \begin{align} \sigma ^2 = \sum _{i=1}^\ell \sum _{j=1}^\ell \sum _{r=-m}^m\gamma _{i,j,r} \int _0^1\psi _i(t)\psi _j(t)\,{d} t . \end{align}

Next, we use (6.11) and write

(6.23) \begin{align} n^{\frac 12-\ell } \widehat{U}_n =\sum _{k=1}^n Z_{kn}, \end{align}

with

(6.24) \begin{align} Z_{kn}\,:\!=\,\sum _{j=1}^\ell n^{\frac 12-\ell }a_{j,k.n}f_j(X_k) . \end{align}

Since $Z_{kn}$ is a function of $X_k$ , it is evident that $(Z_{kn})$ is an $m$ -dependent triangular array with centered variables. Furthermore, ${\mathbb{E}} Z_{kn}=0$ as a consequence of (6.4).

We apply Theorem 4.1 to $(Z_{kn})$ , so $\widehat{S}_n=n^{\frac 12-\ell }\widehat{U}_n$ by (6.23), and verify first its conditions. The condition (4.30) holds by (6.20) and (6.22). Write $Z_{kn}=\sum _{j=1}^\ell Z_{jkn}$ with

(6.25) \begin{align} Z_{jkn}\,:\!=\, n^{\frac 12-\ell }a_{j,k.n}f_j(X_k). \end{align}

Since (6.12) yields $|a_{j,k,n}|\leqslant n^{\ell -1}$ , we have, for $\varepsilon \geqslant 0$ ,

(6.26) \begin{align} {\mathbb{E}}\bigl [{Z_{jkn}^2\boldsymbol{1}\{{|Z_{jkn}|\gt \varepsilon }\}}\bigr ] \leqslant n^{-1}{\mathbb{E}} \bigl [{|f_j(X_k)|^2 \boldsymbol{1}\{{\lvert{f_j(X_k)}\rvert \gt \varepsilon n^{1/2}}\}}\bigr ]. \end{align}

The distribution of $f_j(X_k)$ does not depend on $k$ , and thus the Lindeberg condition (4.31) for each triangular array $(Z_{jkn})_{k,n}$ follows from (6.26). The Lindeberg condition (4.31) for $(Z_{nk})_{k,n}$ then follows easily. Finally, taking $\varepsilon =0$ in (6.26) yields ${\mathbb{E}} Z_{jkn}^2\leqslant Cn^{-1}$ , and thus ${\mathbb{E}} Z_{kn}^2\leqslant Cn^{-1}$ , which shows (4.32).

We have shown that Theorem 4.1 applies, and thus, recalling (6.23) and (6.4),

(6.27) \begin{align} n^{\frac 12-\ell } \bigl ({ \widehat{U}_n-{\mathbb{E}} \widehat{U}_n}\bigr ) = n^{\frac 12-\ell } \widehat{U}_n =\sum _{k=1}^n Z_{kn} \overset{d}{\longrightarrow } \textsf{N}\big(0,\sigma ^2\big). \end{align}

The result (3.19) now follows from (6.27) and (6.21).

Proof of Theorem 3.4. Lemma 4.3 implies that it suffices to consider $U_n ({g;\,(Y_i) } )$ instead of $U_n(f;\,{\mathcal{D}})$ or $U_n(f;\,{{\mathcal{D}}{=}})$ . Note that the definition (4.8) implies that $(Y_i)_1^\infty$ is a stationary $m^{\prime}$ -dependent sequence, with $m^{\prime}\,:\!=\,m+M-1$ . Hence, the result follows from Theorem 3.3 applied to $g$ and $(Y_i)_1^\infty$ .

Proof of Theorem 3.2. Note first that if $R_n$ is any sequence of random variables such that

(7.1) \begin{align} {\mathbb{E}} R_n^2=O\bigl ({n^{-2}}\bigr ), \end{align}

then Markov’s inequality and the Borel–Cantelli lemma show that $R_n\overset{a.s.}{\longrightarrow }0$ .

We begin with the unconstrained case, ${\mathcal{D}}={\mathcal{D}}_\infty =(\infty,\ldots,\infty )$ . We may assume, as in the proof of Theorem 3.3, that $\mu =0$ . Then (6.21) holds, and thus by the argument just given, and recalling that ${\mathbb{E}} \widehat{U}_n=0$ by (6.11) and (6.4),

(7.2) \begin{align} n^{-\ell } \bigl [{U_n(f)-{\mathbb{E}} U_n(f) - \widehat{U}_n}\bigr ]\overset{a.s.}{\longrightarrow } 0. \end{align}

Hence, to prove (3.15), it suffices to prove $n^{-\ell }\widehat{U}_n\overset{a.s.}{\longrightarrow }0$ .

For simplicity, we fix $j\in [\ell ]$ and define, with $f_j$ as above given by (6.1),

(7.3) \begin{align} S_{jn} =S_{jn}(f) \,:\!=\,S_n(f_j) \,:\!=\,\sum _{k=1}^n f_j(X_k) \end{align}

and, using partial summation,

(7.4) \begin{align} \widehat{U}_{jn}\,:\!=\,\sum _{k=1}^n a_{j,k,n}f_j(X_k) =\sum _{k=1}^{n-1}(a_{j,k,n}-a_{j,k+1,n})S_{jk} + a_{j,n,n}S_{jn}. \end{align}

The sequence $(f_j(X_k))_k$ is $m$ -dependent, stationary, and with ${\mathbb{E}} |f_j(X_k)|\lt \infty$ . As is well known, the strong law of large numbers holds for stationary $m$ -dependent sequences with finite means. (This follows by considering the subsequences $(X_{(m+1)n+q})_{n\geqslant 0}$ , which for each fixed $q\in [m+1]$ is an i.i.d. sequence.) Thus, by (7.3) and (6.4),

(7.5) \begin{align} S_{jn}/n\overset{a.s.}{\longrightarrow }{\mathbb{E}} f_j(X_k)=0. \end{align}

In other words, a.s. $S_{jn}=o(n)$ , and thus also

(7.6) \begin{align} \max _{1\leqslant k\leqslant n}|S_{jk}| =o(n)\qquad \text{a.s.} \end{align}

Moreover, (6.12) implies $a_{j,k,n}-a_{j,k+1,n}=O(n^{\ell -2})$ . Hence, (7.4) yields

(7.7) \begin{align} n^{-\ell } \widehat{U}_{jn} =\sum _{k=1}^{n-1} O\big(n^{-2}\big)\cdot S_{jk} + O\big(n^{-1}\big) \cdot S_{jn}, \end{align}

and thus, using (7.6),

(7.8) \begin{align} \bigl \lvert{n^{-\ell } \widehat{U}_{jn}}\bigr \rvert \leqslant C n^{-1} \max _{k\leqslant n}| S_{jk}| =o(1)\qquad \text{a.s.} \end{align}

Consequently,

(7.9) \begin{align} n^{-\ell }\widehat{U}_n = \sum _{j=1}^\ell n^{-\ell }\widehat{U}_{jn }\overset{a.s.}{\longrightarrow } 0, \end{align}

which together with (7.2) yields the desired result (3.15).

Next, for an exact constraint ${\mathcal{D}}{=}$ , we use Lemma 4.2. Then (4.9) together with the result just shown applied to $g$ and $(Y_i)$ yields

(7.10) \begin{align} n^{-b}\big [{U_n(f;\,{{\mathcal{D}}{=}})}-{\mathbb{E}}{U_n(f;\,{{\mathcal{D}}{=}})}\big ] = n^{-b}\big [{U_{n-D}(g)}-{\mathbb{E}}{U_{n-D}(g)}\big ] \overset{a.s.}{\longrightarrow }0. \end{align}

This proves (3.17), and (3.16) follows by (3.4).

Finally, using Theorem 3.1, (3.12)–(3.14) are equivalent to (3.15)–(3.17).

Proof. Since $A$ is positive definite, there exists an orthonormal basis $(v_k)_1^\ell$ in $\mathbb{R}^\ell$ consisting of eigenvectors of $A$ , in other words satisfying $Av_k=\lambda _kv_k$ ; furthermore, the eigenvalues $\lambda _k\gt 0$ . Write $v_k=(v_{ki})_{i=1}^\ell$ . We then have

(8.10) \begin{align} a_{ij}=\sum _{k=1}^\ell \lambda _k v_{ki}v_{kj}. \end{align}

Thus

(8.11) \begin{align} \sum _{i,j=1}^\ell a_{ij}b_{ij} =\sum _{k=1}^\ell \lambda _k \sum _{i,j=1}^\ell b_{ij}v_{ki}v_{kj} =\sum _{k=1}^\ell \lambda _k \langle{v_k,Bv_k}\rangle . \end{align}

Since $B$ is positive semidefinite, all terms in the last sum are $\geqslant 0$ , so the sum is 0 if and only if every term is, and thus

(8.12) \begin{align} \sum _{i,j=1}^\ell a_{ij}b_{ij}=0 \iff \langle{v_k,Bv_k}\rangle =0 \quad \forall k\in [\ell ]. \end{align}

By the Cauchy–Schwarz inequality for the semidefinite bilinear form $\langle{v,Bw}\rangle$ (or, alternatively, by using $\langle{v_k\pm v_n,B(v_k\pm v_n)}\rangle \geqslant 0$ ), it follows that this condition implies $\langle{v_k,Bv_n}\rangle =0$ for any $k,n\in [\ell ]$ , and thus

(8.13) \begin{align} \sum _{i,j=1}^\ell a_{ij}b_{ij}=0 \iff \langle{v_k,Bv_n}\rangle =0 \quad \forall k,n\in [\ell ]. \end{align}

Since $(v_k)_1^\ell$ is a basis, this is further equivalent to $\langle{v,Bw}\rangle =0$ for any $v,W\in \mathbb{R}^\ell$ , and thus to $B=0$ . This yields (8.9).

Proof of Theorem 8.1. The $\ell$ polynomials $\psi _j$ , $j=1,\ldots,\ell$ , of degree $\ell -1$ defined by (6.13) are linearly independent (e.g., since the matrix of their coefficients in the standard basis $\{{1,x,\ldots,x^{\ell -1}}\}$ is upper triangular with non-zero diagonal elements). Hence, the Gram matrix $A=(a_{ij})_{i,j}$ with

(8.14) \begin{align} a_{ij}\,:\!=\,\int _0^1 \psi _i(t)\psi _j(t)\,{d} t \end{align}

is positive definite.

We have by (7.3), similarly to (6.15)–(6.18),

(8.15) \begin{align} {Cov}\bigl ({S_{in},S_{jn}}\bigr )& =\sum _{k=1}^n \sum _{q=1}^n {Cov}\bigl [{f_i(X_k),f_j(X_q)}\bigr ] = \sum _{r=-m}^m\sum _{k=1+r_-}^{n-r_+}{Cov}\bigl [{f_i(X_k),f_j(X_{k+r})}\bigr ] \notag \\& = \sum _{r=-m}^m(n-|r|){Cov}\bigl [{f_i(X_k),f_j(X_{k+r})}\bigr ] = \sum _{r=-m}^m(n-|r|)\gamma _{i,j,r}, \end{align}

and thus, as $n\to \infty$ ,

(8.16) \begin{align} {Cov}\bigl ({S_{in},S_{jn}}\bigr )/n& \to \sum _{r=-m}^m\gamma _{i,j,r} \,=\!:\, b_{ij}. \end{align}

Note that (6.22) can be written as

(8.17) \begin{align} \sigma ^2=\sum _{i,j=1}^\ell b_{ij}a_{ij}. \end{align}

The covariance matrices $ ({{Cov}(S_{in},S_{jn})} )_{i,j=1}^\ell$ are positive semidefinite, and thus so is the limit $B=(b_{ij})$ defined by (8.16). Hence Lemma 8.1 applies and yields, using (8.17) and the definition of $b_{ij}$ in (8.16), the equivalence (i) $\iff$ (iii).

Furthermore, (8.16) yields (iii) $\iff$ (iv).

The implication (iv) $\implies$ (v) is trivial, and the converse follows by the Cauchy–Schwarz inequality.

If (iii) holds, then (6.20) yields ${Var}\ \widehat{U}_n = O \big({n^{2\ell -2}} \big)$ , and (ii) follows by (6.21). Conversely, (ii) $\implies$ (i) by (3.18).

Moreover, for $m\geqslant 1$ , (v) $\iff$ (vi) holds by [Reference Janson36, Theorem 1], recalling ${\mathbb{E}} f_j(X_k)=0$ by (6.4). (Recall also that any stationary sequence $(W_k)_1^\infty$ of real random variables can be extended to a doubly-infinite stationary sequence $(W_k)_{-\infty }^\infty$ .) The case $m=0$ is trivial, since then (v) is equivalent to ${Var} f_j(X_k)=0$ and thus $f_j(X_k)=0$ a.s. by (6.4), while (vi) should be interpreted to mean that (8.6) holds for some non-random $Z_{j,k}=z_j$ .

Finally, suppose that $(X_i)_1^\infty$ is a block factor. In this case, [Reference Janson36, Theorem 2] shows that $Z_{j,k}$ can be chosen as in (8.7). (Again, the case $m=0$ is trivial.) Then (8.8) is an immediate consequence of (8.6)–(8.7).

Proof. As in the proof of Theorem 3.4, it suffices to consider $U_n(g)$ with $g$ given by Lemma 4.3 (with $M=D+1$ ). The first part then is an immediate consequence of Theorem 8.1(i) $\Leftrightarrow$ (vi) applied to $g$ and $Y_i\,:\!=\,(X_i,\ldots,X_{i+D})$ , with appropriate substitutions $\ell \mapsto b$ and $m\mapsto m+D$ .

The second part follows similarly by the last part of Theorem 8.1, with $\xi _i=X_i$ ; note that then $(Y_i)$ is a block factor as in (2.2), with $m$ replaced by $D$ .

Proof of Theorem 3.5. We consider $U_n(f,{\mathcal{D}})$ ; the argument for $U_n(f;\,{{\mathcal{D}}{=}})$ is identical, and $U_n(f)$ is a special case.

Let $\mathcal{I}$ denote the set of all indices $(i_1,\ldots,i_\ell )$ in the sum (3.2); thus (3.2) can be written $U_n(f;\,{\mathcal{D}})=\sum _{I\in{\mathcal{I}}} Z_I$ , where $Z_{i_1,\ldots,i_\ell }\,:\!=\,f(X_{i_1},\ldots,X_{i_\ell })$ . Note that the size $|{\mathcal{I}}| \sim C n^b$ for some $C\gt 0$ , where $b=b({\mathcal{D}})$ .

We define a graph $\widehat{\mathcal{I}}$ with vertex set $\mathcal{I}$ by putting an edge between $I=(i_1,\ldots,i_\ell )$ and $I^{\prime}=(i^{\prime}_1,\ldots,i^{\prime}_\ell )$ if and only if $|i_j-i^{\prime}_k|\leqslant m$ for some $j,k\in \{{1\ldots,\ell }\}$ . Let $\Delta$ be 1 + the maximum degree of the graph $\widehat{\mathcal{I}}$ ; it is easy to see that $\Delta =O\big(n^{b-1}\big)$ . Moreover, it follows from the $m$ -dependence of $(X_i)$ that $\widehat{\mathcal{I}}$ is a dependency graph for the random variables $(Z_I)_I$ , meaning that if $A$ and $B$ are two disjoint subsets of $\mathcal{I}$ such that there is no edge between $A$ and $B$ , then the two random vectors $(Z_I)_{I\in A}$ and $(Z_I)_{I\in B}$ are independent.

The result now follows from [Reference Rinott54, Theorem 2.2], which in our notation yields the following bound, with $\sigma ^2_n\,:\!=\,{Var}\ U_n \sim \sigma ^2 n^{2b-1}$ and $B\,:\!=\,2\sup |f|$ , which implies $|Z_I-{\mathbb{E}} Z_I|\leqslant B$ a.s. for every $I\in{\mathcal{I}}$ :

(9.1) \begin{align} d_K& \leqslant \frac{1}{\sigma _n} \biggl \{{(2\pi )^{-1/2} \Delta B + 16\biggl ({\frac{|{\mathcal{I}}|\Delta }{\sigma ^2_n}}\biggr )^{1/2} \Delta B^2 + 10\biggl ({\frac{|{\mathcal{I}}|\Delta }{\sigma ^2_n}}\biggr ) \Delta B^3}\biggr \} \notag \\& \leqslant C \frac{\Delta }{\sigma _n} \leqslant C n^{-1/2}, \end{align}

since $|{\mathcal{I}}|\Delta \leqslant C n^{b+b-1}\leqslant C \sigma ^2_n$ and $B$ is a constant. (Alternatively, one could use the similar bound in [Reference Fang20, Theorem 2.1].)

Proof. We argue as in [Reference Janson37, Lemmas 4.4 and 4.7] with some minor differences. By (10.2)–(10.3), $f(x_1,\ldots,x_\ell ) =\widehat{F}_\ell (x_1,\ldots,x_\ell ) =\sum _{k=1}^\ell F_k(x_1,\ldots,x_k)$ for a.e. $x_1,\ldots,x_\ell$ , and thus, a.s.,

(10.9) \begin{equation} \begin{split} U_n(f;\,\gt m) &=\sum _{k=1}^\ell \sum _{\substack{1\leqslant i_1\lt \ldots \lt i_{k}\leqslant n\\i_{j+1}-i_j\gt m}} \binom{n-i_k-(\ell -k)m}{\ell -k} F_k({X_{i_1},\ldots,X_{i_k}}) \\ &=\sum _{k=1}^\ell \sum _{i=1}^n \binom{n-i-(\ell -k)m}{\ell -k}\bigl ({U_i(F_k;\,\gt m)-U_{i-1}(F_k;\,\gt m)}\bigr ) \\ &=U_n(F_\ell ;\,\gt m) +\sum _{k=1}^{\ell -1} \sum _{i=1}^{n-1}\binom{n-i-(\ell -k)m-1}{\ell -k-1}U_i(F_k;\,\gt m), \end{split} \end{equation}

using a summation by parts and the identity $\binom{n^{\prime}}{\ell -k}-\binom{n^{\prime}-1}{\ell -k}=\binom{n^{\prime}-1}{\ell -k-1}$ . In particular,

(10.10) \begin{align} |U_n(f;\,\gt m)| &\leqslant |U_n(F_\ell ;\,\gt m)|+\sum _{k=1}^{\ell -1} \sum _{i=1}^{n-1} \binom{n-i-(\ell -k)m-1}{\ell -k-1} U^*_n(F_k;\,\gt m) \notag \\ &= |U_n(F_\ell ;\,\gt m)|+\sum _{k=1}^{\ell -1} \binom{n-(\ell -k)m-1}{\ell -k} U^*_n(F_k;\,\gt m) \notag \\& \leqslant \sum _{k=1}^{\ell } n^{\ell -k} U^*_n(F_k;\,\gt m). \end{align}

Since the right-hand side is weakly increasing in $n$ , it follows that, a.s.,

(10.11) \begin{equation} U^*_n(f;\,\gt m) \leqslant \sum _{k=1}^{\ell } n^{\ell -k} U^*_n(F_k;\,\gt m). \end{equation}

We thus may consider each $F_k$ separately. Let $1\leqslant k\leqslant \ell$ , and let

(10.12) \begin{align} \Delta U_n(F_k;\,\gt m)\,:\!=\,U_n(F_k;\,\gt m)-U_{n-1}(F_k;\,\gt m) . \end{align}

By the definition (4.25), $\Delta U_n(F_k;\,\gt m)$ is a sum of $\binom{n-(k-1)m-1}{k-1}\leqslant n^{k-1}$ terms $F_k\big(X_{i_1},\ldots,X_{i_{k-1}},X_n\big)$ that all have the same distribution as $F_k({\widehat{X}_1,\ldots,\widehat{X}_k})$ , and thus by Minkowski’s inequality and (10.7),

(10.13) \begin{equation} \lVert{\Delta U_n(F_k;\,\gt m)}\rVert _p \leqslant{n}^{k-1}\lVert{F_k(\widehat{X}_1,\ldots,\widehat{X}_k)}\rVert _p \leqslant C{n}^{k-1} . \end{equation}

Furthermore, in each such term $F_k\big(X_{i_1},\ldots,X_{i_{k-1}},X_n\big)$ we have $i_{k-1}\leqslant n-m-1$ . Hence, if we let ${\mathcal{F}}_i$ be the $\sigma$ -field generated by $X_1,\ldots,X_i$ , then, by $m$ -dependence, $X_n$ is independent of ${\mathcal{F}}_{i_{k-1}}$ , whence (10.5) implies

(10.14) \begin{align}{\mathbb{E}} \bigl ({F_k({X_{i_1},\ldots,X_{i_{k-1}},X_n})\mid{\mathcal{F}}_{n-m-1}}\bigr ) &={\mathbb{E}} \bigl ({F_k({X_{i_1},\ldots,X_{i_{k-1}},X_n})\mid X_{i_1},\ldots,X_{i_{k-1}}}\bigr ) \notag \\&=0. \end{align}

Consequently,

(10.15) \begin{align} {\mathbb{E}}\bigl ({\Delta U_n(F_k;\,\gt m)\mid{\mathcal{F}}_{n-m-1}}\bigr )=0. \end{align}

In the independent case $m=0$ treated in [Reference Janson37], this means that $U_n(F_k)$ is a martingale. In general, we may as a substitute split $U_n(F_k;\,\gt m)$ as a sum of $m+1$ martingales. For $j=1,\ldots,m+1$ and $i\geqslant 1$ , let

(10.16) \begin{align} \Delta M_i^{(k,j)}&\,:\!=\,\Delta U_{(i-1)(m+1)+j}(F_k;\,\gt m), \end{align}

(10.17) \begin{align} M_i^{(k,j)} &\,:\!=\,\sum _{q=1}^i\Delta M_q^{(k,j)} =\sum _{q=1}^i\Delta U_{q(m+1)+j}(F_k;\,\gt m) . \end{align}

Then (10.15) implies that $(M_i^{(k,j)})_{i\geqslant 0}$ is a martingale, for each $k$ and $j$ . Hence, Burkholder’s inequality [Reference Gut25, Theorem 10.9.5] yields, for the maximal function $M_n^{(k,j)*}$ ,

(10.18) \begin{align} \lVert{M_n^{(k,j)*}}\rVert _p \leqslant C \biggl \lVert{\biggl ({\sum _{i=1}^n \big|\Delta M_i^{(k,j)}\big|^2}\biggr )^{1/2}}\biggr \rVert _p = C \biggl \lVert{{\sum _{i=1}^n \big|\Delta M_i^{(k,j)}\big|^2}}\biggr \rVert _{p/2}^{1/2}. \end{align}

Furthermore, Minkowski’s inequality yields (since $p/2\geqslant 1$ ), using also (10.16) and (10.13), for $n\geqslant 1$ ,

(10.19) \begin{align} \biggl \lVert{{\sum _{i=1}^n \big|\Delta M_i^{(k,j)}\big|^2}}\biggr \rVert _{p/2} \leqslant \sum _{i=1}^n \Bigl \lVert{\big|\Delta M_i^{(k,j)}\big|^2}\Bigr \rVert _{p/2} = \sum _{i=1}^n \Bigl \lVert{\Delta M_i^{(k,j)}}\Bigr \rVert _{p}^2 \leqslant C n^{1+2(k-1)} . \end{align}

Combining (10.18) and (10.19) yields

(10.20) \begin{align} \lVert{M_n^{(k,j)*}}\rVert _p \leqslant C n^{k-1/2} . \end{align}

It follows from (10.16)–(10.17) that

(10.21) \begin{align} U_n(F_k;\,\gt m) =\sum _{j=1}^{m+1} M^{(k,j)}_{\lfloor{(n-j)/(m+1)}\rfloor +1} . \end{align}

Hence (coarsely),

(10.22) \begin{align} U^*_n(F_k;\,\gt m) \leqslant \sum _{j=1}^{m+1} M^{(k,j)*}_{n}, \end{align}

and thus (10.20) and Minkowski’s inequality yield

(10.23) \begin{align} \bigl \lVert{U^*_n(F_k;\,\gt m)}\bigr \rVert _p \leqslant C n^{k-1/2}, \end{align}

for $k=1,\ldots,\ell$ .

The result (10.8) now follows from (10.23) and (10.11) by a final application of Minkowski’s inequality.

Proof. We use induction on $b$ . We split the induction step into three cases.

Case 1: no constraint, i.e., ${\mathcal{D}}={\mathcal{D}}_\infty$ and $b=\ell$ By (4.27)–(4.28),

(10.27) \begin{align} U_n(f)=U_n(f;\,{\mathcal{D}}_\emptyset )= U_n(f;\,\gt m) -\sum _{J\neq \emptyset }({-}1)^{|J|}U_n(f;\,{\mathcal{D}}_J). \end{align}

Thus,

(10.28) \begin{align} U^*_n(f) \leqslant U^*_n(f;\,\gt m)+\sum _{J\neq \emptyset }U^*_n(f;\,{\mathcal{D}}_J). \end{align}

Suppose first that $\mu =0$ ; then Lemma 10.1 applies to $U^*_n(f;\,\gt m)$ . Furthermore, the induction hypothesis applies to each term in the sum in (10.28), since $b({\mathcal{D}}_J)=\ell -|J|\leqslant \ell -1=b-1$ . Hence, Minkowski’s inequality yields

(10.29) \begin{align} \bigl \lVert{U^*_n(f)}\bigr \rVert _p \leqslant \bigl \lVert{U^*_n(f;\,\gt m)}\bigr \rVert _p+\sum _{J\neq \emptyset }\bigl \lVert{U^*_n(f;\,{\mathcal{D}}_J)}\bigr \rVert _p \leqslant C n^{\ell -1/2}+ C n^{\ell -1} . \end{align}

When $\mu =0$ , (3.7) yields

(10.30) \begin{align} {\mathbb{E}} U_n(f)=O\bigl ({n^{\ell -1}}\bigr ). \end{align}

Now (10.24) follows from (10.29) and (10.30), which shows (10.24) when $\mu =0$ . The general case follows by considering $f-\mu$ ; this does not affect $U_n(f)-{\mathbb{E}} U_n(f)$ .

Finally, both (10.25) and (10.26) follow from (10.24) and (3.7).

Case 2: an exact constraint ${\mathcal{D}}{=}$ , $b\lt \ell$ . This is an immediate consequence of (4.9) in Lemma 4.2 and Case 1 applied to $g$ ; note that $g$ too satisfies $({A}_p)$ by (4.19).

Case 3: a constraint $\mathcal{D}$ , $b\lt \ell$ . This is a consequence of Case 2 by (3.4) and (5.5).

Proof. We consider the second sequence in (10.31); the proof for the first sequence differs only notationally.

We have so far let $f$ be fixed, so the constants above may depend on $f$ . However, it is easy to see that the proof of (10.26) yields

(10.32) \begin{align} \bigl \lVert{U^*_n(f;\,{\mathcal{D}})}\bigr \rVert _p\leqslant C_p \max _{i_1\lt \ldots \lt i_\ell }\lVert{f(X_{i_1},\ldots,X_{i_\ell })}\rVert _p n^{b}, \end{align}

with $C_p$ independent of $f$ (but depending on $p$ ). (Note that we only have to consider a finite set of indices $(i_1,\ldots,i_\ell )$ , as discussed above (3.6).)

Truncate $f$ , and for $B\gt 0$ define $f_B(\textbf{x})\,:\!=\,f(\textbf{x})\boldsymbol{1}\{{|f(\textbf{x})|\leqslant B}\}$ . Then (10.32) yields

(10.33) \begin{align} \bigl \lVert{n^{-b} U^*_n(f-f_B;\,{\mathcal{D}})}\bigr \rVert _p\leqslant C_p \varepsilon (B), \end{align}

where

(10.34) \begin{align} \varepsilon (B)\,:\!=\, \max _{i_1\lt \ldots \lt i_\ell } \lVert{f(X_{i_1},\ldots,X_{i_\ell })\boldsymbol{1}\{{|f(X_{i_1},\ldots,X_{i_\ell })|\gt B}\}}\rVert _p \to 0 \end{align}

as $B\to \infty$ .

Let $q\,:\!=\,2p$ . Since $f_B$ is bounded, we may apply (10.32) (or Theorem 10.1) with $p$ replaced by $q$ and obtain

(10.35) \begin{align} \sup _n \bigl \lVert{n^{-\ell }U^*_n(f_B;\,{\mathcal{D}})}\bigr \rVert _{2p} \lt \infty . \end{align}

Hence, for any $B$ , the sequence $n^{-\ell } U^*_n(f_B;\,{\mathcal{D}})$ is uniformly $p$ th-power integrable. Since $ U^*_n(f;\,{\mathcal{D}}) \leqslant U^*_n(f_B;\,{\mathcal{D}})+ U^*_n(f-f_B;\,{\mathcal{D}})$ , the result now follows from the following simple observation.