9/30/2015
`
`Quasi-random sequences
`
`John D. Cook
`
`Navigation
`
`Singular Value Consulting
`
`Quasi-random sequences in art
`and integration
`
`Posted on 16 March 2009 byjohn
`
`Sometimes when people say they want random points, that's not what they
`
`really want. Random points clump more than most people expect. Quasi-
`
`random sequences are not random in any mathematical sense, but they
`
`might match popular expectations of randomness better than the real thing,
`
`especially for aesthetic applications. If by ”random” someone means
`
`"scattered around without a clear pattern and not clumped together" then
`
`quasi-random sequences might do the trick.
`
`Here are the first 50 points in a quasi-random sequence of points in the unit
`
`square.
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 1/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`0.3
`
`UJ5
`
`n.4
`
`0.2
`
`"
`
`Q
`
`_
`
`|
`
`,
`
`II
`
`
`
`By contrast, here are 50 points in a unit square whose coordinates are
`
`uniform random samples.
`
`'
`
`I
`
`o
`
`I
`
`I.
`
`in
`
`'
`
`I
`
`_
`:-
`
`_
`
`I
`
`.0
`
`‘I
`
`'
`
`'
`
`'
`
`1'
`
`an
`
`.
`
`-
`
`I
`
`,
`
`'
`
`'
`
`-
`
`"‘
`;
`
`I
`
`-I
`
`II
`
`in
`
`II
`
`II
`
`in
`
`in
`
`in
`
`II
`
`an
`
`0.3
`
`..
`
`I
`
`I2I.I5
`
`u_4
`
`|I|.2
`
`un
`
`_
`
`.
`
`The truly random points clump together. Notice the cluster of three points in
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 2/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`the top right corner. There are few other instances of pairs of points being
`
`very close together. Also, there are fairly large areas that don't contain any
`
`random points. The quasi-random points by contrast are better spread out.
`
`They have a se|f—avoiding property that keeps them from clustering, and they
`
`fill the space more efficiently.
`
`Quasi-random sequences could be confused with pseudo-random sequences.
`
`They're not at all the same thing. Pseudo—random sequences are computer-
`
`generated sequences that in many ways behave as if they were truly random,
`
`even though they were produced by deterministic algorithms. For many
`
`practical purposes, including sensitive statistical tests, pseudo-random
`
`sequences are simply random sequences. (The "truly" random points above
`
`were technically "pseudo-random" points.)
`
`The quasi-random points above were part ofa Sobol sequence, a common
`
`quasi-random sequence. Other quasi-random sequences include the Halton
`
`sequence and the Hammersley sequence. Mathematically, these sequences
`
`are defined has having low—discrepancy. Roughly speaking, this means the
`
`”discrepancy" between the number of points that actually fall in a volume and
`
`the number of points you'd expect to fall in the same volume is small. See the
`
`Wikipedia article on quasi-random sequences for more mathematical details.
`
`Besides being aesthetically useful, quasi-random sequences are useful in
`
`applied mathematics. Because these sequences explore a space more
`
`efficiently than random sequences, quasi-random sequences sometimes lead
`
`to more efficient high-dimensional integration algorithms than Monte Carlo
`
`integration. Quasi-Monte Carlo integration, i.e. integration based on quasi-
`
`random sequences rather than random sequences, is popular in financial
`
`applications. Art Owen has written insightful papers on Quasi-Monte Carlo
`
`integration (QMC). He has classified which integration problems can be
`
`efficiently computed via QMC methods and which cannot. In a nutshell, QMC
`
`works well when the effective dimension ofa problem is significantly lower
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 3/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`than the actual dimension. For example, a financial model might ostensibly
`
`depend on ‘I000 variables, but 50 of those variables contribute far more to
`
`the integrand than all the other variables. The integrand might essentially be
`
`a function of only 50 variables. In that case, QMC will work well. Note that it is
`
`not necessary to identify these 50 variables or do any change of variables.
`
`QMCjust magically takes advantage of the situation.
`
`One disadvantage of QMC integration is that it doesn't naturally lead to an
`
`estimate of its own accuracy, unlike Monte Carlo integration. Several hybrid
`
`approaches have been proposed to combine QMC integration and Monte
`
`Carlo integration to get the efficiency of the former and the error estimates of
`
`the latter. For example, one could randomlyjitter the quasi-random points or
`
`randomly permute their components. Some of these results are in Art Owen's
`
`papers.
`
`To read more about quasi-random sequences, see the book Random Number
`
`Generation and Quasi—Monte Carlo Methods.
`
`Categories: Math
`
`Tags:
`
`Integration
`
`Math
`
`Bookmark the
`
`permalink
`
`Previous Post
`
`What happened to XSLT?
`
`Next Post
`PGS EX
`it 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 4/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`Two perspectives on the design of C++
`
`11 thoughts on “Quasi-random
`sequences in art and integration”
`
`Thomas Guest
`
`17 March 2009 at 02:30
`
`Thanks for this fascinating summary, John. Without really
`
`knowing it, I've been aiming for some quasi-random aesthetic
`
`effects. See the graphics here, for example, which I created by
`
`programatically nudging coordinates away from grid squares
`
`(using a random number generator). Maybe I should use a
`
`proper quasi-random sequence?
`
`jason Dyer
`
`17 March 2009 at 17:25
`
`Here's a fun post from a different biog (see the second
`
`footnote) which mentions trying to fill a screen with a flawed
`
`random number generator on the IBM PCJr:
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 5/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`http://www.wurb.com/stack/a rchives/530
`
`Mark De wing
`
`17 March 2009 at 22:26
`
`Here's a presentation from Ken Hanson describing other
`
`methods for generating sets of points. It starts off with digital
`
`halftoning algorithms and moves on from there.
`
`CogitoErgoCogitosum
`
`13 April 2010 at 12:52
`
`Can we assess the quality / validity of the conclusions drawn
`
`from all laboratory experiments performed to date, which
`
`relied on a version of randomness, if we decide now that the
`
`randomness they used wasnt good enough? Exactly how does
`
`this new realization of quasi-randomness and the long
`
`established use of pseudo—randomness reflect / affect the
`
`quality of experimentation and the validity of its conclusions?
`
`Is it fair to look back on the history of science with doubtful
`
`contemplation?
`
`PGS Exhibit 2012
`http://www.johndcook.com/blog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 6/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`CogitoErgoCogitosum
`
`13 April 2010 at 18:56
`
`Here is another question for you... a good one...
`
`You say that there is a distinct difference between “true"
`
`randomness and what humans ‘’feel’’ to be random. The latter
`
`being described as “quasi—random".
`
`Is it possible, then, to analyse a seemingly random set of data...
`II
`
`and discern how random it is. To assess, based on "c|umpage
`
`and lack of “c|umpage", and decide whether or not the event
`
`truly was random... or if a human being tried to make it look
`
`random.
`
`john
`
`13 April 2010 at 19:09 L
`
`There are goodness of fit tests that will distinguish quasi-
`
`random sequences from random sequences.
`
`CogitoErgoCogitosum
`
`15 April 2010 at 15:00
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 7/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`Another realization I had. How do we know that quasi-random
`
`is merely appealing to human senses. How do we know that it
`
`isnt more true to randomness than what you deem "random”?
`
`These pictures with the dots... they were generated on a
`
`computer, right? The regular "random” one wasnt truly random
`
`to begin with... it was pseudo-random, generated by a
`
`computer.
`
`My observation isjust that, which we deem random and which
`
`quasi-random is arbitrary, isnt it?
`
`Could it be that the inherent ”c|umpiness” of "random” events
`
`is in fact the inherent pattern to be found in all pseudo-
`
`random generating algorithms? And that the unappealing
`
`nature of pseudo-random "randomness” is a legitimate
`
`concern?
`
`Of course Im not suggesting that quasi-random is any less
`
`pseudo-random on a computer, but perhaps the algorithm has
`
`been adjusted, the outcomes modified, to be truer to actual
`
`random than you would like to believe. You presume that
`
`quasi-random only ''looks’’ more random, and that clumpiness
`
`is actual random. But Im wondering if you have it right, if you
`
`just dont have too much faith in the computer.
`
`PGS Exhibit 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 8/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`john
`
`15 April 2010 at 16:00 L
`
`Quasi-random sequences have aesthetic applications, but they
`
`can be objectively defined by their mathematical properties.
`
`For this reason they are sometimes called ”low discrepancy
`
`sequences" where "discrepancy" has a technical definition.
`
`Rick Wicklin
`
`27 October 2011 at 13:31
`
`I reached similar conclusions, not in art or integration, but on
`
`the theatrical stage. Turns out that when directors tell cast
`
`members to "go to a random position” on stage, they really
`
`mean "go to a quasi-random position." For details, see
`
`http://b|ogs.sas.com/content/iml/2011/O1/28/random-uniform-
`
`versus—uniform|y-spaced—applying—statistics—to—show—choir/
`
`Pingback: Something like a random sequence but |John D.
`
`Cook
`
`Pingback: Three surprises with the trapezoid rule | John D.
`
`__
`PGS Exh1b1t 2012
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 1) 9/13
`
`Cook
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`Leave a Reply
`Your email address will not be published. Required fields are marked
`*
`
`Name *
`
`Email *
`
`Website
`
`Comment
`
`Notify me of followup comments via e—mail
`
`PGS Exhibit 2012
`http://www.johndcook.com/blog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR201 5-003 09 3 10 3 1 D10/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`
`
`Subscribe to my newsletter
`
`Email Address
`
`1
`
`Latest Posts
`
`The academic cocoon
`
`Doubly and triply periodic functions
`
`Taking away a damaging tool
`
`Julia for Python programmers
`
`Nicholas Higham on Mathematics in Color
`
`PGS Exhibit 2012
`categones
`http://www.johndcook.com/blog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR2015_00309 3 10 3 1 D11/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`Select Category
`
`Archives
`
`Select Month
`
`Tags
`
`V
`
`V
`
`Bayesian Biostatistics BOOKS Business C++ Cancer Clinical trials
`
`Computational statistics
`
`Differential equations Economics
`
`Education Emacs Functional programming Geodesy Graphics History HTML
`
`Integration Interview LaTeX Math MS Office Music Number theory
`
`Perl PowerShel| Probability and Statistics
`
`Productivity Programming Python Quality
`
`Quotes Regular expressions Reproducibility Rstats Science SciPy
`
`Simplicity Special functions SymPy Twitter Typography Unicode Windows
`
`Subscribe by email
`
`Subscribe by R55
`
`
`
`http://www.johndcook.com/biog/2009/03/16/quasi-random-sequences-in-art-and-integration{)VeSternGeCO V PGS (IPR201 5-003 09 3 0 31 D12/13
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)
`
`

`
`9/30/2015
`
`Quasi-random sequences
`
`http://www.johndcook.com/blog/2009/03/16/quasi-random -sequences-i n-art-
`
`and-integratio
`
`PGS Exhibit 201213/13
`nWesternGeco V. PGS (IPR2015-00309, 310, 311)
`
`PGS Exhibit 2012
`WesternGeco v. PGS (IPR2015-00309, 310, 311)