Matpic
mathematics, in pictures
Concept

Coupon collector

The problem of how long it takes to see every one of n equally likely kinds when sampling at random with replacement. The answer is about n ln n draws, and the wait is dominated by the last few kinds, which is why covering everything takes far longer than seeing most things.

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

One piece, and connected, are different thresholds. Two curves against the average degree for graphs of 400 points: the largest component's share, rising from an average degree of one, and the probability of connectivity, rising only near the logarithm of the point count.

Two thresholds, not one

A random graph acquires a piece holding most of its points at average degree one, and is still not connected. Connectivity waits until the average degree reaches the logarithm of the size, and what holds it up is the very last isolated point.

probability · Random graphs 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

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.

probability · Birthday problem 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.

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.

applied · Stable matching How far a deck of 52 is from random after each riffle shuffle. A bar chart over one to 12 riffle shuffles of the exact total variation distance from a uniformly random deck. The bars stay near one for the first few shuffles and drop sharply around 8.

The forgetting that happens all at once

A single small chain forgets its start gradually, a little more with every step. A family of large ones can do something different — stay almost perfectly informed about where it began, and then lose all of it inside a window far shorter than the wait. That cliff is the cutoff phenomenon, and it is why "seven shuffles" is an answer rather than a convention.

probability · Markov chains Arcs that overlap and still leave gaps. n=14, a=0.2: starts 0.014,0.017,0.118,0.192,0.232,0.237,0.251,0.428,0.458,0.500,0.510,0.579,0.930,0.931; gaps 1; P(cover) exact 0.34675223.

Arcs that cover a circle

Throw fourteen arcs, each a fifth of a circle, onto the circle at random: together they are nearly three times as long as it, and still a third of the time some stretch is left bare. The chance of covering is an alternating sum over which gaps are too long, found by W. L. Stevens in 1939. Its terms run into the thousands and cancel to almost nothing, and they say that random covering costs a logarithm.

probability · Inclusion exclusion

Named alongside it

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

ExpectationMarkov chainSimulationBirthday problemBonferroni inequalitiesConnectivityDeferred acceptanceExact arithmeticExpected valueFirst momentGeometric probabilityGumbel distribution

All concepts