The Galton-Watson process probabilistic model was developed by Sir Francis Galton (who proposed the problem) and the Rev. Henry William Watson (who solved it) in their study of the extinction of English surnames. The same model is also commonly known as a "branching process". Despite its classical structure and the elementary derivations of its basic theorems, it, along with Markov processes, is one of the fundamental models of modern probability theory.
Galton asked the question if every surname would eventually become extinct. He knew that some surnames were no longer borne by anyone, others ("Smythe") were somewhat scarce, and still others ("Smith") were hugely popular. Would all surnames eventually become extinct? Assuming new surnames are invented ("Sting" might become one) or imported ("Singh") (or both ("Scolnicov")), it is conceivable that every surname would eventually become extinct, without the human race (synonymous, of course, with the English) becoming extinct.
Assuming traditional usage, in propagating a surname only male scions count (the women, good Victorians that they undoubtably are, will either adopt their husband's surname and have children or keep their maiden name and remain childless; note, however, that we may easily adapt the parameters of the model to suit other more modern circumstances). We need to trace the number of male descendents of a given male individual ("ur-Smith"?) to determine what happens to his surname. Note that this is a random tree: the root is Mr. ur-Smith, its sons are his sons, and so on.
Watson and Galton assumed this model for the offspring of a given male x: Let the random variable Zx be the number of sons of x.
So here's how we build our process:
- Procure an infinite supply of IID random variables Z1, Z2, ...
- Start with Mr. ur-Smith; he has Z1 sons.
- Son #1 of Mr. ur-Smith shall have Z2 sons; son #2 shall have Z3; ...; son #Z1 shall have ZZ1+1.
- The Z2 sons of son #1 will have ZZ1+2, ..., ZZ1+Z2+1 sons, respectively.
- Continue in this manner.
Obviously,
despite general nastiness in computing the indices, we can construct Mr. ur-Smith's
lineage in this manner, and satisfy the above 2 properties.
The Smith family name will become extinct if at some generation there are no further sons. Obviously, if P(Z1=0)=0 (the probability of having no sons is 0) then this will never happen. If, on the other hand, we allow for the possibility of having 0 sons, then there is always a positive probability of extinction: ur-Smith himself could have 0 sons, or even (with very low probability) once there are 1000000 Smiths, all will have 0 sons. But can we say something better?
Galton and Watson showed the following: Let μ(D)=EZ1 (=EZn, for all n) be the expected number of sons of any Smith.
- The expected number of Smiths at generation k is μ(D)k.
- If μ(D) > 1, then with positive probability the Smith surname shall live on (for ever).
- If μ(D) < 1, then almost always (i.e. with probability 1) the Smith surname will die out.
- If μ(D) = 1, then either all Z's are (almost always) constantly 1, in which case there will almost always be precisely 1 Smith in every generation, and the Smith surname will live on forever, or Z's are not constants, in which case almost always the Smith surname will die out.
The case μ(D)=1 is the most interesting, of course.
Today, Galton-Watson processes are employed as a basic probabilistic model in many fields. First, we can use it to describe populations (biological and other) for more characteristics than just their surname. Note, however, that as the model allows for unbounded growth of the population, it might not be realistic in many situations.
These processes are also used in other fields in Probability. In percolation, for instance, any percolation on a tree is a Galton-Watson process, and can be analysed accordingly. For graphs with cycles, we can still use Galton-Watson processes which dominate their percolation, to derive useful results.