Matpic
mathematics, in pictures
Theme

Order out of noise — page 1

Random processes that reliably produce the same shape, and the reason that is less mysterious than it looks.
Pascal's triangle mod 2, 32 rows. Only the odd entries are drawn; the pattern that appears is the Sierpiński triangle. Discrete

Pascal's triangle, in two colours

Shade the odd numbers in Pascal's triangle and a fractal appears. Nothing was designed to produce it, and the same shape arrives independently from a completely different construction.

 Ulam's spiral to 900. The integers up to 900 laid out in a square spiral, with the primes marked; they crowd onto diagonal lines. Discrete

The primes on a spiral, and a pattern nobody ordered

Wind the whole numbers outward in a square spiral, mark the primes, and they line up on diagonals. The observation is a hundred years old and there is still no proof it means anything.

 A Galton board after 600 balls. 600 balls fall through 12 rows of pegs, each bouncing left or right at random, and pile up in a bell-shaped heap. Probability

A bell curve assembled out of coin flips

Drop six hundred balls through a board of pegs, each bouncing left or right at random, and they pile up in a shape that can be predicted precisely. Nothing coordinated them.

 120 needles on a lined floor. 120 needles dropped at random across evenly spaced lines; 83 of them cross a line. Probability

Getting pi by dropping needles on the floor

Throw a needle at a lined floor enough times, count how often it crosses a line, and pi falls out. There is no circle anywhere in the experiment.

 When a shared birthday becomes likely. The chance that some pair in a group shares a birthday, against group size. It passes a half at 23 people, where the probability is 50.7%. Probability

Twenty-three people

A room needs 253 people before someone probably shares a birthday with you. It needs 23 before two of them probably share one with each other. The gap between those numbers is the whole problem.

 Six people, and the trio that cannot be avoided. The fifteen pairs among six people, coloured at random. Whatever the colouring, three people are all mutual acquaintances or all mutual strangers — here 1, 2, 5. Discrete

Six people at a party

Among any six people, three are mutual acquaintances or three are mutual strangers. Five is not enough, and the arrangement that saves five is a pentagon. Beyond that the numbers become unknowable.

 Nine walks, and the square root. 9 independent walks of 400 steps, each step one place left or right. The dashed curves are ±√n: the walks stay near them, spill past them, and come back — which is what a typical distance means as opposed to a limit. Probability

A walk that always comes home, until it does not

Step left or right at random, forever, and the walk returns to where it started with certainty. On a grid it also returns. In space it does not, and about a third of walks leave and never come back.

 A rule for moving between 3 states. 3 states drawn as circles with an arrow for every move the rule allows, labelled with its chance; a dashed loop is the chance of staying put. Probability

The rule that forgets where it came from

A walk between a few states, with the next step decided by the current one and nothing else. Run it long enough and the starting point stops mattering — but only when two conditions hold, and both of them have a picture in which they fail.

 One set of sums, two scalings, two different limits. The exact distribution of a sum of n independent copies, scaled two ways. Divided by n it collapses onto the mean; divided by the square root of n it holds a fixed width and settles into a shape. Probability

The average settles and the wobble does not

Two theorems are usually met a page apart and sound as though one is a sharper version of the other. They are the same sums looked at through two different magnifying glasses: divide by the number of them and everything collapses to a point, divide by its square root and a shape appears.

 Time spent on one side of the axis. The exact distribution of the number of steps a 40-step fair walk spends above the axis. It is U-shaped: the extremes are the likeliest outcomes and an even split is the rarest. Probability

Half the time is the rarest answer

In a fair game of many rounds, the fraction of the time one side is ahead is not usually near a half. It is usually near nought or one, and an even split is the single least likely outcome there is.

 One walk at three magnifications, and the shape it is heading for. The same random walk over three windows, each ten times longer than the last and scaled vertically by the square root of ten, so all three look alike. Beside them, the exact distribution of the position after a few step counts, standardised, closing on the bell curve. Probability

The walk that becomes a curve

Shrink the steps of a random walk and it disappears. Shrink them while stretching the time in the right proportion — space by the square root of whatever time is divided by — and something is left behind, which is a curve nobody could draw.

 π(x) against its two estimates, up to 20,000. The ratio of the prime counting function to x over the logarithm of x, and to the logarithmic integral, plotted against x. The first is above one and coming down slowly; the second is close to one throughout. Number

Counting what has no formula

There is no expression that gives the nth prime, and yet the number of primes below a bound is predictable to within a fraction of a per cent — by a function that is not a formula for the primes but an integral of the wrong-looking quantity.

 A lopsided distribution added to itself, and the shape that returns. On the left, the exact distribution of a sum of copies of one lopsided distribution, standardised, for several counts: the shapes converge. On the right, the bell curve convolved with itself, which is the bell curve again. Probability

The shape that averaging leaves alone

Adding independent quantities blurs their distributions together, and rescaling restores the width. Almost every shape is changed by that operation. Exactly one is returned unaltered, and that is why sums of unrelated things keep arriving at it.

 How fast a sum becomes a bell curve. The largest gap between the distribution of a standardised sum and the bell curve, against the number of terms, on logarithmic axes. Both summands fall along a line of slope about minus a half. Probability

How fast the bell arrives

The limit theorem says a standardised sum approaches the bell curve and says nothing about when. The rate is one over the square root of the number of terms, the constant in front is made of the third moment, and both are visible.

 The chance the average clears 0.75, against the number of draws. The exact probability that the average of n draws exceeds a fixed level, on a logarithmic scale, falling along a straight line whose slope is the rate function, with the normal approximation drawn beside it and diverging. Probability

The tail is not a bell

The limit theorem describes a window of width one over the root of n around the mean; ask instead for the chance that an average lands a fixed distance away and the answer falls exponentially, at a rate computed from the summand before any n is chosen.

 The 91 histograms 12 draws can produce. A triangle whose points are the possible histograms of a fixed number of draws over three faces, each drawn as a dot shaded by how far it is from the true distribution. Probability

When the whole histogram deviates

A rare average has a price, an exponent that grows with the number of trials. Ask instead for the chance that the whole tally of outcomes comes out wrong, and the exponent is no longer a function of one number — it is a distance between two distributions, and every rare-average rate is a shadow of it.

 The rotation number against the parameter at K = 1. The measured rotation number of a circle map plotted against its parameter, forming a staircase that is flat over an interval at each simple rational. Dynamics

The staircase that is flat almost everywhere

A map of the circle advances by an average amount each step. Plot that average against the parameter driving it and the graph is flat over an interval at every rational, rises only on a set of measure zero, and still climbs from nothing to one.

 The chance of being connected, against the chance of an edge. Curves of the exact probability that a random graph on three to six labelled points is connected, plotted against the probability of each individual edge. Probability

The moment everything joins up

Add edges to a set of points one chance at a time and the graph goes from dust to a single piece — not gradually, but over a window that narrows as the point count grows. The last obstacle is almost always a single point with no edge at all, and that is what fixes where the change happens.

 The slopes the equation demands, and the curves that obey them. A field of short segments whose slope at each point is 0.9 times the height there, with 3 solution curves integrated through it; each doubles over an interval of 0.770 wherever that interval is taken. Analysis

The equation with only one answer

A rate of change proportional to the current amount is the most common description in nature, and it pins down the function completely. There is exactly one curve through each starting point, and a half-life and a doubling time are the same measurement.

 How fast each way of averaging closes in, as the dimension grows. Relative error against the number of points, both on logarithmic scales, for a regular grid in 1, 4, 8 dimensions and for random points in 8; the grid's lines steepen or flatten with the dimension and the random one does not move from a slope of a half. Probability

The error that does not care how many dimensions

A grid gets rapidly better in one dimension and hopelessly worse in twenty. Random points get better at the same slow rate whatever the dimension, which is why a method that is bad everywhere ends up being the only one that works.

 Two unbiased estimates of one integral, and their spread. The sharply peaked integrand with the proposal density that follows it, above a strip plot of 200 estimates from each of two methods; the weighted estimates cluster 4.2 times more tightly about the same value. Probability

Sampling where the answer lives

Monte Carlo error cannot be made to fall faster than the square root, so the only thing left to attack is the constant in front of it. Drawing points where the integrand is large, and dividing by how often they were drawn, leaves the answer alone and can shrink the noise many times over.

 A walk that visits each state as often as its weight says. The target distribution over 12 states with the share of a 40,000-step Metropolis run beside each bar, above the first 300 steps of the walk itself; the two distributions differ by 0.5 per cent in total. Probability

A walk that samples a distribution

When a distribution can be evaluated but not drawn from, a wandering point can be arranged to visit each state as often as its weight says. The rule needs no normalising constant, compares two weights and steps or stays.

 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. Probability

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.

 The expected number of monochromatic sets, and where it drops below one. The logarithm of the expected number of single-coloured 4, 5, 6-point sets in a random two-colouring, plotted against the number of points, with the crossing of one marked for each. Discrete

The colouring nobody has ever seen

Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.

All themes