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 2 essays across one field — 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

Named alongside it

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

Birthday problemConnectivityExpectationExpected valueFirst momentIsolated vertexMarkov chainPhase transitionPoisson approximationRandom graphSimulationThreshold

All concepts