Quasi-Monte Carlo (QMC)

The foundation of QMC is the use of low-discrepancy sequences (LDS) such as Sobol, Halton, and Faure sequences. Unlike pseudo-random numbers, these deterministic points are constructed to fill the integration hypercube more uniformly by minimizing gaps and clustering. The discrepancy of a sequence quantifies the maximum deviation between the empirical distribution of points and the ideal uniform distribution. By achieving a discrepancy of O((log N)^s / N), QMC avoids the random clumping that degrades the convergence of standard Monte Carlo.

Standard Monte Carlo converges at a rate of O(N⁻½) regardless of the problem's dimension, meaning quadrupling the samples only halves the error. QMC achieves a deterministic error bound of approximately O(N⁻¹) for smooth integrands, representing a quadratic speedup. In practice, this means a QMC simulation with 1,000 samples can achieve accuracy comparable to a Monte Carlo simulation with 1,000,000 samples for well-behaved, low-dimensional problems. This efficiency is critical for computationally expensive power flow models.

A practical limitation of pure QMC is the difficulty of obtaining unbiased error estimates, as deterministic sequences lack the central limit theorem's guarantees. Randomized QMC (RQMC) solves this by applying a randomization technique, such as a digital shift or scrambling, to the low-discrepancy sequence. This preserves the uniformity properties of the LDS while creating multiple independent replicates. The variance across these replicates provides a rigorous confidence interval, combining the speed of QMC with the statistical diagnostics of Monte Carlo.

The superiority of QMC over standard Monte Carlo depends heavily on the effective dimension of the integrand. Many high-dimensional problems in finance and engineering have a low effective dimension, meaning most variance is concentrated in a few key variables or low-order interaction terms. QMC excels here because low-discrepancy sequences are exceptionally uniform in low-dimensional projections. Additionally, QMC requires the integrand to have bounded variation in the sense of Hardy and Krause; discontinuous functions, such as those arising from discrete switching in power systems, can degrade performance.

Sobol sequences are the most widely used LDS in practice due to their excellent uniformity properties in high dimensions. They belong to the family of (t, s)-sequences in base 2, constructed using primitive polynomials over the Galois field GF(2) and direction numbers. Each coordinate of a Sobol point is generated by XOR-ing direction numbers based on the binary representation of the index. Modern libraries like SciPy (scipy.stats.qmc) and OpenTURNS provide optimized Sobol generators with property A and A' guarantees, ensuring good two-dimensional projections.

In Probabilistic Power Flow (PPF), QMC is used to sample uncertain inputs—such as wind speed or load demand—to estimate the distribution of bus voltages and line flows. The deterministic nature of QMC ensures that the tails of the input distributions are explored more systematically than with random sampling, leading to more accurate estimates of Conditional Value at Risk (CVaR) and violation probabilities. When combined with Nataf transformation to handle correlated non-normal inputs, QMC provides a robust alternative to Polynomial Chaos Expansion for non-smooth grid models.

The foundational building block of QMC. A low-discrepancy sequence is a deterministic point set designed to fill a hypercube more uniformly than random points. The discrepancy measures the maximum deviation between the empirical distribution of the points and the true uniform distribution. Key properties include:

• Sobol sequences: Optimized for high-dimensional integration with base-2 radical inversion
• Halton sequences: Generated by reversing the digits of integers in coprime bases
• Faure sequences: A permuted generalization of Halton sequences for better high-dimensional uniformity
• Niederreiter sequences: Algebraic constructions achieving optimal asymptotic discrepancy

The theoretical backbone that bounds the QMC integration error. This inequality states that the absolute error of a QMC approximation is bounded by the product of two terms:

• The variation of the integrand (a measure of its smoothness, specifically in the sense of Hardy and Krause)
• The star discrepancy of the point set used This decomposition reveals why QMC excels for smooth functions: the error depends on the deterministic uniformity of the points, not on the probabilistic variance of a random estimator. For functions with bounded variation, the convergence rate is strictly superior to standard Monte Carlo.

A hybrid technique that injects controlled randomness into low-discrepancy sequences to enable practical error estimation. Pure QMC produces a single deterministic estimate with no measure of uncertainty. RQMC solves this by applying a randomized scrambling to the deterministic points, creating multiple independent replicates while preserving the low-discrepancy structure. Common scrambling methods include:

• Owen's nested scrambling: The gold standard, applying random permutations to each digit of the base-b expansion
• Digital shift: A simpler affine transformation modulo one
• Cranley-Patterson rotation: A random shift applied to lattice rules The resulting confidence intervals are typically much narrower than those from standard Monte Carlo.

A critical concept explaining why QMC succeeds in high nominal dimensions. The effective dimension of a function quantifies how many input variables actually drive the output variance. A 100-dimensional problem may have an effective dimension of only 5 if the integrand is dominated by low-order interactions. QMC sequences concentrate their uniformity in the first few dimensions, making them highly efficient for functions with:

• Low truncation dimension: The function can be well-approximated by projecting onto the first few variables
• Low superposition dimension: The function is dominated by low-order ANOVA terms This explains why QMC often outperforms Monte Carlo even in problems with hundreds of nominal dimensions.

The functional analysis framework used to quantify the effective dimension. The Analysis of Variance (ANOVA) decomposition expresses a square-integrable function as a sum of orthogonal components of increasing interaction order:

• f₀: The constant mean term
• fᵢ(xᵢ): First-order effects of individual variables
• fᵢⱼ(xᵢ, xⱼ): Second-order interaction effects
• Higher-order terms for complex interactions The variance contribution of each term is measured by Sobol sensitivity indices. QMC is particularly effective when the total variance is dominated by low-order ANOVA components, as low-discrepancy sequences are designed to integrate these terms with high precision.

An alternative class of deterministic integration methods closely related to QMC. A rank-1 lattice rule generates points using a single generating vector z of integers coprime to the number of points N. The points are defined as:

• xᵢ = {i · z / N} for i = 0, ..., N-1, where {·} denotes the fractional part Lattice rules are particularly effective for periodic integrands and can achieve near-optimal convergence rates when the generating vector is carefully chosen. Korobov filters and component-by-component construction algorithms are used to find good generating vectors. In power flow analysis, lattice rules can be applied to the probabilistic load and generation variables when their distributions are transformed to the unit hypercube.