Randomized quasi-Monte Carlo and replicate error

For $q,k\ge 1$ set $\varphi (q,k)=\frac{(q+k-2)(q+k-1)}{2}+q$. Listing pairs by increasing $q+k$ and then increasing $q$ shows that $\varphi$ is a bijection. Each digit $D_j$ lies in $\{0,\dots ,b-1\}$, and prescribing the first $N$ consecutive digits specifies exactly one half-open interval of length $b^{-N}$ by [F1]. More generally, prescribing any $s$ distinct digit positions among the first $N$ leaves exactly $b^{N-s}$ such intervals, so those digits have joint probability $b^{-s}$.

Fix distinct $q_1,\dots ,q_s$ and positive integers $n_1,\dots ,n_s$. The index sets $\{\varphi (q_i,k):1\le k\le n_i\}$ are disjoint. If their digit values are prescribed, let $N$ be the largest used index. Exactly $b^{N-{\sum }_i{n}_i}$ length-$b^{-N}$ intervals have those values, so their joint probability is $b^{-{\sum }_i{n}_i}$. For each $q$ and $m\ge 1$, the event $T_{q,m}=\{D_{\varphi (q,k)}=b-1\text{ for every }k\ge m\}$ is contained, for every $L\ge 1$, in the event that its first $L$ tail digits all equal $b-1$. Step 1.1 gives $\mathbb{P}(T_{q,m})\le b^{-L}$ for every $L$, so [F5] gives $\mathbb{P}(T_{q,m})=0$. The countable union of these events over $q,m$ is null. Outside it, each stream has no tail consisting entirely of $b-1$ digits; consequently a prescribed initial digit word places its numeric sum in the corresponding half-open base-$b$ interval, not at its right endpoint. Thus every finite family of the numeric ${\tilde{U}}_{q_i}$ has the product uniform cylinder probabilities outside a null set. The event ${\tilde{U}}_q=1$ is contained in $T_{q,1}$, so replacing that value by $0$ leaves every finite-dimensional law unchanged.

Each digit $D_j$ is constant on the finite Borel partition into intervals of length $b^{-j}$. A finite partial sum defining ${\tilde{U}}_q$ is constant on the common refinement at the largest digit index it uses, hence is measurable. Its pointwise limit is measurable by [F4]. The map $g:[0,1]\to [0,1)$ given by $g(x)=x$ for $x<1$ and $g(1)=0$ is Borel; explicitly, for Borel $A\subseteq [0,1)$, $g^{-1}(A)=(A\cap [0,1))$ together with $\{1\}$ exactly when $0\in A$. Therefore $U_q=g({\tilde{U}}_q)$ is measurable. For any finite set of indices $q_i$, the $b$-adic cylinder rectangles for $(U_{q_i})$ form a $\pi$-system generating the Borel sets of $[0,1{)}^s$: every open set is the union of the countably many such cells contained in it, since the cell diameters tend to zero. Step 2.1 gives agreement there with product Lebesgue measure; [F2] therefore gives the product law on all Borel sets. Hence the $U_q$ are mutually independent and each is uniform.

Each map $u\mapsto {\sigma }_{\min \{b!-1,\lfloor b!u\rfloor \}}$ is Borel, with the preimage of ${\sigma }_r$ equal to $[r\mathrm{/}b!,(r+1)\mathrm{/}b!)$ for $0\le r<b!$. For distinct $q_1,\dots ,q_s$, independence and uniformity from step 3.1 give $\mathbb{P}({\pi }_{q_i}={\sigma }_{r_i}\text{ for every }i)={\prod }_i\mathbb{P}(U_{q_i}\in [r_i\mathrm{/}b!,(r_i+1)\mathrm{/}b!))=(b!{)}^{-s}$. These maps are measurable and the joint probabilities show that the ${\pi }_q$ are mutually independent uniform permutations.

Let ${\mathcal{A}}_b$ be the algebra of finite unions of base-$b$ elementary boxes in $[0,1{)}^d$. There are countably many such boxes. For any open $O\subseteq [0,1{)}^d$ and $x\in O$, choose ${\delta }_x>0$ such that the relative ${\delta }_x$-ball about $x$ lies in $O$. At every sufficiently large level $k$, the unique level-$k$ box containing $x$ has diameter at most $\sqrt{d}{b}^{-k}<{\delta }_x$, hence is contained in $O$. Therefore $O$ is the union of the countably many base-$b$ boxes contained in it. Thus $\sigma ({\mathcal{A}}_b)$ contains every open set and equals the Borel $\sigma$-algebra.

Let $\mathcal{C}$ be the Borel sets $E$ for which every $\eta >0$ admits $A\in {\mathcal{A}}_b$ with $\lambda (E\mathrm{△}A)<\eta$. It contains ${\mathcal{A}}_b$ and is closed under complements and finite unions by the symmetric-difference inequalities and the algebra property. If $E_i\in \mathcal{C}$, then $E^{(N)}={\bigcup }_{i=1}^N{E}_i\uparrow E={\bigcup }_{i\ge 1}{E}_i$; [F2] lets us choose $N$ with $\lambda (E\setminus E^{(N)})<\eta \mathrm{/}2$. Approximate each of the finitely many $E_i$, $i\le N$, within $\eta \mathrm{/}(2N)$ and union those approximants. The resulting member of ${\mathcal{A}}_b$ is within $\eta$ of $E$. Thus $\mathcal{C}$ is a $\sigma$-algebra, so step 1.1 gives $\mathcal{C}$ equal to all Borel sets.

By [F1], choose a finite simple function $s={\sum }_{j=1}^M{c}_j{\mathbf{1}}_{E_j}$ with $\mathrm{\parallel }f-s{\mathrm{\parallel }}_2<\epsilon \mathrm{/}2$. By step 2.1 choose $A_j\in {\mathcal{A}}_b$ so that ${\sum }_{j=1}^M\mathrm{\mid }{c}_j\mathrm{\mid }\lambda (E_j\mathrm{△}{A}_j{)}^{1\mathrm{/}2}<\epsilon \mathrm{/}2$. The finite box step function $g={\sum }_j{c}_j{\mathbf{1}}_{A_j}$ then satisfies $\mathrm{\parallel }s-g{\mathrm{\parallel }}_2\le {\sum }_j\mathrm{\mid }{c}_j\mathrm{\mid }\mathrm{\parallel }{\mathbf{1}}_{E_j}-{\mathbf{1}}_{A_j}{\mathrm{\parallel }}_2={\sum }_j\mathrm{\mid }{c}_j\mathrm{\mid }\lambda (E_j\mathrm{△}{A}_j{)}^{1\mathrm{/}2}<\epsilon \mathrm{/}2$.

The triangle inequality gives $\mathrm{\parallel }f-g{\mathrm{\parallel }}_2\le \mathrm{\parallel }f-s{\mathrm{\parallel }}_2+\mathrm{\parallel }s-g{\mathrm{\parallel }}_2<\epsilon$. Since $f$ and $\epsilon$ were arbitrary, the stated finite-span density follows.

If $u$ is the full coordinate set, then $f_u=f$ and ${\mathrm{\partial }}_u{f}_u={\mathrm{\partial }}_{u}f$. Otherwise, [F6] makes $f_u$ continuous: changing $x_u$ by less than $\delta$ changes the integrand uniformly in $x_{-u}$, and integration over a unit-volume cube preserves that bound. Repeated application of [F2] to the complementary coordinates, with [F4] identifying iterated integrals and [A1, F5] identifying the Riemann and Lebesgue integrals, gives ${\mathrm{\partial }}_u{f}_u(x_u)={\int }_{[0,1{]}^{d-\mathrm{\mid }u\mathrm{\mid }}}{\mathrm{\partial }}_{u}f(x_u,x_{-u})d{x}_{-u}$. The same uniform-continuity argument makes this derivative continuous. Since $\mathrm{\mid }{\mathrm{\partial }}_{u}f\mathrm{\mid }$ is continuous on the nonempty compact cube, [F7] gives a finite supremum; the displayed integral (or $f_u=f$ in the full-set case) shows $M_u\le {\sup }_{[0,1{]}^d}\mathrm{\mid }{\mathrm{\partial }}_{u}f\mathrm{\mid }$.

Fix $(\tau ,\rho )$ and let $c_{u,\kappa ,\tau ,\rho }=\int f_u(x_u){\prod }_{j\in u}{h}_{k_j,t_j,r_j}(x_j)d{x}_u$. The integrand is bounded and continuous on each cell of a finite rectangular partition, so it is Riemann integrable; by [A1, F5] this coefficient is also its Riemann integral. Each contrast has integral zero on its parent. Subtracting the left-endpoint value in one coordinate therefore leaves the integral unchanged. Applying [F3] successively in every coordinate expresses the resulting alternating finite difference as the iterated integral of ${\mathrm{\partial }}_u{f}_u$ over ${\prod }_{j\in u}[a_j,x_j]$; its absolute value is at most $M_u{\prod }_{j\in u}{b}^{-k_j}$. The outer integral of the absolute contrast product factors by [F4] as ${\prod }_{j\in u}\mathrm{\parallel }{h}_{k_j,t_j,r_j}{\mathrm{\parallel }}_1$.

From the explicit child values in [F1], for $1\le r<b$, $\mathrm{\parallel }{h}_{k,t,r}{\mathrm{\parallel }}_1=2\sqrt{\frac{r}{r+1}}{b}^{-(k+1)\mathrm{/}2}\le 2b^{-k\mathrm{/}2}\mathrm{.}$ Thus step 2.1 gives $\mathrm{\mid }{c}_{u,\kappa ,\tau ,\rho }\mathrm{\mid }\le 2^{\mathrm{\mid }u\mathrm{\mid }}{M}_u{b}^{-3\mathrm{\mid }\kappa \mathrm{\mid }\mathrm{/}2}$.

For fixed $u,\kappa$, the contrasts at distinct translations have disjoint supports, and at the same parent their child coefficient vectors are orthonormal by the dot-product calculation in [F1]. Their tensor products are therefore orthonormal. There are $b^{\mathrm{\mid }\kappa \mathrm{\mid }}(b-1{)}^{\mathrm{\mid }u\mathrm{\mid }}$ such products, so ${\sigma }_{u,\kappa }^2={\sum }_{\tau ,\rho }\mathrm{\mid }{c}_{u,\kappa ,\tau ,\rho }{\mathrm{\mid }}^2\le b^{\mathrm{\mid }\kappa \mathrm{\mid }}(b-1{)}^{\mathrm{\mid }u\mathrm{\mid }}{4}^{\mathrm{\mid }u\mathrm{\mid }}{M}_u^2{b}^{-3\mathrm{\mid }\kappa \mathrm{\mid }}=4^{\mathrm{\mid }u\mathrm{\mid }}(b-1{)}^{\mathrm{\mid }u\mathrm{\mid }}{M}_u^2{b}^{-2\mathrm{\mid }\kappa \mathrm{\mid }}$, as claimed.

On one parent interval, the unnormalized child coefficient vector for contrast $r$ is $(1,\dots ,1,-r,0,\dots ,0)$, with $r$ initial ones. Its entries sum to zero and its squared Euclidean norm is $r(r+1)$. The normalization in [F1] therefore makes each $h_{k,t,r}$ have integral zero and squared $L^2$ norm one. If $r<s$ are contrasts on the same parent, the $s$-contrast is constant on the first $r+1$ children, where the $r$-contrast coefficients sum to zero, so their inner product is zero. Distinct parents have disjoint interiors. At different levels, a finer parent is either disjoint from a coarser parent or lies in one of its children, where the coarser contrast is constant; the finer contrast has integral zero. Hence all one-dimensional contrasts are orthonormal and orthogonal to $1$.

On the partition into $b^J$ level-$J$ intervals, the constant and contrasts with $0\le k<J$ are orthonormal by step 1.1. Their number is $1+(b-1){\sum }_{k=0}^{J-1}{b}^k=b^J$, the dimension of the space of functions constant on those intervals. They therefore form an orthonormal basis of that finite-dimensional space.

Products of the one-dimensional bases from step 2.1 are orthonormal on rectangular grids by [F5]: each factor is bounded and supported on a finite union of intervals, hence integrable, and the cube is a finite-measure product space. Their inner products therefore factor coordinatewise; a coordinate with distinct basis functions gives zero. Their finite tensor products span each rectangular-grid step function because each one-dimensional basis in step 2.1 spans its level grid. Thus the family indexed by $(u,\kappa ,\tau ,\rho )$ in [F1], together with $1$, is orthonormal and its span contains every base-$b$ box step function.

By [F2] the closed span in step 3.1 is all $L^2([0,1{)}^d)$. Apply [F3] and [F4], using [A1], to obtain the orthogonal expansion of $f$. Grouping the finitely many translation and contrast terms for each fixed $(u,\kappa )$ gives exactly ${\nu }_{u,\kappa }(f)$ from [F1]; the empty-coordinate term is the constant $I(f)$. Since $U$ has uniform law on the unit cube, [F7] identifies $\mathbb{E}[f(U)]=I(f)$ and its centered second moment with $\mathrm{\parallel }f-I(f){\mathrm{\parallel }}_2^2$; [F6] identifies this with $\mathrm{Var}(f(U))$. Parseval then gives the displayed sum of squared component norms.

By [F1], the law of every $X_i$ is normalized Lebesgue measure. Since $f$ is integrable for that law, [F2] gives $\mathbb{E}[f(X_i)]={\int }_{[0,1{)}^d}f(x)dx=I(f)$ for each $i$, and each $f(X_i)$ is integrable.

The finite sum of the integrable variables $f(X_i)$ is integrable. By linearity, $\mathbb{E}[{\widehat{I}}_n(f)]=n^{-1}{\sum }_{i=1}^n\mathbb{E}[f(X_i)]=n^{-1}{\sum }_{i=1}^{n}I(f)=I(f)$. No covariance or independence assumption is used.

By [F1], independent full-set randomizations give independent estimates with the same law. By [F2] their common mean is $I$, and the stated finite variance supplies the moment hypothesis of [F3].

Apply [F3] to $Z_r={\widehat{I}}_r$. It gives $\mathbb{E}[{\widehat{V}}_R]=\mathrm{Var}({\bar{I}}_R)$. Independence and the common variance ${\tau }^2$ give $\mathrm{Var}({\bar{I}}_R)=R^{-2}{\sum }_r\mathrm{Var}({\widehat{I}}_r)={\tau }^2\mathrm{/}R$. Since the data are fixed in the probability law of these replicates, this variance concerns randomization only.

Fix a point $a_i$ and coordinate $j$. Its input prefixes of lengths $0,1,\dots ,K-1$ are distinct nodes, so the corresponding permutations are independent. Conditional on the fixed input digits, each output digit is uniform on $\{0,\dots ,b-1\}$, independently of the earlier output digits. For each $m\ge 1$, the event that all output digits from position $m$ onward equal $b-1$ is contained, for every $L\ge 1$, in the event that its first $L$ digits equal $b-1$, which has probability $b^{-L}$; [F5] makes that tail event null. The countable union over $m$ is null. Outside it, every specified output prefix of length $K$ puts the numeric output in the corresponding half-open base-$b$ interval, not at its right endpoint. These cylinders form a generating $\pi$-system, so [F4] extends their probabilities $b^{-K}$ to the uniform Borel law. Independent permutation families across coordinates give $X_i\sim \mathrm{Unif}([0,1{)}^d)$. The finite set of points and coordinates has a common probability-one event on which none of their expansions is eventually all $b-1$.

At any fixed digit depth $K$, the map from input words of length $K$ to output words is a bijection: it is a bijection at depth one, and at each subsequent depth every existing prefix is extended by the bijection supplied by its own permutation. Taking the coordinatewise product gives a bijection of all depth-vector digit boxes. It therefore permutes the boxes of total depth $m-t$ and preserves the number of input points in each image box. On the probability-one event from step 1.1, these digit boxes are exactly the numeric half-open elementary intervals of the scrambled coordinates. By [F1] every such output box contains $\lambda b^t$ points.

Step 1.1 proves marginal uniformity and step 2.1 proves net preservation outside the null expansion events identified in step 1.1. These are exactly the two assertions.

For a fixed point and coordinate, adding an independent uniform digit modulo $b$ makes the output digit uniform; the output digits are independent because the shift digits at distinct positions are independent. Thus every prescribed output prefix of length $K$ has probability $b^{-K}$. For each $m\ge 1$, the event that every output digit from position $m$ onward is $b-1$ is contained, for every $L\ge 1$, in the event that its first $L$ tail digits are all $b-1$, which has probability $b^{-L}$; [F5] makes that tail event null. Outside the countable union of these null events, each prefix places the numeric output in its corresponding half-open interval, not at its right endpoint. These intervals form a generating $\pi$-system, so [F4] extends the prefix probabilities to the uniform Borel law. The coordinate shift streams are independent, hence the same cylinder calculation for rectangles in $[0,1{)}^d$ gives each vector the uniform cube law. The half-open modification at output value $1$ changes only a null event.

For any coordinate and depth $K$, adding a fixed digit word modulo $b$ is a bijection of the finite set of length-$K$ words. The full coordinatewise map is therefore a bijection of the depth-vector digit boxes. It permutes, without splitting, all boxes of total depth $m-t$, preserving their point counts. Outside the null expansion events in step 1.1 these digit boxes are exactly the numeric half-open elementary intervals, so [F1] gives the same count $\lambda b^t$ in each shifted box.

Step 1.1 proves each shifted point uniform, and step 2.1 proves preservation of the net counts with probability one.

By [F1] the replicate estimates form an IID sequence. Their common mean is $I$ by [F2], and their variance is the positive finite number ${\tau }^2$ by hypothesis. Under [A1], apply [F4] to obtain $Y_R:=\sqrt{R}({\bar{I}}_R-I)\mathrm{/}\tau \Rightarrow N(0,1)$.

Let $s_R^2=(R-1{)}^{-1}{\sum }_{r=1}^R({\widehat{I}}_r-{\bar{I}}_R{)}^2$. The finite second moment and [F5] give $s_R^2\to {\tau }^2$ almost surely, hence $s_R\mathrm{/}\tau \to 1$ in probability. By [F3], $\sqrt{{\widehat{V}}_R}=s_R\mathrm{/}\sqrt{R}$; on $s_R>0$ the displayed statistic equals $Y_R\mathrm{/}(s_R\mathrm{/}\tau )$.

Since $\tau >0$, step 2.1 implies $\mathbb{P}(s_R=0)\to 0$. Assigning any fixed value on that event matches the quotient convention in [F7]. Apply [F7] to step 1.1 with denominator $s_R\mathrm{/}\tau \to 1$ to obtain the stated standard-normal limit. The limit is in $R$ at fixed $n$, not in the point count $n$.