The collection

Every essay — page 24

Page 24 of 48, continuing through the fields in the same order.

Geometry Analysis Algebra Discrete Topology Probability Number Dynamics Logic Computation Applied What's new Series Concepts Search

Probability

Randomness with a shape.

Two thresholds, not one

A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

Finding a threshold with two moments

At the threshold the largest part is neither of the two obvious sizes. A table with one row per graph size, giving the largest component at the critical edge probability and that value divided by three candidate scalings.

The window where the giant is born

One threshold narrowing, one staying wide. Probability curves for connectivity and for containing a triangle, plotted against the edge probability as a multiple of each property's own threshold, at several graph sizes.

Sharp, or merely a threshold

58.6% at 46 candidates, against 37% without the values. The chance of ending with the best candidate when the values are shown, against the number of candidates, for 10 sizes. It falls towards 0.5802 rather than towards 1/e.

When the numbers are shown

About the fourth-best, whatever the size of the field. The smallest expected rank achievable by an online rule, against the number of candidates, for 10 sizes. It rises to 3.8516 at 2500 candidates and its limit is 3.8695.

Giving up on the best

Half of what an oracle takes

Up to 4 choices among 60, and the thresholds that nest. For 60 candidates in random order and 1, 2, 3, 4 acceptances, the chance of ending with the best among those accepted — 37.3%, 60.0%, 74.3%, 83.5% — and where along the sequence the rule starts accepting for each number of choices in hand.

The thresholds that nest

Add the odds from the end: start at event 5 of 12. The odds of 12 independent events with chances 1/k — the secretary problem, the sum of the odds from the end reaching one at event 5, and the chance of stopping on the last success from each starting point, highest at 39.6%.

Add the odds from the end

A 6-sided die rolled 6 to 40 times: some face missing, and the sum stopped early. Curves of the chance that some face of a die has not yet appeared against the number of rolls, with the inclusion–exclusion sum stopped after one, two and three terms drawn around the exact curve.

A sum stopped early still says something

How many get their own hat

The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over.

The bound is the answer to a search

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.

No single input can move it far

Waiting for all 6 when they are not equally likely. One bar per kind giving the expected wait for that kind on its own, with the rarest much the tallest, and the expected wait for the whole collection printed above them.

The one that hardly ever comes up

How long 4 equally likely patterns take to appear. A bar for each of 4 patterns of 3 coin tosses giving the expected number of tosses before it first appears, with the lengths at which each pattern overlaps itself listed.

Two patterns, one chance, different waits

Any unevenness brings the match sooner

The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

A collision that finds a factor

Two children, and at least one is a boy. Four equally likely families drawn as quarters of a square: the question “is at least one a boy?” rules out only the girl–girl family, and leaves three equal quarters; the chance of two boys is 33.3%.

Two children and the sentence about one of them

One experiment, measured by runs and by awakenings. Two unit squares for the same coin and the same schedule: the same experiment weighed two ways: by runs, heads keeps half the square; by awakenings, heads is one of 3 equal slices.

One coin, counted by runs and by wakings

Permutations that avoid 8 forbidden cells. A 5 by 5 grid with 8 forbidden cells shaded and one permutation that avoids them marked, beside the numbers of ways to place non-attacking rooks on the forbidden cells and the count of avoiding permutations they give.

The cells a permutation must miss

5 couples seated so that no one sits beside a partner. A round table with 10 seats alternating women and men, labelled by couple, arranged so that no man sits next to his partner, with the number of such arrangements.

A round table with no couple together

Birthdays within k days: a half at 23, 14, 9, 7 people. Curves of the probability that two of m people have birthdays within k days, for k = 0, 1, 3, 6, with the group size at which each passes one half marked.

Fourteen people within a day

Nobody alone: a half at 3,064 people. The probability that no person in a room has a birthday unshared by anyone else, against the number of people, exactly and by a Poisson estimate.

A room where nobody is alone

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.

The ground a walk covers