Matpic
mathematics, in pictures
Concept

Pseudorandomness

The property of a sequence produced by a rule that nevertheless passes the statistical tests one would apply to a random one. The tests are always passed by some rules with visible structure, so passing them is evidence about which tests were run rather than about the absence of pattern.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

Points too even to be random. 256 independent random points beside 256 points of a Halton sequence, with the largest mismatch between a box's share of points and its area plotted against the number of points for both.

Points too even to be random

Independent random points clump, and the clumping is what makes the error fall only as the square root. Points chosen to be evenly spread rather than independently beat that rate, and the price is that nothing about them is random at all.

probability · monte carlo A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · de bruijn

Named alongside it

The objects these essays reach for when they reach for this one.

Convergence rateDe bruijn sequenceDiscrepancyDiscrete logarithmEquidistributionError boundFinite fieldGroupIntegralMonte CarloPeriodicityPolynomial

All concepts