Deterministic quasi-Monte Carlo and discrepancy — Examples

1 · Prerequisites

2 · Summary

Summary

These examples check the Koksma–Hlawka bound on a smooth integrand, show an integrable inverse-CDF transform whose endpoint singularity has infinite variation, and separate good one-coordinate projections from joint net quality. A final example distinguishes the arbitrary point counts allowed for quadrature and lattice rules from the power-of-base sizes required of digital nets.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Uniform coordinate projections can hide a poor joint projection

Example

Use the four-node rank-one lattice rule in dimension two with $N = 4$ and $z = (1, 1)$ . Both one-coordinate projections are the equally spaced set ${0, 1 / 4, 1 / 2, 3 / 4}$ , but the two-coordinate set lies on the diagonal. It is not a $(0, 2, 2)$ -net in base $2$ , and its star discrepancy is at least $1 / 4$ .

Facts & Assumptions

Given: Dimension $d = 2$ , node count $N = 4$ , and rank-one lattice generator $z = (1, 1)$ .

[F1]

The rank-one lattice rule uses nodes $x_{n, j} = {n z_{j} / N}$ for $n = 0, \dots, N - 1$ , with ${a} = a - ⌊ a ⌋$ . (Digital point-set and rank-one lattice cube quadrature)

[F2]

A $(t, m, d)$ -net in base $b$ has $b^{m}$ points and each elementary interval with exponent sum $m - t$ contains exactly $b^{t}$ points; $D_{N}^{*}$ is the supremum of anchored-box count error. (Star discrepancy, digital nets, and digital sequences)

[F3]

The rank-one input is admissible: $1$ is a common divisor of $1$ and $4$ , and every common divisor $d$ satisfies $d \leq ∣ 1 ∣ = 1$ by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ; hence $\gcd (1, 4) = 1$ by Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ .

Proof

1.1F1F3givenalgebra

By [F1] and [F3], the nodes are $P = {(0, 0), (1 / 4, 1 / 4), (1 / 2, 1 / 2), (3 / 4, 3 / 4)}$ . Each coordinate projection has one point in each base- $2$ interval of length $1 / 4$ , so each is a $(0, 2, 1)$ -net.

2.1F2step 1.1

The elementary interval $E = [0, 1 / 2) \times [0, 1 / 2)$ has volume $1 / 4$ and contains $(0, 0)$ and $(1 / 4, 1 / 4)$ , hence two points. A $(0, 2, 2)$ -net would require exactly $2^{0} = 1$ point in every such interval, so $P$ is not one.

3.1F2step 1.1algebra∎

At $u = (1 / 2, 1 / 2)$ , the anchored box contains $2$ of the $4$ nodes, so its empirical proportion is $1 / 2$ while its volume is $1 / 4$ . Thus $D_{4}^{*} (P) \geq ∣ 1 / 2 - 1 / 4 ∣ = 1 / 4$ .

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Digital net sizes are powers of their base

Example

In base $2$ , a digital $(t, m, d)$ -net has exactly $2^{m}$ nodes, so six nodes cannot form one. A six-node rank-one lattice rule is still a valid deterministic quadrature rule, and the Koksma–Hlawka inequality is stated for arbitrary finite nonempty point sets rather than only digital-net sizes.

Facts & Assumptions

Given: Base $2$ , dimension $d = 2$ , and node count $N = 6$ .

[F1]

A $(t, m, d)$ -net in base $b$ has exactly $b^{m}$ nodes. (Star discrepancy, digital nets, and digital sequences)

[F2]

A rank-one lattice rule accepts any integer $N \geq 1$ and a generator $z$ with $\gcd (z_{1}, N) = 1$ , and uses nodes $x_{n, j} = {n z_{j} / N}$ . (Digital point-set and rank-one lattice cube quadrature)

[F3]

Koksma–Hlawka is stated for any finite nonempty point multiset and integrand of finite upper-anchor Hardy–Krause variation. (Koksma–Hlawka integration bound with upper-anchor variation)

[F4]

Since $2 > 1$ , $m \mapsto 2^{m}$ is strictly increasing on the natural exponents, by the monotonicity-in-the-exponent clause of Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$ . The rank-one input with $z_{1} = 1$ and $N = 6$ is admissible: $1$ is a common divisor of $1$ and $6$ , and every common divisor $d$ satisfies $d \leq ∣ 1 ∣ = 1$ by If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ , so $\gcd (1, 6) = 1$ by Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ .

Verification

technique · direct

1.1F1F4givenalgebra

The positive integer powers of $2$ are $1, 2, 4, 8, \dots$ : by [F4], if $m \leq 2$ then $2^{m} \leq 2^{2} = 4$ , while if $m \geq 3$ then $2^{m} \geq 2^{3} = 8$ . Hence no integer $m \geq 0$ gives $2^{m} = 6$ , so [F1] rules out a base- $2$ digital net with six nodes.

1.2F2F4givenalgebra

With $N = 6$ and $z = (1, 1)$ , [F2] and [F4] generate six nodes; the first coordinate is $n / 6$ for $n = 0, \dots, 5$ , so the nodes are distinct and the lattice-rule inputs are admissible.

2.1F1F3step 1.1step 1.2∎

The star discrepancy and the Koksma–Hlawka statement are defined for this six-node point set even though its size is not a power of $2$ . Thus a finite deterministic quadrature rule exists at this size, while the digital-net label and its elementary-interval guarantee do not apply.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A smooth finite-variation integrand and its deterministic error bound

Example

On $[0, 1]^{2}$ , take $f (x, y) = x y$ and the one-point set $P = ((1 / 4, 1 / 2))$ . Then $V_{H K, 1} (f) = 3, D_{1}^{*} (P) = \frac{7}{8}, ∣ Q_{P} (f) - I_{2} (f) ∣ = \frac{1}{8},$ so the Koksma–Hlawka bound is valid for this smooth integrand.

Facts & Assumptions

Given: The function $f (x, y) = x y$ on the unit square and the point set containing $(1 / 4, 1 / 2)$ .

[F1]

For $C^{d}$ functions, upper-anchor Hardy–Krause variation is the sum of the integrals of the absolute mixed derivatives on all nonempty upper faces. (Mixed-derivative formula for smooth Hardy–Krause variation)

[F2]

The unit square has volume $1$ ; grid cells' volumes sum to that volume, and for the constant-one function every lower and upper Darboux sum equals the sum of the cell volumes, so its integral is $1$ . (Axis-parallel rectangles in $R^{m}$ and their volume, Grid partitions of a rectangle in $R^{m}$ , their cells, refinements and mesh, Lower and upper Darboux sums over a grid partition in $R^{m}$ , The lower and upper Darboux integrals over a nondegenerate rectangle in $R^{m}$ )

[F3]

A continuous function on the square is Riemann integrable, and its integrable sections have iterated integrals equal to the multiple integral. (Every continuous function on a closed nondegenerate rectangle in $R^{m}$ is Riemann integrable, Riemann--Fubini on product rectangles, with lower and upper section integrals and content-zero exceptional sections)

[F4]

Star discrepancy is the supremum over $u \in [0, 1]^{d}$ of the absolute difference between the fraction of nodes in $[0, u)$ and its volume. (Star discrepancy, digital nets, and digital sequences)

[F5]

If $G$ is continuous on $[a, b]$ , differentiable on $(a, b)$ , and its interior derivative has a Riemann-integrable extension, then its integral is $G (b) - G (a)$ . (Newton–Leibniz needs only continuity on $[a, b]$ , differentiability on $(a, b)$ , and a Riemann-integrable extension of the interior derivative)

[F6]

For a finite nonempty point multiset and an integrand of finite upper-anchor Hardy–Krause variation, $∣ Q_{P} (f) - I_{d} (f) ∣ \leq D_{N}^{*} (P) V_{H K, 1} (f)$ . (Koksma–Hlawka integration bound with upper-anchor variation)

Verification

technique · direct

1.1F1F2givenalgebra

The upper faces are $f (x, 1) = x$ and $f (1, y) = y$ , and the full mixed derivative is $\partial_{x y} f = 1$ . By [F1], $V_{H K, 1} (f) = \int_{0}^{1} 1 d x + \int_{0}^{1} 1 d y + \int_{[0, 1]^{2}} 1 d x d y = 1 + 1 + 1 = 3$ ; the one-dimensional integrals and the square integral of $1$ equal the respective volumes by [F2].

1.2F3F4F5givenalgebra

At $u = (1 / 4, 1 / 2)$ the point is excluded from the half-open anchored box, so the discrepancy there is $1 / 8$ . If $u_{1} \leq 1 / 4$ or $u_{2} \leq 1 / 2$ , the box is empty and its volume is at most $1 / 2$ . If both coordinates exceed those thresholds, the box contains the point and its error is $1 - u_{1} u_{2} \leq 1 - (1 / 4) (1 / 2) = 7 / 8$ ; values approach $7 / 8$ as $u ↓ (1 / 4, 1 / 2)$ . Thus $D_{1}^{*} (P) = 7 / 8$ . Also $Q_{P} (f) = 1 / 8$ . By [F3], the double integral equals the iterated Riemann integral, and [F5] evaluates it as $I_{2} (f) = \int_{0}^{1} y (\int_{0}^{1} x d x) d y = 1 / 4$ .

2.1F6step 1.1step 1.2∎

The error is $∣ 1 / 8 - 1 / 4 ∣ = 1 / 8 \leq (7 / 8) \cdot 3 = D_{1}^{*} (P) V_{H K, 1} (f)$ , consistent with [F6].

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

An inverse-CDF singularity can be integrable but have infinite variation

Example

Let $U$ have the uniform law on $[0, 1)$ and define $g (u) = (1 - u)^{- 1 / 2}$ for $0 \leq u < 1$ . Extend $g$ to the closed cube by setting $g (1) = 0$ ; this endpoint convention does not change $g (U)$ . The map $g$ has distribution function $F_{X} (x) = 0$ for $x < 1$ and $F_{X} (x) = 1 - x^{- 2}$ for $x \geq 1$ , and satisfies $F_{X} (g (u)) = u$ for all $0 \leq u < 1$ (the inverse-CDF property in this example). Its expectation is finite, but $V_{H K, 1} (g) = \infty$ , so the Koksma–Hlawka bound gives no finite error guarantee for this integrand.

Facts & Assumptions

Given: A real random variable $U$ with the uniform probability law on $[0, 1)$ , represented by the identity map on $([0, 1), B ([0, 1)), P_{U})$ .

[A1]

For $0 \leq a < 1$ , $P_{U} (U \leq a) = a$ ; thus $P_{U} (U > a) = 1 - a$ .

[F1]

A real random variable is a measurable map into $R$ with its Borel sigma-algebra. (Random elements and real random variables, The Borel sigma-algebra of a topological space)

[F2]

A map between measurable spaces is measurable when the preimage of every measurable target set is measurable. (A measurable function between measurable spaces)

[F3]

The half-lines $(- \infty, x]$ generate the Borel sigma-algebra of $R$ . (Seven generating families for the Borel sigma-algebra on the real line)

[F4]

A measurable function composed with a random element is measurable. (Composition with a Borel measurable outer map preserves measurability)

[F5]

The cumulative distribution function of a real random variable is $F_{X} (x) = P (X \leq x)$ . (Cumulative distribution function of a real random variable)

[F6]

For $a > 0$ , $a^{- 1 / 2} = 1 / \sqrt{a}$ , the square root is the unique nonnegative root, squaring preserves nonstrict order on nonnegative reals, and taking reciprocals reverses positive order; the equality case follows from trichotomy. (Rational powers $a^{r}$ of a positive base, Laws of rational exponents, Square roots exist: a unique $\sqrt{a} \geq 0$ with $(\sqrt{a})^{2} = a$ ; the positives are ${x^{2} : x \neq 0}$ , Squaring is monotone on the nonnegatives, Inverses of positives are positive, and reciprocation reverses order, Ordered field)

[F7]

For every positive integer $n$ , $0 < (1 / 2)^{n} < 1$ , and $(1 / 2)^{n} \to 0$ . (Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$ , For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ )

[F8]

The expectation of a nonnegative random variable is its extended Lebesgue integral. (Expectation of a nonnegative or integrable random variable)

[F9]

For a measurable $h \geq 0$ , $E [h (U)] = \int h d P_{U}$ . (Change of variables for expectation)

[F10]

For nonnegative $X$ , $E [X] = \int_{0}^{\infty} P (X > t) d t$ . (Layer-cake formulas for random variables)

[F11]

For rational $p > 1$ , $\int_{1}^{\infty} t^{- p} d t = 1 / (p - 1)$ . (The improper $p$ -test for rational exponents)

[F12]

In dimension one, upper-anchor Hardy–Krause variation is ordinary total variation. (Hardy–Krause variation anchored at the upper corner)

[F13]

Koksma–Hlawka applies to a finite nonempty point multiset and requires finite upper-anchor Hardy–Krause variation. (Koksma–Hlawka integration bound with upper-anchor variation)

Proof

1.1givenF1F2F3F4F6construct

On $[0, 1)$ define $g (u) = (1 - u)^{- 1 / 2}$ . Since $0 < 1 - u \leq 1$ , [F6] gives $g (u) \geq 1$ . For $x < 1$ , the sublevel set ${u : g (u) \leq x}$ is empty. For $x \geq 1$ , [F6] gives $g (u) \leq x$ exactly when $x^{- 2} \leq 1 - u$ , so this sublevel set is $[0, 1 - x^{- 2}]$ (with the endpoint interpreted inside $[0, 1)$ ). Each such set is Borel. Since the half-lines in [F3] generate the target Borel sigma-algebra and preimages commute with complements and countable unions, [F2] shows that $g$ is measurable. Thus $X : = g (U)$ is a real random variable by [F1] and [F4].

1.2F6F7F12givenchoose

For $n \geq 1$ put $u_{n} = 1 - 2^{- 2 n}$ . By [F7], $0 < u_{n} < 1$ . The unique nonnegative square root of $(2^{- n})^{2}$ is $2^{- n}$ , so [F6] gives $g (u_{n}) = 2^{n}$ . Given $M > 0$ , choose $n$ with $2^{- n} < 2 / (M + 1)$ using [F7]; then $g (u_{n}) > (M + 1) / 2$ . The grid with knots $0 < u_{n} < 1$ has variation at least $∣ g (u_{n}) - g (0) ∣ + ∣ g (1) - g (u_{n}) ∣ = 2 g (u_{n}) - 1 > M$ . Hence $V_{H K, 1} (g) = \infty$ by [F12].

2.1A1F5F6step 1.1algebra

By [F5] and [A1], the distribution function of $X$ is $F_{X} (x) = 0$ for $x < 1$ and $F_{X} (x) = 1 - x^{- 2}$ for $x \geq 1$ . For each $u < 1$ , $F_{X} (g (u)) = 1 - (g (u))^{- 2} = u$ , so $g$ is the inverse-CDF transform on $[0, 1)$ .

2.2A1F6F8F10F11step 1.1

For $0 \leq t < 1$ , $X \geq 1$ gives $P (X > t) = 1$ . For $t \geq 1$ , [F6] gives $X > t$ exactly when $U > 1 - t^{- 2}$ , and [A1] then gives $P (X > t) = t^{- 2}$ . By [F8], [F10], and [F11] with $p = 2$ , $E [X] = \int_{0}^{1} 1 d t + \int_{1}^{\infty} t^{- 2} d t = 1 + 1 = 2$ .

3.1F8F9step 1.1step 2.2

By [F9], change of variables for expectation applied to the measurable nonnegative $g$ and random element $U$ identifies $E [X]$ with $\int g d P_{U}$ . By [F8] and step 2.2 this value is finite and equals $2$ .

4.1F13step 3.1step 1.2∎

The expectation is finite by step 3.1, but the integrand has infinite upper-anchor variation by step 1.2. Therefore the finite-variation hypothesis in [F13] fails, so Koksma–Hlawka yields no finite error bound for this integrand.

Deterministic quasi-Monte Carlo and discrepancy — Examples

1 · Prerequisites

2 · Summary

Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

Uniform coordinate projections can hide a poor joint projection

Example

Facts & Assumptions

Proof

Digital net sizes are powers of their base

Example

Facts & Assumptions

Verification

A smooth finite-variation integrand and its deterministic error bound

Example

Facts & Assumptions

Verification

An inverse-CDF singularity can be integrable but have infinite variation

Example

Facts & Assumptions

Proof

Sources