The walk that counts a family
Worth reading first: The path folded at its first touch · Sixteen trees on four points.
In 1873 Francis Galton asked, in the Educational Times, why so many aristocratic surnames die out. His model was the simplest possible: one man, who has a random number of sons, each of whom has a random number of sons, independently and with the same distribution, generation after generation. The surname survives as long as there are sons to carry it. The Reverend Henry Watson answered the next year with the method still used — the generating function of the number of sons, iterated — and the model is called the Galton–Watson process. The moment a giant appears used it to find where a random graph’s giant component is born: a family dies out for certain when each member has on average at most one child, and survives with positive probability when the average exceeds one.
That is the question of whether the family ends. This essay asks how big it gets when it does, and answers it by turning the family into a random walk. The path folded at its first touch met the tool that does the work, the cycle lemma, as a counting fact about walks; here it becomes a theorem about family trees. And when the number of children is Poisson with mean one, the probability that a family has exactly members turns out to be — where is the number of rooted trees on labelled points, the count that sixteen trees on four points began from. A probability about random families is a count of fixed trees in disguise.
A family is a walk
Number the members of a family in the order a depth-first search meets them: the ancestor first, then the first child and that child’s whole line of descendants, then the second child and its line, and so on. The figure’s family has sixteen members, numbered that way. Now walk along the list keeping a count: start at 0, and at each member add that member’s number of children minus one. The ancestor has two children, so the count goes to 1; member 2 has one child, so it stays at 1; member 3 has two, so it rises to 2; and a member with no children lowers the count by one.
The count has a meaning at every step. After visiting members it equals the number of members already known about — born to someone visited — but not yet visited, minus one. At the start one person, the ancestor, is known and unvisited, so the count is . Each visit removes one person from the unvisited pile and adds their children to it. So the count stays at 0 or above for as long as someone is still waiting to be visited, and it reaches at exactly the step when the pile empties — when the whole family has been seen. In the figure that happens at step 16.
So the size of the family is the first time the walk hits . Nothing has been lost in the translation: the sequence of children’s counts in depth-first order determines the tree completely, and the walk is its running sum. The walk is called the family’s Łukasiewicz path, after the logician whose bracket-free notation reads a formula’s tree from the same sequence. And because the members’ numbers of children are independent and identically distributed, the walk’s steps are too: it is an ordinary random walk with steps , where is the number of children, which is what makes the rest of the argument possible.
One rotation in eight
The walk’s steps are each at least — a member can have no children, but not fewer — and a family of size is a sequence of steps that adds to and does not reach before its last step. The cycle lemma says that among the cyclic rotations of any sequence of steps, each at least , adding up to , exactly one has that property. The figure shows a sequence of eight steps and all eight of its rotations; seven of them reach early, and one, the rotation that starts just after the sequence’s last lowest point, reaches only at the end.
The reason is a picture. Draw the walk of the whole sequence and repeat it, so that it descends by one unit each period; the rotation that starts at the last moment the walk is at its lowest level within a period must stay above that level until it has gone round once, and every other starting point reaches a lower level sooner. The lemma is due in this form to Arieh Dvoretzky and Theodore Motzkin in 1947, and the same fact underlies the ballot theorem and the reflection count of counting the paths that go wrong, where the Catalan numbers are exactly the walks that a rotation makes complete.
Applied to families it gives the hitting-time theorem. The steps of the random walk are independent and identically distributed, so every rotation of a given sequence of steps is exactly as likely as the sequence itself. Group the sequences that add to by rotation; within each group exactly one in is a complete family. Therefore
where is the walk’s position after steps. The left side is a hard question about trees; the right side is a question about the sum of independent numbers, which is easy. Richard Otter proved this for branching processes in 1949 and Meyer Dwass gave the cycle-lemma proof in 1969.
The law of the family’s size
Take the number of children to be Poisson with mean . The sum of independent Poisson() numbers is Poisson(), so means that sum equals , which has probability . Dividing by ,
This is the Borel distribution, found by Émile Borel in 1942 in a model of customers arriving at a queue during a busy period, which is the same branching structure: each customer served brings in a Poisson number of new arrivals. With it is . The figure simulates 100,000 families with Poisson(1) children, letting each grow until it ends, and compares the share of each size with the formula. A family of one — the ancestor childless — has probability and the simulation gives 0.3698; a family of two has probability against 0.1344; and every size up to sixteen agrees within its sampling error, which the computation checks size by size.
The distribution decays slowly. A family of ten has probability 1.25%, and a family of a hundred about 0.04%, which is small but nothing like the exponential smallness of a sum of independent things. Families with one child each on average are usually tiny and occasionally enormous.
The probability is a count of trees
The numerator is familiar. Cayley’s formula says there are trees on labelled points, as sixteen trees on four points drew for four points, and choosing a root multiplies by : there are rooted labelled trees. The figure counts them by brute force — every way of giving each point except the root a parent, keeping those with no cycles — and finds 1, 2, 9, 64, 625 and 7,776, exactly each time. Multiplied by , these are the Borel probabilities to every digit.
That is not a numerical coincidence, and the reason is worth saying. A Poisson(1) family of size , with its members labelled to at random, is a uniformly random rooted labelled tree: every one of the trees is equally likely. The family’s shape as a branching process — who has how many children, in what order — corresponds to the tree’s structure, the Poisson probabilities for each member’s children combine to divided by a product of factorials, and that product is exactly cancelled by the number of ways the labels can be distributed down an ordered tree. What is left is for each labelled tree. So a random walk, a branching process and Cayley’s formula are three descriptions of one object, and every function is a tree with two marks found the same hiding in random functions for the same reason.
Every family ends, and the average is infinite
The hitting-time theorem also explains the shape of the tail. For the walk has mean step zero, and a walk with no drift returns to its starting level eventually, as a walk that always comes home proved; so the walk reaches with probability one, and every family ends. But the probability that the family has at least members falls only like — the probability that a fair walk has not yet gone below zero after steps, by the same reflection argument as the path folded at its first touch. The figure’s middle curve follows the dashed line: 2.4% of families have at least a thousand members, against a prediction of 2.5%.
A tail of is too heavy to have a finite mean. The expected number of members is , one per generation on average, which is for and infinite at . A family that is certain to end has infinitely many members on average. There is no contradiction, only a heavy tail: the certainty is carried by the many small families and the infinite mean by the rare enormous ones.
On either side the picture changes completely. With the walk drifts downward and the tail falls exponentially; no simulated family of 20,000 reached two hundred members. With it drifts upward, and a fixed share of walks never reaches at all: 31.3% of the simulated families were still growing when stopped at twenty thousand members, against the theoretical survival probability of 31.4%, the root of the extinction equation that the giant-component essay solved.
The same walk explores a random graph
The depth-first walk is not only a device for families. It is how a random graph’s components are measured, and the connection explains why the Borel law turns up there too. To find the component containing a point of a random graph, explore it: start at the point, look at its neighbours, then visit them one at a time, each time adding the newly discovered neighbours to a pile of points waiting to be visited. The number waiting, minus one, is a walk exactly like the family’s, and the component is fully explored when it first reaches . In a random graph on points where each pair is joined with probability , each point visited early in the exploration has a binomial number of new neighbours that is close to Poisson with mean — which is why the moment a giant appears could locate the giant at by asking whether a Poisson() family survives.
The hitting-time theorem sharpens that. At , the size of the component containing a given point is, for large , close to the Borel law of this essay: a point is isolated with probability about , in a component of two with probability about , and so on, with the same decay of the individual probabilities. The approximation fails only when the exploration has met a sizeable share of the graph and starts revisiting points, which at happens at component sizes around — the critical window that the window where the giant is born measured. Below that scale the random graph’s components are Galton’s families, and the walk that counts the one counts the other.
Galton’s question, answered by a walk
Galton’s original question was about surnames, and the walk answers its finer form. Suppose each man has a Poisson number of sons with mean exactly one — a population neither growing nor shrinking on average. Then every surname dies out, but the number of men who ever bear a given surname has the Borel distribution, which means that about 37% of surnames die with their first bearer, 63% last at least two men, a quarter last at least ten, and 2.5% last at least a thousand. A stable population, in this model, loses surnames steadily and keeps a few for a very long time, and that is the pattern Galton was trying to explain.
The model is too simple for any real population — the number of sons is not independent from man to man, nor the same for every generation, and surnames are adopted and changed — and its quantitative predictions should not be read off a parish register. What survives is the qualitative point. In any population that is not growing, almost every line dies out, and the ones that last do so by luck rather than by any property of the line.
What the simulation does not show
The family sizes are simulated, and the simulation has limits it cannot hide. Each family is grown until it ends or reaches a cap — a hundred thousand members for the Borel comparison, twenty thousand for the tails — and a family stopped at the cap is counted as never ending; at a few families out of twenty thousand would reach the cap even though they would eventually end, and they sit in the tail’s last point. The cycle lemma, the hitting-time theorem and the tree count are exact, and the figures check them exactly where they can: the walk of the drawn family is computed step by step, all eight rotations are examined, and every rooted tree up to six points is enumerated. The Borel law beyond size sixteen, the tail and the infinite mean are theorems the figures illustrate rather than prove.
And the depth-first order is a choice. Visiting the family generation by generation instead gives a different walk with the same endpoint; the hitting-time theorem holds for that one too, because it depends only on the steps being exchangeable. What the depth-first walk adds is that the tree can be rebuilt from it, so that the bijection between families and walks is exact rather than merely a statement about sizes.
Still open: when the children are not independent
The argument used two things: that the numbers of children are independent, and that they all have the same distribution. Both fail in most real populations, and both fail in the random graphs where branching processes are used as approximations. When the offspring distribution varies with the generation or the environment — a branching process in a random environment — the survival probability and the size of the surviving population depend on the environment in ways that are understood in outline and not in detail; the critical case, where the environment is on average neither favourable nor unfavourable, has a theory of its own that is still developing. And for exploration of a graph in which the people met are not independent, because the graph has short cycles, no exact counterpart of the hitting-time theorem is known: the walk is still defined, but its steps are no longer exchangeable, and the cycle lemma has nothing to say.
Down by one at the end
Visit a family depth-first and add each member’s number of children minus one: the running total is a random walk, and the family is complete at exactly the step the walk first reaches . The cycle lemma says that one rotation in of any such sequence is a complete family, so the chance of a family of size is the chance the walk is at after steps, divided by . For Poisson(1) children that is the Borel law , matched by 100,000 simulated families, and its numerator is Cayley’s count of rooted labelled trees, enumerated here up to 7,776. With one child on average every family ends and the average family is infinite; with 1.2 children, nearly a third never end.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- Every third coefficient — both name generating function, random walk
- When to stop tossing a coin — both name generating function, random walk
Named objects
A dashed tag is an object no other essay names yet.
Branching processCycle lemmaGenerating functionHitting timeLabelled treePoisson distributionRandom walk