Quasi Monte Carlo and effective dimension

Definition Write a model expectation as an integral over the unit cube,

where $f$ composes the discounted payoff with a map from uniform coordinates to the model inputs, for example $u_k \mapsto \Phi^{-1}(u_k)$ in each coordinate to get $d$ independent standard normals, followed by a path construction. For a point set $P_N = \{u_1, \dots, u_N\}$ in $[0,1)^d$, the equal-weight rule is

Plain Monte Carlo uses independent uniform points. Quasi-Monte Carlo uses deterministic points chosen to fill the cube evenly, so its error $Q_N - I$ is a fixed number, not a random variable. The Koksma-Hlawka inequality, stated in the course without proof, says that if $f$ has finite variation $V_{HK}(f)$ in the sense of Hardy and Krause, then for every point set

where $D_N^*$ is the star discrepancy of the next card. In one dimension $V_{HK}(f)$ is the ordinary total variation. The hypothesis is restrictive for financial integrands. An unbounded integrand has infinite variation, and a payoff composed with $\Phi^{-1}$ is often unbounded near the faces of the cube. An indicator of a region whose boundary is not parallel to the coordinate axes, such as a digital payoff on a basket of two assets, also has infinite Hardy-Krause variation in two or more dimensions. Then the bound says nothing, which is not the same as saying that quasi-Monte Carlo fails.

Definition For a point set $P_N = \{u_1, \dots, u_N\}$ in $[0,1)^d$ and a corner $t \in [0,1]^d$, let $A(t)$ be the number of points in the anchored box $[0, t_1) \times \dots \times [0, t_d)$, whose volume is $t_1 t_2 \cdots t_d$. With the local mismatch

the star discrepancy is

It is a number in $[0, 1]$ that depends only on where the points are, not on how they were produced, so it measures coverage and says nothing about independence. In one dimension, with the points sorted as $x_{(1)} \le \dots \le x_{(N)}$,

so $1/(2N)$ is the smallest possible value, attained only by the midpoints. In one dimension it is the Kolmogorov-Smirnov distance between the empirical distribution of the points and the uniform distribution.

Definition An infinite sequence $u_1, u_2, \dots$ in $[0,1)^d$ is a low-discrepancy sequence if there is a constant $C_d$ such that the first $N$ points satisfy

for all $N \ge 2$. The van der Corput sequence in base $2$ mirrors the binary digits of $j$ about the binary point, so $j = 1, 2, 3, 4$, written $1$, $10$, $11$ and $100$ in binary, give $0.1$, $0.01$, $0.11$ and $0.001$ in binary, that is $\tfrac12$, $\tfrac14$, $\tfrac34$ and $\tfrac18$. The Halton sequence uses van der Corput sequences in different prime bases for different coordinates, and Sobol’ sequences are built from base $2$ digit operations. Both satisfy the bound. For independent uniform points the star discrepancy is typically of order $N^{-1/2}$. Combined with the Koksma-Hlawka inequality, an integrand of finite Hardy-Krause variation is integrated with error at most a constant times $(\log N)^d / N$. That beats $N^{-1/2}$ as $N \to \infty$, but for large $d$ the factor $(\log N)^d$ is enormous at practical sizes, so this rate alone does not predict performance in high dimension, and general convergence rates lie beyond this lesson.

Definition A randomization of a point set $P_N$ produces random points $\tilde u_1, \dots, \tilde u_N$ such that each $\tilde u_j$ is uniformly distributed on $[0,1)^d$ while the set keeps an even structure. The simplest is the random shift modulo one, $\tilde u_j = (u_j + \Delta) \bmod 1$ in each coordinate with $\Delta$ uniform on $[0,1)^d$, which leaves the spacing of a grid or lattice unchanged. Scrambling of digital nets is another, whose implementation lies beyond this lesson. For an integrable $f$ each term has expectation $I$, so

is unbiased. The points of one randomized set are dependent, so the $N$ values $f(\tilde u_j)$ cannot be treated as independent draws. Instead take $R \ge 2$ independent randomizations of the same point set, with the same $N$ and the same integrand, and let $Q_N^{(r)}$ be the estimate from the $r$-th one. These replicates are independent and identically distributed with mean $I$. If their variance is finite, the average

has variance $\operatorname{Var}(Q_N^{(1)})/R$, and this variance is estimated without bias by

because the sample variance with divisor $R - 1$ is unbiased for the variance of independent, identically distributed replicates. A Student $t$ interval with $R - 1$ degrees of freedom is exact only for normal replicates and is otherwise an approximation that needs enough replicates. Randomization makes the error measurable while keeping the estimate unbiased, but it does not guarantee one convergence rate for every payoff.

Definition Let $W$ be a standard Brownian motion, $0 = t_0 < t_1 < \dots < t_m = T$ a time grid and $Z_1, \dots, Z_m$ independent standard normals. The chronological construction sets $W_{t_k} = W_{t_{k-1}} + \sqrt{t_k - t_{k-1}}\, Z_k$. The Brownian bridge construction generates $W_T = \sqrt{T}\, Z_1$ first and then fills in interior times by Gaussian conditioning. Suppose $s < u < t$ are grid times, the values $W_s = x$ and $W_t = y$ are already generated, and every other generated value lies at a time outside $(s, t)$. By independent increments, the conditional law of $W_u$ given all generated values is $N(\mu_u, v_u)$ with

and the next coordinate fills it in as $W_u = \mu_u + \sqrt{v_u}\, Z_k$. For the midpoint of $[0, T]$ with $W_0 = 0$ and $W_T = w$, Gaussian conditioning with $\operatorname{Cov}(W_{T/2}, W_T) = T/2$ and $\operatorname{Var}(W_T) = T$ gives the mean $\tfrac{T/2}{T}\, w = w/2$ and the variance $T/2 - (T/2)^2/T = T/4$. On a grid with $m = 2^k$ steps the fill-in goes level by level, the midpoint first, then the quarter points, and so on. Both constructions produce a centered Gaussian vector with covariance $\min(t_i, t_j)$, so they give exactly the same joint law of $(W_{t_1}, \dots, W_{t_m})$, and the same expectation and variance for every square-integrable payoff. They differ only in which coordinate controls which feature of the path.

Definition Let $f$ be square integrable on $[0,1]^d$, with variance $\sigma^2 = \operatorname{Var}(f(U)) > 0$ for $U$ uniform on the cube. The ANOVA decomposition writes $f = \sum_{S} f_S$ over the subsets $S \subseteq \{1, \dots, d\}$, where $f_{\varnothing} = I$ and, for $S \neq \varnothing$, the term $f_S$ depends only on the coordinates in $S$ and integrates to zero over each of them. These terms are orthogonal, so

For a proportion $p$ close to $1$, such as $0.99$, the effective dimension in the truncation sense is the smallest $s$ for which the terms with $\varnothing \neq S \subseteq \{1, \dots, s\}$ carry at least $p\sigma^2$. In the superposition sense it is the smallest $s$ for which the terms with $1 \le \lvert S \rvert \le s$ carry at least $p\sigma^2$. The truncation dimension depends on the order of the coordinates, so it changes when the path is built differently, while the integral does not.