Randomization methods

RandomizationMethod

Abstract interface for methods that randomize deterministic point sets with randomize.

An implementation must preserve the shape of its input point matrix and keep every point in the unit box. It should provide randomize(points::AbstractMatrix, method) and return a new matrix unless the method is explicitly documented as mutating its input. The randomization must preserve the low-discrepancy properties promised by the concrete method and should use an owned or supplied random-number generator for reproducibility.

Deterministic samplers store their default randomization method in an R field. Pass a method explicitly to randomize when a different randomization is needed for an existing point set.

randomize(x, R::RandomizationMethod)

Apply the randomization method R to a sample matrix x.

Arguments

• x::AbstractMatrix: Matrix with one point per column. Its entries must be in the unit box expected by the selected randomization method.
• R::RandomizationMethod: Randomization strategy to apply.

Returns

• A matrix with the same size as x, with each point randomized according to R. NoRand() returns the original matrix unchanged; other methods return a new matrix unless their method documentation says otherwise.

Examples

julia> using QuasiMonteCarlo

julia> points = sample(4, 2, SobolSample());

julia> randomized = randomize(points, Shift());

julia> size(randomized) == size(points)
true

NoRand() <: RandomizationMethod

Identity randomization for deterministic samplers.

randomize(points, NoRand()) returns points unchanged. It is also the default value of the R field on deterministic sampler types.

Examples

julia> using QuasiMonteCarlo

julia> points = sample(4, 2, SobolSample(R = NoRand()));

julia> randomize(points, NoRand()) === points
true

ScrambleMethod <: RandomizationMethod

A scramble method randomizes a digital net in an integer base.

Interface rules

Concrete subtypes must provide the fields base::Integer, pad::Integer, and rng::AbstractRNG. base must match the base of the sequence being scrambled, and pad must be at least log(base, n) for a point set with n points. The randomize interface preserves the matrix size and keeps points in the unit box.

The package provides DigitalShift, MatousekScramble, and OwenScramble. New implementations should add methods to the generic randomize/randomize! interface rather than changing sampler methods.

Examples

julia> using QuasiMonteCarlo

julia> points = sample(8, 2, FaureSample());

julia> randomized = randomize(points, DigitalShift(base = 2, pad = 4));

julia> size(randomized) == size(points)
true

The scramble methods implementer are

• DigitalShift.
• OwenScramble: Nested Uniform Scramble which was introduced in Owen (1995).
• MatousekScramble: Linear Matrix Scramble which was introduced in Matousek (1998).

DigitalShift(base::Integer; pad = 32, rng = Random.TaskLocalRNG()) <: ScrambleMethod

Digital shift. randomize(x, R::DigitalShift) returns a scrambled version of x.

Fields

• base::Integer: Base of the digital net being scrambled.
• pad::Integer = 32: Number of base-base digits retained for each point.
• rng::AbstractRNG = Random.TaskLocalRNG(): Random-number generator used by the shift.

The scramble method is Digital Shift. It scrambles each coordinate in base b as yₖ = (xₖ + Uₖ) mod b where Uₖ ∼ 𝕌({0:b-1}). U is the same for every point points but i.i.d. along every dimension.

MatousekScramble(base::Integer; pad = 32, rng = Random.TaskLocalRNG()) <: ScrambleMethod

Linear Matrix Scramble, also known as Matousek's scramble.

Fields

• base::Integer: Base of the digital net being scrambled.
• pad::Integer = 32: Number of base-base digits retained for each point.
• rng::AbstractRNG = Random.TaskLocalRNG(): Random-number generator used by the scramble.

randomize(x, R::MatousekScramble) returns a scrambled version of x. The scramble method is Linear Matrix Scramble which was introduced in Matousek (1998). pad is the number of bits used for each point. One needs pad ≥ log(base, n).

References: Matoušek, J. (1998). On thel2-discrepancy for anchored boxes. Journal of Complexity, 14(4), 527-556.

OwenScramble(base::Integer; pad = 32, rng = Random.TaskLocalRNG()) <: ScrambleMethod

Nested Uniform Scramble, also known as Owen's scramble.

Fields

• base::Integer: Base of the digital net being scrambled.
• pad::Integer = 32: Number of base-base digits retained for each point.
• rng::AbstractRNG = Random.TaskLocalRNG(): Random-number generator used by the scramble.

randomize(x, R::OwenScramble) returns a scrambled version of x. The scramble method is Nested Uniform Scramble which was introduced in Owen (1995). pad is the number of bits used for each point. One needs pad ≥ log(base, n).

References: Owen, A. B. (1995). Randomly permuted (t, m, s)-nets and (t, s)-sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing: Proceedings of a conference at the University of Nevada, Las Vegas, Nevada, USA, June 23–25, 1994 (pp. 299-317). Springer New York.

Shift(; rng = Random.TaskLocalRNG()) <: RandomizationMethod

Cranley-Patterson rotation.

Fields

• rng::AbstractRNG = Random.TaskLocalRNG(): Random-number generator used to draw one shift vector for each call to randomize.

Examples

julia> using QuasiMonteCarlo, Random

julia> points = sample(8, 2, SobolSample());

julia> shifted = randomize(points, Shift(rng = MersenneTwister(42)));

julia> size(shifted) == size(points)
true

References: Cranley, R., & Patterson, T. N. (1976). Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis, 13(6), 904-914.