Probability

The walk that counts a family

Start with one ancestor, give everyone a random number of children, and ask how big the whole family gets. Visit the family member by member and keep a running total of children minus one: the total is a random walk, and the family is finished at the exact step the walk first drops below zero. A theorem about rotating sequences then gives the size's law in one line, and when each person has on average one child it is Cayley's count of labelled trees, multiplied by e⁻ⁿ/n!.

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 nn members turns out to be nn−1e−n/n!n^{n-1}e^{-n}/n! — where nn−1n^{n-1} is the number of rooted trees on nn 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

A family of 16, and the walk that counts it. seed 11: children 2,1,2,2,0,2,1,1,2,0,0,0,0,1,1,0; walk 0,1,1,2,3,2,3,3,3,4,3,2,1,0,0,0,-1
Fig. 1 A family tree with Poisson(1) numbers of children, its 16 members numbered in the order a depth-first search visits them. Below, the walk that adds each member’s number of children minus one: it first reaches −1 at step 16, the size of the family.

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 kk 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 1−1=01 - 1 = 0. 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 −1-1 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 −1-1. 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 ξ−1\xi - 1, where ξ\xi is the number of children, which is what makes the rest of the argument possible.

One rotation in eight

One rotation in 8 is a family. steps 1,-1,2,-1,0,-1,-1,0; rotation 8 hits -1 last.
Fig. 2 One sequence of 8 steps, each −1 or more, adding up to −1, started at each of its 8 positions in turn. Exactly one rotation first reaches −1 at its very last step, shaded.

The walk’s steps are each at least −1-1 — a member can have no children, but not fewer — and a family of size nn is a sequence of nn steps that adds to −1-1 and does not reach −1-1 before its last step. The cycle lemma says that among the nn cyclic rotations of any sequence of nn steps, each at least −1-1, adding up to −1-1, exactly one has that property. The figure shows a sequence of eight steps and all eight of its rotations; seven of them reach −1-1 early, and one, the rotation that starts just after the sequence’s last lowest point, reaches −1-1 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 nn steps is exactly as likely as the sequence itself. Group the sequences that add to −1-1 by rotation; within each group exactly one in nn is a complete family. Therefore

P(family has n members)=1n P(Sn=−1),P(\text{family has } n \text{ members}) = \frac1n\,P(S_n = -1),

where SnS_n is the walk’s position after nn steps. The left side is a hard question about trees; the right side is a question about the sum of nn 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

How big a family gets, with one child on average. 1:0.3698/0.3679 2:0.1344/0.1353 3:0.0753/0.0747 4:0.0493/0.0488 5:0.0351/0.0351 6:0.0271/0.0268 7:0.0209/0.0213 8:0.0174/0.0174 9:0.0143/0.0146 10:0.0122/0.0125 11:0.0112/0.0109 12:0.0100/0.0095 13:0.0083/0.0085 14:0.0074/0.0076 15:0.0069/0.0068 16:0.0060/0.0062
Fig. 3 The sizes of 100,000 family trees in which every member has a Poisson(1) number of children: the share of each size from 1 to 16, against the Borel law nn−1e−n/n!n^{n-1}e^{-n}/n!.

Take the number of children to be Poisson with mean λ\lambda. The sum of nn independent Poisson(λ\lambda) numbers is Poisson(nλn\lambda), so Sn=−1S_n = -1 means that sum equals n−1n - 1, which has probability e−λn(λn)n−1/(n−1)!e^{-\lambda n}(\lambda n)^{n-1}/(n-1)!. Dividing by nn,

P(size=n)=e−λn(λn)n−1n!.P(\text{size} = n) = \frac{e^{-\lambda n}(\lambda n)^{n-1}}{n!}.

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 λ=1\lambda = 1 it is nn−1e−n/n!n^{n-1}e^{-n}/n!. 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 e−1=0.3679e^{-1} = 0.3679 and the simulation gives 0.3698; a family of two has probability 2e−2/2=0.13532e^{-2}/2 = 0.1353 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 family's probability counts labelled trees. 1: 1, 2: 2, 3: 9, 4: 64, 5: 625, 6: 7776
Fig. 4 The rooted trees on n labelled points, counted by brute force — 1, 2, 9, 64, 625 and 7,776, which are nn−1n^{n-1} — and the same numbers multiplied by e−n/n!e^{-n}/n!, which is exactly the probability that a Poisson(1) family has n members.

The numerator nn−1n^{n-1} is familiar. Cayley’s formula says there are nn−2n^{n-2} trees on nn labelled points, as sixteen trees on four points drew for four points, and choosing a root multiplies by nn: there are nn−1n^{n-1} 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 nn−1n^{n-1} each time. Multiplied by e−n/n!e^{-n}/n!, 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 nn, with its members labelled 11 to nn at random, is a uniformly random rooted labelled tree: every one of the nn−1n^{n-1} 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 e−1/k!e^{-1}/k! for each member’s kk children combine to e−ne^{-n} 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 e−n/n!e^{-n}/n! 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 nn−1n^{n-1} hiding in random functions for the same reason.

Every family ends, and the average is infinite

Families that end, barely. λ=0.8: 1:1.0000 2:0.5445 5:0.2419 10:0.1236 20:0.0527 50:0.0112 100:0.0019 200:0.0000 500:0.0000 1000:0.0000 2000:0.0000 5000:0.0000 inf 0.0000; λ=1: 1:1.0000 2:0.6314 5:0.3754 10:0.2587 20:0.1822 50:0.1127 100:0.0800 200:0.0565 500:0.0352 1000:0.0239 2000:0.0165 5000:0.0112 inf 0.0057; λ=1.2: 1:1.0000 2:0.6979 5:0.4909 10:0.4038 20:0.3537 50:0.3225 100:0.3146 200:0.3132 500:0.3130 1000:0.3130 2000:0.3130 5000:0.3130 inf 0.3130
Fig. 5 The share of 20,000 simulated families with at least n members, on logarithmic scales, for mean numbers of children 0.8, 1 and 1.2. At exactly one every family ends, yet the tail falls only like the dashed 2/(πn)\sqrt{2/(\pi n)}.

The hitting-time theorem also explains the shape of the tail. For λ=1\lambda = 1 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 −1-1 with probability one, and every family ends. But the probability that the family has at least nn members falls only like 2/(πn)\sqrt{2/(\pi n)} — the probability that a fair walk has not yet gone below zero after nn 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 n−1/2n^{-1/2} is too heavy to have a finite mean. The expected number of members is 1+λ+λ2+⋯1 + \lambda + \lambda^2 + \cdots, one per generation on average, which is 1/(1−λ)1/(1 - \lambda) for λ<1\lambda < 1 and infinite at λ=1\lambda = 1. 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 λ=0.8\lambda = 0.8 the walk drifts downward and the tail falls exponentially; no simulated family of 20,000 reached two hundred members. With λ=1.2\lambda = 1.2 it drifts upward, and a fixed share of walks never reaches −1-1 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 −1-1. In a random graph on nn points where each pair is joined with probability c/nc/n, each point visited early in the exploration has a binomial number of new neighbours that is close to Poisson with mean cc — which is why the moment a giant appears could locate the giant at c=1c = 1 by asking whether a Poisson(cc) family survives.

The hitting-time theorem sharpens that. At c=1c = 1, the size of the component containing a given point is, for large nn, close to the Borel law of this essay: a point is isolated with probability about e−1e^{-1}, in a component of two with probability about e−2e^{-2}, and so on, with the same n−3/2n^{-3/2} 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 c=1c = 1 happens at component sizes around n2/3n^{2/3} — 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 λ=1\lambda = 1 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 2/(πn)\sqrt{2/(\pi n)} 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 −1-1. The cycle lemma says that one rotation in nn of any such sequence is a complete family, so the chance of a family of size nn is the chance the walk is at −1-1 after nn steps, divided by nn. For Poisson(1) children that is the Borel law nn−1e−n/n!n^{n-1}e^{-n}/n!, 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.