Transcript Quasi-Random Sequences and Their Discrepancies

Quasi-Random Sequences and Their
Discrepancies
Author: William J. Morokoff & Russel E. Caflisch
Presented by Shuaiyuan Zhou
Oct-16-2009
 Monte Carlo Integration
 Quasi-Random Sequences and their Discrepancy
 Koksma-Hlawka inequality
 Wozmiakowski identity
 Low discrepancy sequences
 L2 discrepancy
 Orthogonal projections
 Computational speed
Monte Carlo integration
 In mathematics, Monte Carlo integration is numerical
integration using random numbers.
 When we evaluate the integral of a function, f(x), in the s-
dimensional unit cube, Is, we are in fact calculating the
average of the function at a set of randomly sampled points.
 The accuracy of Monte Carlo integration lies in the selection
of the sequence of points {xn}.
 Random sequences
 Quasi-random sequences (low discrepancy sequences)
Quasi-random sequences
 Sequences with good uniformity properties
 Uniformity of a sequence is measured by its discrepancy: the
error in representation of the volume of subsets of the unit
cube by the fraction of points in the subsets.
Discrepancy
 For a set of J in Is and a sequence of N points {xn} in Is,
define
 If E is the set of all subrectangles of Is and E* is the set of all
subrectangles with one corner at 0, then discrepancies and
star discrepancies are defined as

norm:
L2 norm:
Properties of discrepancy
1.
 with probability 1, for any dimension s. size of discrepancy.
 This bound can be improved !!
2.
 This is regarded as the best bound. Quasi-random sequences with this property
are presented below.
3.
 E* is a subset of E, while any set in E can be written as a combination of 2s sets
in E*.
4.

nomrs are larger than L2 norms.
Koksma-Hlawka inequality
 Use discrepancy as an error bound for Monte Carlo integration.
 In one dimension,
 In s-dimension, similarly,
 Define for all k ≤ s and all sets of k integers 1 ≤ i1 < i2 < … < ik ≤ s, V is the
variation and D* is the star discrepancy of the orthogonal projection of the
sequence {xn} on to the appropriate k-dimensional subspace of Is.
Wozmiakowski identity
 Koksma-Hlawka inequality is an over-estimation
 L2 star discrepancy and integration error. The average is taken
with respect to the Brownian sheet measure.
Low discrepancy sequences
 Discrepancy is of size O((logN)s/N).
 Halton
 Sobol’
 Faure
Halton
the constant grows super-exponentially with dimension
Sobol’ & Faure
 For Sobol’ and Faure sequences, bound of discrepancies looks similarly;
with different coefficient of the (logN)sN-1 term.
 Sobol’
 Since t is a function of s, so the constant grows super-exponentially with
s
 Faure
 CsF is smaller than both CsS and CsH, and it goes to zero as dimension
increases while the other go to infinity.
 Faure sequence is superior.
Is this discrepancy bound good
enough?
 1.Discrepancy for a uniform sequence decreases as N increases;
however, the bound has the maximum when N = es.
This means that we can use the bound as a measure of
performance only after its maximum has been attained. Thus, in
high dimensions, a very large number of points is need.

 2. Terms other than the leading order one can not be neglected.
 3. Even in lower dimension, such as 4 and 16, the discrepancy
bound is not accurate.
L2 discrepancy
 Calculation formula for TN and TN *:
 TN* > TN for all sequences and all N. The qualitative behavior
of the two descrepancies is similar for large N, but TN is
smoother and has a shorter, less extreme, transient region.
 Disadvantage of using TN: no direct connection has been
established between it and integration error.
 However, computation of TN indicates that it is a useful gauge
of integration error convergence as a function of N.
 Some features about TN:
 1. When N is large enough, TN should have a local minimum
 2. In high dimensions, unless one uses a very large number of
points, TN is of size N-1.
 3. The value of TN is insensitive to where the sequence
begins.
Orthogonal projections
 Look at two-dimensional orthogonal projections of the points
in Is.
 Choosing different dimension, the result might be quite
different.
 How to improve?
 Scrambling procedure proposed by Braaten and Weller.
 For example, if N points in Is were required, then s sequences
of N random numbers were generated and sorted from
smallest to largest. This mapping of original position in the
sequence to final position was then used to permute the
sequence.
Computational speed
 Computation time is approximately proportional to
dimension and to number of points used.
 Sobol’ is faster than Halton.
 Sobol’ and Halton is faster than Faure.
Thank you !