Deterministic quasi-Monte Carlo and discrepancy

Fix an integer dimension $d\ge 1$. A point multiset is a finite ordered list $P=(x_0,\dots ,x_{N-1})$ with $N\ge 1$ and $x_i=(x_{i1},\dots ,x_{id})\in [0,1{)}^d$; repeated points are counted with their multiplicities. For $u=(u_1,\dots ,u_d)\in [0,1{]}^d$, its anchored half-open box and its volume are $B(u):={\prod }_{j=1}^d[0,u_j),\mathrm{vol}(B(u)):={\prod }_{j=1}^d{u}_j\mathrm{.}$ The star discrepancy of $P$ is $D_N^{\ast }(P):={\sup }_{u\in [0,1{]}^d}\mid \frac{1}{N}{\sum }_{i=0}^{N-1}{\mathbf{1}}_{B(u)}(x_i)-{\prod }_{j=1}^d{u}_j\mid \mathrm{.}$ An infinite sequence $(x_n{)}_{n\ge 0}$ in $[0,1{)}^d$ is uniformly distributed if $D_N^{\ast }(x_0,\dots ,x_{N-1})\to 0$ as $N\to \mathrm{\infty }$. For a bounded Riemann-integrable $f:[0,1{]}^d\to \mathbb{R}$, the cube integral and the point-set cube quadrature are $I_d(f):={\int }_{[0,1{]}^d}f(x)dx,Q_P(f):=\frac{1}{N}{\sum }_{i=0}^{N-1}f(x_i),$ where $I_d$ is the Riemann integral of The lower and upper Darboux integrals over a nondegenerate rectangle in ${\mathbb{R}}^m$. No randomness is part of $Q_P$.

Let $b\ge 2$ be an integer. A base-$b$ elementary interval in dimension $d$ is $E={\prod }_{j=1}^d[a_j{b}^{-k_j},(a_j+1)b^{-k_j}),$ where each $k_j\ge 0$ and each $a_j$ is an integer with $0\le a_j<b^{k_j}$. For integers $m\ge 0$ and $0\le t\le m$, a point multiset $P$ is a $(t,m,d)$-net in base $b$ if it has $b^m$ entries and every base-$b$ elementary interval with ${\sum }_{j=1}^d{k}_j=m-t$ contains exactly $b^t$ entries, counted with multiplicity. A sequence $(x_n{)}_{n\ge 0}$ in $[0,1{)}^d$ is a $(t,d)$-sequence in base $b$ if for every $m\ge t$ and $k\ge 0$, the aligned block $(x_{k{b}^m},\dots ,x_{(k+1)b^m-1})$ is a $(t,m,d)$-net.

For a prime integer $p$, we have $p\ge 2$ (Prime and composite integers: $p$ is prime when $p>1$ and its only positive divisors are $1$ and $p$). Write ${\mathbb{F}}_p:=\mathbb{Z}\mathrm{/}p\mathbb{Z}$, which is a field by For every prime $p$, the two operations on $\mathbb{Z}\mathrm{/}p$ make it a field. By Division with remainder in $\mathbb{Z}$: for $a\in \mathbb{Z}$ and $b>0$ there are unique $q,r\in \mathbb{Z}$ with $a=qb+r$ and $0\le r<b$, each residue class has exactly one representative in $\{0,\dots ,p-1\}$, and every $n\in \{0,\dots ,p^m-1\}$ has a unique base-$p$ expansion $n={\sum }_{r=1}^m{n}_{r-1}{p}^{r-1}$ with digits $n_{r-1}\in \{0,\dots ,p-1\}$. The integer powers use Integer powers $a^m$. A digital point set in base $p$ is generated from matrices $C_1,\dots ,C_d\in {\mathbb{F}}_p^{m\times m}$ as follows. For each such $n$, let $v(n)=(n_0,\dots ,n_{m-1}{)}^T\in {\mathbb{F}}_p^m$, interpreting each digit as its residue class, and compute $y^{(j)}=C_{j}v(n)$ in ${\mathbb{F}}_p^m$. Taking the unique representatives $y_r^{(j)}\in \{0,\dots ,p-1\}$, set $x_{n,j}:={\sum }_{r=1}^m{y}_r^{(j)}{p}^{-r}\mathrm{.}$ Since $0\le y_r^{(j)}\le p-1$, the finite geometric sum gives $0\le x_{n,j}\le {\sum }_{r=1}^m(p-1)p^{-r}=1-p^{-m}<1$; the identity follows by telescoping with the integer-power laws Laws of integer exponents, and $p^{-m}>0$ by Monotonicity of $x\mapsto x^n$ and of $n\mapsto a^n$ and Inverses of positives are positive, and reciprocation reverses order. It is a digital $(t,m,d)$-net only if this generated point multiset also satisfies the stated $(t,m,d)$-net counting condition; arbitrary generator matrices need not do so.

A digital sequence is generated by infinite matrices $C_j=(c_{r,k}^{(j)}{)}_{r,k\ge 1}$ over ${\mathbb{F}}_p$. For each $n\ge 0$, pad its finite base-$p$ expansion with zero digits and, for every $r,j$, compute the finite field sum $y_{r,j}(n)={\sum }_{k\ge 1}{c}_{r,k}^{(j)}{n}_{k-1}$; only finitely many summands are nonzero. Let ${\tilde{y}}_{r,j}(n)\in \{0,\dots ,p-1\}$ be its unique integer representative. The output coordinate is the real series $x_{n,j}:={\sum }_{r=1}^{\mathrm{\infty }}{\tilde{y}}_{r,j}(n)p^{-r}\mathrm{.}$ This series is defined by Series, partial sums, convergence and the sum, divergence, and the tail series and converges: its terms satisfy $0\le {\tilde{y}}_{r,j}(n)p^{-r}\le (p-1)p^{-r}$; since $p\ge 2$, Inverses of positives are positive, and reciprocation reverses order gives $p^{-1}\in (0,1)$, and the bounding geometric series ${\sum }_{r=1}^{\mathrm{\infty }}(p-1)p^{-r}$ converges to $1$ by For $\mathrm{\mid }r\mathrm{\mid }<1$, ${\sum }_{k\ge 0}{r}^k=1\mathrm{/}(1-r)$, and for $\mathrm{\mid }r\mathrm{\mid }\ge 1$ the series diverges. The comparison theorem If $0\le a_k\le b_k$ eventually, convergence of $\sum b_k$ gives convergence of $\sum a_k$, and divergence of $\sum a_k$ gives divergence of $\sum b_k$ therefore gives convergence of the output series. Its sum lies in $[0,1]$; the resulting points are required to lie in $[0,1{)}^d$. It is a digital $(t,d)$-sequence when it also satisfies the aligned-block net condition above. No discrepancy rate follows from these definitions alone.

Fix $d\ge 1$ and a real function $f:[0,1{]}^d\to \mathbb{R}$. For each nonempty coordinate subset $u\subseteq \{1,\dots ,d\}$, restrict $f$ to the face adjacent to the all-ones corner by setting $f_u(x_u):=f(z),z_j=\{\begin{array}{ll}{x}_j,& j\in u,\\ 1,& j\mathrm{\notin }u\mathrm{.}\end{array}$ For a finite coordinate grid on $[0,1{]}^{\mathrm{\mid }u\mathrm{\mid }}$, write its cells as $R_k={\prod }_{j\in u}[t_{j,k_j},t_{j,k_j+1}]$. For a cell with lower and upper vertices $a,b$, define its alternating increment $\mathrm{\Delta }(f_u;R_k):={\sum }_{ϵ\in \{0,1{\}}^{\mathrm{\mid }u\mathrm{\mid }}}(-1{)}^{\mathrm{\mid }u\mathrm{\mid }-\mathrm{\mid }ϵ\mathrm{\mid }}{f}_u(z_{ϵ}),$ where $(z_{ϵ}{)}_j=a_j$ if ${ϵ}_j=0$ and $(z_{ϵ}{)}_j=b_j$ if ${ϵ}_j=1$. The Vitali variation of $f_u$ is $V_V(f_u):={\sup }_{\text{finite coordinate grids on }[0,1{]}^{\mathrm{\mid }u\mathrm{\mid }}}{\sum }_k\mathrm{\mid }\mathrm{\Delta }(f_u;R_k)\mathrm{\mid }\mathrm{.}$ The Hardy–Krause variation anchored at the upper corner is $V_{HK,1}(f):={\sum }_{\mathrm{\varnothing }\mathrm{\ne }u\subseteq \{1,\dots ,d\}}{V}_V(f_u),$ with value $+infty$ if any summand is infinite. For $d=1$ this is the ordinary total variation on $[0,1]$. The anchor is part of the convention: every coordinate outside $u$ is fixed at $1$. The smooth mixed-derivative formula for this convention is proved separately for $C^d$ functions.

The same Vitali-variation definition applies on a nondegenerate rectangle $R={\prod }_{j=1}^q[a_j,b_j]$: each coordinate grid starts at $a_j$ and ends at $b_j$. For a subrectangle $R\subseteq [0,1{]}^d$, write $V_{HK,1}(f;R)$ for the sum of the Vitali variations of its face restrictions with complementary coordinates fixed at the upper endpoints of $R$. If a varied side has length zero, that face's Vitali variation is defined to be zero. For $R=[0,1{]}^d$ this notation is exactly $V_{HK,1}(f)$.

Let $d\ge 1$ and let $h:[0,1{]}^d\to \mathbb{R}$ be bounded and nondecreasing in each coordinate while the other coordinates are fixed. Then $h$ is Riemann integrable on $[0,1{]}^d$.

Let $f:[0,1{]}^d\to \mathbb{R}$ and let $R={\prod }_{j=1}^d[a_j,b_j]\subseteq [0,1{]}^d$ be a closed axis-parallel rectangle, allowing zero side lengths. For each nonempty subset $u\subseteq \{1,\dots ,d\}$, define the lower-face restriction $f_{u,0,R}(x_u):=f(z),z_j=\{\begin{array}{ll}{x}_j,& j\in u,\\ a_j,& j\mathrm{\notin }u\mathrm{.}\end{array}$ If every side indexed by $u$ is nondegenerate, its Vitali variation on ${\prod }_{j\in u}[a_j,b_j]$ is the supremum of the sums of absolute alternating increments over finite product grids on that rectangle, using the convention of Hardy–Krause variation anchored at the upper corner. If any side indexed by $u$ has length zero, that term is defined to be zero. The Hardy–Krause variation on $R$ anchored at its lower corner is $V_{HK,0}(f;R):={\sum }_{\mathrm{\varnothing }\mathrm{\ne }u\subseteq \{1,\dots ,d\}}{V}_V(f_{u,0,R};{\prod }_{j\in u}[a_j,b_j]),$ with value $+\mathrm{\infty }$ if any summand is infinite. Write $V_{HK,0}(f):=V_{HK,0}(f;[0,1{]}^d)$. The lower anchor fixes every complementary coordinate at the lower endpoint of $R$; this auxiliary convention is distinct from the upper anchor used in Hardy–Krause variation anchored at the upper corner.

Inputs: a dimension $d\ge 1$, a function $f:[0,1{]}^d\to \mathbb{R}$ that is finite at each generated node, and exactly one of the following point-set specifications:

1. Digital branch: a prime $p$, an integer $m\ge 1$, and matrices $C_1,\dots ,C_d\in {\mathbb{F}}_p^{m\times m}$. Optionally supply an integer $t$ with $0\le t\le m$ when the caller also wants the exact $(t,m,d)$-net property checked.
2. General lattice-rule branch: a full-rank discrete additive subgroup $L\subset {\mathbb{R}}^d$ containing ${\mathbb{Z}}^d$, with finite quotient $L\mathrm{/}{\mathbb{Z}}^d$, and a supplied complete list $P$ of the distinct coset representatives in $[0,1{)}^d$.
3. Rank-one lattice branch: an integer $N\ge 1$ and $z=(z_1,\dots ,z_d)\in {\mathbb{Z}}^d$ with $\gcd (z_1,N)=1$, where $\gcd$ has the convention of Common divisor, and the greatest common divisor $\gcd (a,b)$, with the convention $\gcd (0,0):=0$.

Outputs: The ordered point list $P$, the finite node average $A_P(f)$, and, when $t$ is supplied in the digital branch, the net-count check result.

A lattice rule means the equal-weight rule on the representatives of an integration lattice $L$ as in branch 2; its node count is $N=\mathrm{\mid }L\mathrm{/}{\mathbb{Z}}^d\mathrm{\mid }$. Branch 3 specifies the rank-one fractional-part construction.

Instructions:

1. In the digital branch, for each $n=0,\dots ,p^m-1$, write $n={\sum }_{r=1}^m{n}_{r-1}{p}^{r-1}$, form $v(n)=(n_0,\dots ,n_{m-1}{)}^T\in {\mathbb{F}}_p^m$, and compute $y^{(j)}=C_{j}v(n)$ in ${\mathbb{F}}_p^m$. Replace each coordinate $y_r^{(j)}$ by its representative in $\{0,\dots ,p-1\}$ and set $x_{n,j}={\sum }_{r=1}^m{y}_r^{(j)}{p}^{-r}$. The output point list is $P=(x_0,\dots ,x_{p^m-1})$. If $t$ was supplied, enumerate every integer tuple $k_1,\dots ,k_d\ge 0$ with ${\sum }_j{k}_j=m-t$ and every tuple $a_j\in \{0,\dots ,p^{k_j}-1\}$; count the output nodes in each corresponding elementary interval. Return “net check passed” exactly when every count equals $p^t$, and otherwise return “not a $(t,m,d)$-net.”
2. In the general lattice-rule branch, take the supplied complete list $P$ of representatives; do not add further points or repeat any coset representative.
3. In the rank-one lattice branch, for each $n=0,\dots ,N-1$, set $x_{n,j}=\{n{z}_j\mathrm{/}N\}$ for $j=1,\dots ,d$, where $\{a\}:=a-\lfloor a\rfloor \in [0,1)$ and $\lfloor a\rfloor$ is the integer part from Integer part: for every real $x$ there is exactly one integer $m$ with $m\le x<m+1$. The output point list is $P=(x_0,\dots ,x_{N-1})$.
4. In each branch, let $N$ be the output list length and return the finite node average $A_P(f):=N^{-1}{\sum }_{n=0}^{N-1}f(x_n)$ together with $P$. In the digital branch $N=p^m$; in the general lattice branch $N=\mathrm{\mid }L\mathrm{/}{\mathbb{Z}}^d\mathrm{\mid }$. When $f$ is bounded and Riemann integrable, $A_P(f)=Q_P(f)$ and its target is the cube integral $I_d(f)$ of Star discrepancy, digital nets, and digital sequences. For other admissible inputs the finite average is still defined, but no cube-integral target is asserted. The algorithm does not estimate a discrepancy, a variation, or a sampling variance, and a generated digital point set has no claimed net quality unless the optional count check passes.

Let $d\ge 1$ and let $f:[0,1{]}^d\to \mathbb{R}$ be the continuous extension to the closed cube of a function on $(0,1{)}^d$ whose mixed partial derivatives of every order at most $d$ exist and extend continuously to $[0,1{]}^d$. This is the $C^d$ hypothesis here, including agreement of the boundary values of $f$ with its order-zero extension. For $u=\{j_1<\cdots <j_q\}$, write ${\mathrm{\partial }}_{u}f$ for the iterated derivative ${\mathrm{\partial }}_{j_q}\cdots {\mathrm{\partial }}_{j_1}f$, interpreted on the closed cube by its continuous extension. For each nonempty $u$, let $f_u(x_u)=f(x_u;1_{-u})$ be the restriction to the face adjacent to the upper corner. Then $V_{HK,1}(f)={\sum }_{\mathrm{\varnothing }\mathrm{\ne }u\subseteq \{1,\dots ,d\}}{\int }_{[0,1{]}^{\mathrm{\mid }u\mathrm{\mid }}}\mid {\mathrm{\partial }}_{u}f(x_u;1_{-u})\mid d{x}_u,$ where $V_{HK,1}$ is the upper-anchor variation of Hardy–Krause variation anchored at the upper corner, and ${\mathrm{\partial }}_u$ differentiates once in each coordinate in $u$.

Let $N\ge 1$, let $P=(x_0,\dots ,x_{N-1})$ be a point multiset in $[0,1{)}^d$, and let $f:[0,1{]}^d\to \mathbb{R}$ have finite upper-anchor Hardy–Krause variation. This finiteness implies that $f$ is bounded and Riemann integrable by Finite Hardy–Krause variation implies bounded Riemann integrability, so $Q_P(f)$ is defined. Let $G$ be a finite coordinate grid containing every coordinate of every point of $P$, with knots $0=t_{j,0}<\cdots <t_{j,m_j}=1$. Its lower-corner Riemann sum is $C_k:={\prod }_{j=1}^d[t_{j,k_j},t_{j,k_j+1}],S_G(f):={\sum }_{0\le k_j<m_j}f(t_{1,k_1},\dots ,t_{d,k_d})\mathrm{vol}(C_k),$ where the cells and volume convention are those of Grid partitions of a rectangle in ${\mathbb{R}}^m$, their cells, refinements and mesh and Axis-parallel rectangles in ${\mathbb{R}}^m$ and their volume, and $S_G$ is the lower-corner tagged Riemann sum of Tagged grid partitions and Riemann sums in ${\mathbb{R}}^m$. Then $\mid Q_P(f)-S_G(f)\mid \le D_N^{\ast }(P)V_{HK,1}(f)$, with the quadrature and star discrepancy of Star discrepancy, digital nets, and digital sequences and the variation of Hardy–Krause variation anchored at the upper corner.

Let $(x_n{)}_{n\ge 0}$ be any sequence in $[0,1{)}^d$ such that $D_N^{\ast }(x_0,\dots ,x_{N-1})⟶0(N\to \mathrm{\infty })\mathrm{.}$ Then for every bounded Riemann-integrable $f:[0,1{]}^d\to \mathbb{R}$, $\frac{1}{N}{\sum }_{n=0}^{N-1}f(x_n)⟶I_d(f)\mathrm{.}$ Here $D_N^{\ast }$ and $I_d$ have the conventions of Star discrepancy, digital nets, and digital sequences.

Let $d\ge 1$ and let $f:[0,1{]}^d\to \mathbb{R}$ have finite upper-anchor Hardy–Krause variation $V_{HK,1}(f)$ as defined in Hardy–Krause variation anchored at the upper corner. Then $f$ is bounded and Riemann integrable on $[0,1{]}^d$.