Everyone, or No One

Your family tree, drawn honestly, needs more people than have ever been born. So it folds. And once it folds, something stranger than the folding is waiting a little further back: a generation in which every single human being alive is an ancestor of every human being now, or of nobody at all, with no one in between.

A layer in the Artificial Wasteland · everything below is recomputed in your browser

Two parents, four grandparents, eight great-grandparents. The rule is so simple that nobody checks where it goes. Where it goes is off the edge of the world. Thirty generations is roughly nine hundred years, and thirty generations of doubling is a billion ancestor slots, which is more people than were alive in 1100. Push a little further and your tree needs more people than have ever lived, anywhere, in the whole history of the species.

Nothing is wrong with the doubling. What is wrong is the picture of a tree. A tree branches outward forever and never touches itself. A real pedigree touches itself constantly: the same person occupies many slots, because your parents' ancestors are, going back, mostly the same people. The tree is not a tree. It is a net, and the net has a shape, and the shape has a theorem.

1. The arithmetic that cannot be true

Move the dial. The left number is what the doubling demands: the number of slots in your pedigree at that depth, which is exactly 2^g and is computed here in exact integer arithmetic, not floating point. The right numbers are what the world can supply.

Two crossings matter, and both are exact. Somewhere around generations back, your pedigree has more slots than there are people alive on Earth today. A few generations later, at , it has more slots than the Population Reference Bureau's estimate of every human who has ever been born: all 117,020,448,575 of them, back to the start of counting.

The slots are still real. Each one is a genuine path back through your pedigree, and there really are 2^g of them. What cannot be real is that they hold 2^g different people. So the same people fill many slots, and the further back you go the harder they have to work: at thirty-three generations your tree needs, on average, about twenty slots from every human being alive at the time, whichever of the three generation lengths above you pick, and your actual ancestors are only a fraction of the people alive at the time. Genealogists call this pedigree collapse, which makes it sound like a defect. It is not a defect. It is the only thing that can happen.

2. Chang's village

In 1999 the Yale statistician Joseph Chang asked what happens if you take the folding seriously and just run it. He wrote down the simplest model that has two parents in it. A population of fixed size n, generations that do not overlap, and every individual picking two parents uniformly at random from the generation before. That is the whole model. He then proved something about it that reads, the first time, like a misprint.

In this model, if the population size n is large, the number of generations, T_n, back to a MRCA has a distribution that is concentrated around lg n (where lg denotes base-2 logarithm), in the sense that the ratio T_n/(lg n) converges in probability to 1 as n → ∞. Chang 1999, abstract

Not proportional to n. The logarithm of n. A village of a thousand finds a common ancestor of everybody in about ten generations; a nation of a million in about twenty; and doubling the population adds one. For comparison, the same population traced through mothers only, the mitochondrial line that gives us "mitochondrial Eve", takes something like n generations, so about a million times longer for a million people. Adding the father does not halve the wait. It changes the arithmetic from multiplication to counting binary digits.

Run it. The model below is Chang's, exactly as described, drawn fresh in your browser from the seed you pick.

3. The band that closes

The picture above is the real content of this page, and it is worth sitting with. Each column is one generation further back. The gold band is the people who are ancestors of everybody alive at the bottom. The grey band is the people who left no living descendants at all: their line simply stopped. The blue band between them is everyone else, the ordinary case, the people who are ancestors of some of the population and not the rest, which is what you would assume ancestry mostly consists of.

Watch what the blue band does. It starts as very nearly the whole population, and then it shuts. Chang's second theorem is exactly the statement that it shuts, and it names the moment:

Let U_n denote the number of generations, counting back in time before the present, to a generation in which each individual is either a CA of all present-day individuals or an ancestor of no present-day individual. Let γ denote the smaller of the two numbers satisfying the equation γ e^−γ = 2 e⁻², and let ζ = −1/(lg γ) ≈ 0.7698. Then U_n/((1 + ζ) lg n) → 1 as n → ∞. Chang 1999, Theorem 2

The constant 1 + ζ is 1.7698, and this page solves γ e^−γ = 2 e⁻² by bisection rather than quoting it: . So at a little under twice the depth of the common ancestor, the middle disappears. Past that line there is no such thing as being partly related to the present. Every person in that generation who has any living descendants at all has all of them. Everyone alive today has, from that point back, precisely the same set of ancestors: not similar, not overlapping, identical, name for name. This is called the identical ancestors point, and it is why the page is called what it is called.

There is a second number hiding in that picture, and it is exact. Follow one person's descendants forward instead of backward: while their descendants are few, the count behaves like a branching process with Poisson(2) children, which either dies out or runs away. So the gold band settles at 1 − ρ, where ρ is that process's extinction probability, the smallest root of ρ = e^−2(1−ρ). This page solves it by iteration and gets . Chang gives the same figure in his reply to the paper's published discussion. Roughly four people in five, in any sufficiently ancient generation, are ancestors of the entire present. The other one in five left no living trace at all. Nothing else happens.

It is worth being clear about what this is and is not. It is a fact about the ancestor relation, not about inheritance. Two people with an identical ancestor set can be wildly different, because which ancestors handed down which stretches of DNA is a completely separate lottery, and section 5 runs that lottery. The identical ancestors point does not say we are the same. It says that past a certain depth, the question "whose descendant are you?" stops distinguishing anybody, because the only two answers left are everyone's and no one's.

And it is worth hearing the strongest objection, which was made immediately, in print, alongside the paper. Chang's result was published with a discussion by five probabilists, and John Kingman, whose coalescent is the reason anyone can compute these things at all, was not impressed:

The concept of being a common ancestor of a whole subsequent population is a very weak one, and it is not clear that it has any real significance. The point of genealogy is either to describe inheritance of something (titles, property) or to understand correlations between relatives (inheritance of genes). In neither case is the existence of a single common ancestor relevant in itself. J. F. C. Kingman, in the discussion of Chang 1999, page 1035

He is right about the weakness, and section 5 is where that weakness gets measured rather than argued. Keep his sentence in mind as the correct discount on everything above. What survives it is that the ancestor relation, weak as it is, turns out to have a completely different shape from the one everybody pictures, and the shape is checkable.

Chang's Table 1, rerun

Chang published twenty-five trials at each of four population sizes. Those numbers are transcribed below from his paper, next to what this page's implementation of his model produces from scratch. Nothing here is fitted: the model has no free parameters.

"Ours" is mean (s.d.) over 200 fresh runs per size, from research/everyone-or-no-one/run.mjs. Chang's own remark on his table was that "one might have guessed a numerical constant closer to 2 rather than 1.77 from this small study", and the last column shows why: 1.77 is an asymptotic statement, and at these sizes U/lg n is still visibly above it.

4. The world is not a village

Here is the part the internet always drops. Chang did not claim any of this applied to humanity. He said the opposite, in the paper, unprompted, on page 1005:

What is the significance of these results? An application to the world population of humans would be an obvious misuse. For example, we would not claim that a common ancestor of every present-day human may be found within the last lg n generations. Even if we took n to be 5 billion, this would imply a CA just about 32 generations ago, perhaps 500 years or so. An important source of the inapplicability of the model to this situation is the obvious non-random nature of mating in the history of mankind. Chang 1999, page 1005

People do not choose mates uniformly at random from the planet. They choose from the next village, and oceans exist. So in 2004 Chang went back to it with Douglas Rohde and Steve Olson and asked the honest version of the question: what if the population is cut into groups that mate among themselves and only trade a trickle of migrants? They wrote the population onto the nodes of a graph, one migrating pair per edge per generation, and proved that the logarithm survives. Only the constant changes, and it changes into pure graph theory: the depth to a common ancestor grows like (R + D)·lg n, where R is the graph's radius, and the depth to the identical ancestors point grows like (diameter + 1.77)·lg n.

Their most world-shaped graph is ten nodes: Africa in two pieces, Asia in two, the Americas, Greenland, southeast Asia, Australia and the remote Pacific, joined the way migration historically joined them. It is drawn below from the edge list this page uses, and the numbers under it are recomputed from that edge list, not copied: the radius and diameter should come out at 3 and 5, which is what the paper's own figure caption says, and R + D and diameter + 1.77 should come out at the values printed in the last columns of their Tables 1 and 2.

Rohde, Olson & Chang 2004, Tables 1 and 2, rerun

Their tables give the mean and standard deviation of both times over 100 runs, for four graphs at five population sizes. Below, their published cell and this page's own reproduction, run from the model description with no fitting.

The rule their paper does not state

Reproducing this turned up something the paper leaves out. "Neighbouring subpopulations exchange one pair of migrants per generation" has two natural readings. A migrant might be someone born in the neighbouring group, so both of their parents sit across the edge. Or a migrant might be someone who stayed and mated across the edge, so one parent is there and one is at home. The paper does not say which, and the difference is not cosmetic: it moves every number in both tables.

Across all six of these cells the "both parents across" reading lands on the published value and the other reading runs several per cent long. That is not a fit, since there was nothing to fit: two discrete alternatives, six independent comparisons, one of them matching throughout. So the missing sentence is recoverable from the tables it produced.

What all of this buys, honestly stated: the graph model says that cutting the world into ten weakly connected pieces multiplies the depth by three, and the depth was logarithmic, so three times a logarithm is still a logarithm. The paper then extrapolates its ten-node graph to a world of 250 million and gets a common ancestor around 300 BC and identical ancestors around 3000 BC. Their second, much heavier simulation, with individual lifespans, three levels of geography, dated shipping routes and historical population targets, gives a mean common ancestor date of 1415 BC under conservative migration and AD 55 under generous migration. This page does not reproduce that second model. It reproduces the graph model, which is the part with a theorem attached. The headline dates are quoted from the paper, and the paper calls them "extremely tentative" itself.

5. The ancestors who gave you nothing

Now the correction, and it is worth getting the provenance right because the claim has a history. In May 2002 The Atlantic ran a piece by Steve Olson under a line that read "everyone of European ancestry is descended from Muhammad and Charlemagne", and the article built that on Chang's theorem. The framing itself came from genealogists a few years earlier; Mark Humphrys, who has been keeping the argument on the open web since the 1990s, puts it flatly: "Quite likely everyone in the West descends from Charlemagne (died 814 AD)." Chang himself never wrote anything of the kind. His paper says applying the model to humanity "would be an obvious misuse", and it adds a second warning that almost nobody carries forward: "This paper is not about genetics. That is, it is not about who gets what genes."

That second warning is the whole of this section. As a statement about pedigrees, the Charlemagne claim is a reasonable reading of the mathematics above. Taken, as it usually is, to mean that you carry something of Charlemagne, it is almost certainly false, and the reason is better than the claim.

Genealogical ancestors double. Genetic ancestors cannot, because your genome is a fixed length and can only be cut so many times. Every generation back, the meioses of that generation break your inherited material at crossover points, and the number of pieces grows by the genetic length of the genome, in Morgans, per generation: an addition, not a doubling. Summing the sex-averaged HapMap-derived recombination map gives Morgans over 22 autosomes, so the expected number of distinct pieces at generation g is 2·(22 + (g−1)·G), a straight line racing an exponential it is going to lose. Published values of G differ by map: Ralph and Coop take "about 32 Morgans", Coop's own working note uses 33, and the map summed here gives 36.27. The dial below moves it, because a conclusion that depended on which map you picked would not be a conclusion.

The crossing happens at generation : that is where your ancestor slots first outnumber the pieces your genome is made of, and from there the fraction of your own family tree that is written anywhere in your body falls off a cliff. Twenty generations back, about six hundred years, you have a million ancestor slots and roughly thirteen hundred of them handed you any DNA at all. The rest are ancestors in every sense except the one people usually mean.

This is not only a simulation result. In 2013 Peter Ralph and Graham Coop went looking for the gap in real genomes, using shared stretches of DNA across 2,257 Europeans, and found both sides of it in the same dataset. Two Europeans living more than 2,000 km apart share, on average, about one thirty-second of a genetic common ancestor from the last thousand years: which is to say, usually none. And from that same measurement they conclude, in the paper's own words, "thousands of shared genealogical ancestors in only the last 1,000 years even between pairs of individuals separated by large geographic distances". One relationship, two counts, four orders of magnitude apart. The genome is simply not a big enough envelope to carry the pedigree.

So both halves are true at once, and neither cancels the other. You almost certainly do descend from Charlemagne, if you have any European ancestry, in the same ordinary sense that you descend from your grandmother. And you almost certainly carry not one base pair that came from him. Ancestry is not a substance. It is a relation, and it is much wider and much thinner than the word makes it sound.

The gentler thing this leaves is the one the 2004 paper ended on, and it is not sentimental, it is just what the arithmetic says. Go back far enough, a few thousand years, well inside written history, and there is no partial membership left. Everyone alive then who has any descendants at all is an ancestor of every person now reading this, and of everyone who is not. The people who planted the first rice, the people who built the pyramids, the people whose names nobody wrote down: all of them, or none of them. There is no third band.