Theme

Order out of noise — page 3

Random processes that reliably produce the same shape, and the reason that is less mysterious than it looks.

The cubic curves over GF(43) with the most and the fewest points. The solutions of two equations y squared equals x cubed plus ax plus b over the field with 43 elements, drawn as dots on a square grid: the curve with the most points and the curve with the fewest.

Give or take twice the square root

A cubic curve over the integers mod 43 should have about 44 points — one for each value of x, on average, and one at infinity. No curve misses by more than 13, the largest whole number below 2√43, and every count from 31 to 57 belongs to some curve. The first fact is Hasse's theorem, the second Deuring's, and the way the counts spread between the limits is a semicircle.

Probability

How many get their own hat

The chance that nobody gets their own hat settles on 1/e. The chance that exactly one person does settles on 1/e too, exactly two on 1/(2e), exactly three on 1/(6e) — the Poisson distribution with mean 1. The reason is a set of averages that come out exactly 1 at every size, and the counts reach the limit so fast that eight hats are within six ten-thousandths of it.

What one input can do, over 1024 cases. A table of functions of several inputs with the largest effect any single input has on each, the bound that effect implies, and the true tail probability — computed by enumerating every input.

Probability

No single input can move it far

Independence was never the hypothesis doing the work. A quantity built from many separately drawn inputs concentrates whenever changing one of them moves it only a little — and that covers quantities which are not sums of anything and have no formula at all.

Fair bits from a biased coin. 44 flips of a coin biased 0.7 towards 1, read in 22 pairs. Mixed pairs are kept and give their first bit; matched pairs are discarded. Over a long run the output is 50.2% ones, at 0.210 output bits per flip.

Computation

Fair bits from an unfair coin

Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.

Rule 184 at density 0.30. A space-time diagram of rule 184 on a ring of 120 cells, 80 steps down the page, starting from a random row with 36 cars. The diagonal stripes are free-moving cars; the jams dissolve.

Dynamics

A road where nobody overtakes

Rule 184 moves every 1 one cell to the right whenever the cell ahead is empty. It is one of only five elementary rules that never change the number of 1s, and that single property turns it into a model of traffic with an exact transition: below half density every jam dissolves, above it jams can never all clear and drift backwards against the flow.

A random pairing of 24 edges. Chord diagram of one uniformly random pairing of a 24-gon's edges, corners coloured by the vertex they become. a 24-gon with its edges paired at random and glued head to tail: the 24 corners fall into 3 vertices, so the surface has genus 5, against a most possible of 6.

Topology

The surface a random gluing makes

Pair the edges of a large polygon at random and glue each pair head to tail. The surface almost always has nearly as many handles as the polygon allows: a thousand edges leave about seven and a half vertices, and the genus is within four of its ceiling of 250. The vertices behave like the cycles of a random permutation, and their average is a harmonic number.

12 harmonic series with random signs, each settling on its own sum. Partial sums of the harmonic series with each sign chosen by a fair coin, for several independent runs, plotted against the number of terms on a logarithmic scale, beside the all-plus and alternating sign patterns.

Analysis

A coin in front of every term

Put all plus signs in front of 1, 1/2, 1/3, … and the sum runs off to infinity; alternate them and it settles on log 2. Toss a fair coin for each sign instead, and the sum settles — every time, on a different number. Where it tends to settle has a smooth, flat-topped shape, and at the value 2 that shape takes a height that agrees with one eighth to forty-two decimal places and is not one eighth.

$How long four orbits of the doubling map spend in each quarter. Grouped bars for four starting points of the doubling map, each group showing the fraction of time the orbit spends in each quarter of the unit interval, against a dashed line at one quarter.$ Dynamics

Almost every orbit is fair

Double a number and keep the fractional part, and do it again, and again. Where the orbit goes is written in the number's binary digits, and for almost every starting point it spends exactly a quarter of its time in each quarter of the interval. The proof is a short argument about Fourier coefficients being pushed to infinity — and it leaves room for a set of exceptions with no length at all, which includes every fraction and, for all anyone can prove, every number anyone has ever named.

Channel capacity 1 − H(p), and three codes at p = 0.1. The capacity of the binary symmetric channel plotted against its flip probability, with the rates of repetition, the Hamming code and no coding marked at one flip probability.

Computation

The rate a noisy channel allows

A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.

Decoding from 20 + m random combinations: the chance it works. Bars for the exact probability that 20 plus m random binary combinations of 20 message bits have full rank, with simulated frequencies as dots, for m from zero upwards.

Computation

Erasures a code can see

If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.

The Fermat quotient of 2 at every prime up to 4000, and where it is 0. A scatter of the Fermat quotient of 2 modulo p, divided by p, against p for the primes up to 4000; the points spread evenly between zero and one and reach zero at the Wieferich primes.

Number

Two primes where Fermat holds twice

Fermat's theorem says p divides 2^(p−1) − 1. Usually p² does not. It does at 1093 and at 3511 and at no other prime anyone has found, in searches reaching past 10^19. The leftover, (2^(p−1) − 1)/p taken mod p, behaves like a random number, so a prime has about a one-in-p chance of the extra divisibility — and a random count with that chance grows so slowly that two by now is unremarkable, while nobody can prove there are any more, or that there are infinitely many primes where it fails.

Probability

A room where nobody is alone

Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.

Measuring a closed curve with inlets by throwing lines at it. A curve inside a disc crossed by a sample of random lines with each crossing marked, beside the mean number of crossings and the length it implies against the true length.

Analysis

A length counted by the lines that cross it

Throw straight lines at random across a curve and count how often they cross it. The average count, times π times the radius of the target, is the curve's length — for a wiggly closed curve, a spiral or a snowflake alike, with no following of the curve and no derivative anywhere. It is Crofton's formula of 1868, and it measures length the way a map-reader's ruled transparency does.

The ground a 1,500-step walk covers. A random walk on a square grid drawn as a path, with every grid square it visited shaded and its start and end marked.

Probability

The ground a walk covers

A random walk of a thousand steps visits far fewer than a thousand places: in one dimension about fifty, in the plane about four hundred, in space about six hundred and sixty. The share of steps that land on new ground is exactly the chance of never coming home — so the number that decides whether a walker returns also decides how much of the world it sees.

A random labelled tree on 60 points. A tree drawn in horizontal layers by distance from a root point, with the leaves coloured differently from the internal points.

Discrete

A random tree is one part in e leaves

Choose a labelled tree on n points uniformly at random. A point is a leaf exactly when its label never appears in the tree's Prüfer code, so the share of leaves is (1 − 1/n)^(n − 2) — half the points for a tree on four, 36.8% for a large one, the reciprocal of e. The whole degree distribution follows the same way: one plus a Poisson count with mean one.

A majority of independent voters, more often right than any of them. The probability that a simple majority of n independent voters is right, for n from 1 to 201, when each voter is right with probability 0.45, 0.51, 0.55, 0.6, 0.7.

Applied

A majority wiser than its members

Condorcet's other theorem turns voting round: the voters no longer have preferences but judgements about a single fact, each a little more likely right than wrong. Then a simple majority of many of them is almost certainly right — 6,763 voters who are each right 51% of the time make a majority right 95% of the time. The theorem survives voters worse than a coin, if the average is better. It does not survive voters who share their mistakes, and when their skills differ the right rule weighs votes rather than counting them.

Number

The shape a random partition takes

There are about twenty-four thousand billion billion billion ways to write 1,000 as a sum of whole numbers. Pick one at random, draw its Ferrers diagram, shrink it by the square root of a thousand, and it is almost exactly the curve e^(−cx) + e^(−cy) = 1 with c = π/√6. So is the next one, and the next. A random partition of a large number has a shape, and the shape is known exactly.

How far each estimate can stray, when rare jumps are possible. The error that the sample mean and the median of 12 block means stay within, at confidence levels from 80% to 99.9%, over 60000 repeated samples of 120 draws from normal draws with rare large jumps, with Chebyshev's guarantee for the mean.

Probability

The median of many small averages

Knowing only that a quantity has a finite spread, the plain average of n samples can be promised to within σ/√(nδ) with confidence 1 − δ, and no better — Chebyshev's bound is tight, and rare large jumps achieve it. Cut the same samples into a dozen blocks, average each block, and take the median of the averages, and the promise improves to within about σ√(log(1/δ)/n). Nothing about the data has been assumed beyond the spread; only the way of combining it has changed.

Probability

A sphere that is nearly all equator

On an ordinary globe, the band within a tenth of the radius of the equator holds a tenth of the surface. On a sphere in a thousand dimensions the same band holds 99.85% of it, and the band of a fifth holds all but about two parts in ten billion. Almost every point of a high-dimensional sphere is near every equator at once — and so any function that cannot change quickly is, over almost all of the sphere, almost constant.

Where a coin-signed geometric series lands, for λ = 1/3, 1/2, 1/√2, 1/φ. Histograms of the exact distribution of the sum of plus or minus λ to the k, one panel per value of λ: a dust of separated pieces below one half, a flat block at one half, and smooth-looking overlapping shapes above.

Analysis

A coin in front of every power

Toss a coin for each sign of ±1 ± λ ± λ² ± … and the sum lands somewhere. Below λ = 1/2 it lands on a dust with gaps in it, at exactly 1/2 it lands anywhere with equal chance, and above 1/2 it lands on a smooth-looking hill — which for most λ has a density and for the golden value does not, though no picture can tell the two apart.

Who does well in a random market, as it grows. A log-log plot of the average rank of partner for the proposing side and the receiving side of random balanced markets against the market's size, with dashed curves for ln n and n over ln n.

Applied

One extra person on one side

In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.

Two staircases and the interval between them, at K = 1.5. A plot against the drive of the upper and lower ends of the circle map's rotation interval above the critical line, two stepped curves with the band between them shaded.

Dynamics

A whole interval of speeds

Below the critical line every orbit of the circle map goes round at the same average speed. Above it the map folds back on itself, and the speed depends on where the orbit starts — not a few different values but a whole interval of them, every fraction in it the speed of some periodic orbit, and almost none of them ever seen by an orbit started at random.

The standard map as its kick grows. Three square phase portraits of the standard map at increasing strengths, dotted with orbits: curves spanning the square at the smallest, fewer at the critical value, and a scattered sea with islands at the largest.

Dynamics

The last circle to break

Kick a spinning rotor once a turn and most of its motions stay on curves that wind round forever, walls no orbit can cross. As the kick grows the walls break one by one, and the last to go is the one whose winding is the golden ratio — at a kick of 0.9716, found by watching a sequence of periodic orbits approximate it and asking whether they are stable.

Where x ↦ βx mod 1 spends its time, the golden ratio φ. A histogram of 2000000 orbit points of the β-map for the golden ratio φ in 50 bins, with Parry's staircase density drawn over it; they agree, and the density steps down at the orbit of 1.

Dynamics

Where a base-β orbit spends its time

Follow x ↦ βx mod 1 for a million steps and count how often the orbit visits each part of the interval. For the doubling map the answer is evenly; for the golden ratio it is a staircase with one step, spending 1.17 times the average near 0 and 0.72 times it near 1. The step sits exactly where the orbit of the number 1 lands, and in a base whose 1 never has a finite expansion the staircase has infinitely many steps.

All themes