Гальтон и Ватсон: вымирание фамилий

Задача

Проблема 4001, опубликованная Фрэнсисом Гальтоном в журнале «Educational Times» 1 апреля 1873 года:

Большая нация, из которой нас интересуют только взрослые мужчины числом $N$, каждый со своей фамилией, заселяет область. Закон их размножения таков, что в каждом поколении доля $a_0$ взрослых мужчин не имеет сыновей, доживших до взрослого возраста, доля $a_1$ имеет одного, $a_2$ — двух, и так далее до $a_5$. Найти: (1) какая доля фамилий вымрет через $r$ поколений; (2) сколько будет случаев, когда одну фамилию носят $m$ человек.

Мотив был вполне викторианский: в обществе обсуждали, что знатные роды угасают, и видели в этом признак вырождения элиты. Гальтон, занимавшийся наследственностью (и, увы, евгеникой — биометрическая революция), хотел понять, требует ли явление особого объяснения или это просто арифметика.

Первый присланный ответ (Дж. Карра) Гальтон назвал совершенно ошибочным. Тогда он обратился к другу — преподобному Генри Уильяму Ватсону, математику и священнику.

Метод: производящие функции

Ватсон применил инструмент, который здесь работает идеально.

Определение. Пусть $p_{k}$ — вероятность, что у мужчины ровно $k$ сыновей. Производящая функция:

$$f(s) = \sum_{k=0}^{\infty} p_{k}s^{k}, \qquad |s|\leqslant1.$$

Пусть $Z_n$ — число мужчин в $n$-м поколении, $Z_0=1$, и $f_{n}(s) = E\left[s^{Z_{n}}\right]$.

Ключевая теорема. Производящая функция $n$-го поколения есть $n$-кратная композиция:

$$f_{n}(s) = \underbrace{f(f(\cdots f(s)\cdots))}_{n\ \text{раз}}, \qquad\text{то есть}\qquad f_{n+1}(s) = f_{n}(f(s)) = f(f_n(s)).$$

Почему. Каждый из $Z_n$ членов поколения независимо порождает потомство с функцией $f$. По формуле полной вероятности:

$$f_{n+1}(s) = E\left[s^{Z_{n+1}}\right] = E\left[E\left[s^{Z_{n+1}}\mid Z_{n}\right]\right] = E\left[f(s)^{Z_{n}}\right] = f_{n}\!\left(f(s)\right).$$

Изящество здесь в том, что сложнейший вероятностный вопрос сведён к итерации одной функции — предмету, о котором алгебра кое-что знает.

Вероятность вымирания. Обозначим $\eta_{n} = P(Z_{n}=0) = f_{n}(0)$. Последовательность не убывает, её предел $\eta$ — вероятность вымирания когда-либо, и он удовлетворяет неподвижному уравнению

$$\boxed{\;\eta = f(\eta)\;}$$

Ошибка Ватсона

Уравнение $\eta = f(\eta)$ всегда имеет корень $\eta = 1$, потому что $f(1)=\sum p_k = 1$.

Ватсон нашёл этот корень и заключил, что вероятность вымирания равна единице всегда. Отсюда знаменитый вывод статьи 1875 года: все фамилии обречены исчезнуть, и удивляться тут нечему, ибо утраченная фамилия не может быть восстановлена.

Вывод неверен. Ошибка тонкая и очень поучительная: уравнение может иметь два корня в $[0,1]$, и надо брать наименьший.

Правильный ответ. Пусть $m = f'(1) = \sum k p_{k}$ — среднее число сыновей. Функция $f$ на $[0,1]$ выпукла и возрастает, $f(1)=1$. Поэтому:

• если $m \leqslant 1$ (и $p_1 \ne 1$), график $f$ лежит выше диагонали при $s<1$, единственный корень $\eta=1$: вымирание неизбежно (докритический и критический случай);
• если $m > 1$, график пересекает диагональ ещё раз, в точке $\eta_{0}<1$, и вероятность вымирания равна $\eta_0 < 1$: с положительной вероятностью род продолжается вечно (надкритический случай).

Условие $m>1$ выглядит очевидным задним числом — но именно его Ватсон и упустил.

Численный пример. Пусть $p_0=1/4$, $p_1=1/4$, $p_2=1/2$. Тогда $m = 0\cdot\tfrac14 + 1\cdot\tfrac14+2\cdot\tfrac12 = 1{,}25>1$.

$$f(s)=\tfrac14+\tfrac14 s+\tfrac12 s^{2}, \qquad \eta = \tfrac14+\tfrac14\eta+\tfrac12\eta^{2}.$$

Умножая на 4: $2\eta^{2}-3\eta+1=0$, откуда $\eta = 1$ или $\eta=\tfrac12$. Берём меньший: вероятность вымирания $1/2$. Ватсон ответил бы «1».

Настоящий приоритет

Ирене-Жюль Бьенеме (тот самый, чьё неравенство приписали ЧебышёвуПафнутий Львович Чебышёврусский математик и механик · 1821–1894Основал петербургскую математическую школу, дал первые строгие оценки в законе распределения простых чисел и построил около сорока механизмов, включая шагающую машину., — петербургская школа) поставил и по существу решил ту же задачу в 1845 году, за 28 лет до Гальтона, рассматривая угасание французских дворянских и буржуазных родов. Он опубликовал заметку в бюллетене Философского общества Парижа, причём, судя по формулировкам, знал правильный критерий. Само доказательство утеряно.

Открытие принадлежит Хайду и Сенете (1972), которые нашли заметку Бьенеме, — тем же исследователям, что восстановили его приоритет в неравенстве. Поэтому корректное название процесса — процесс Бьенеме — Гальтона — Ватсона.

Ирония: один и тот же человек дважды потерял приоритет, и оба раза его восстановили одни и те же люди в одной и той же работе. Для линии это готовый сюжет — Бьенеме появляется в точке о петербургской школе и здесь.

Что из этого выросло

• Ядерная физика. Цепная реакция — ветвящийся процесс, где «потомки» — нейтроны, порождённые делением. Критическая масса — это в точности условие $m=1$: при $m<1$ реакция затухает, при $m>1$ идёт вразнос. Расчёты Лос-Аламоса (УламСтанислав Улампольско-американский математик · 1909–1984Раскладывая пасьянс после болезни, придумал метод Монте-Карло — считать вероятность не формулой, а перебором случайных исходов. Заодно ему принадлежит схема, сделавшая водородную бомбу возможной., Хокинс, 1944) опирались прямо на эту теорию.
• Эпидемиология. Базовое репродуктивное число $R_0$ — то же самое $m$. Порог $R_0=1$ разделяет затухание вспышки и эпидемию; вакцинация действует, снижая эффективное $R$ ниже единицы. Прямое продолжение модели Даниила БернуллиБернуллишвейцарская династия математиков · XVII–XVIII векаВосемь математиков в трёх поколениях одной базельской семьи — и почти столько же ссор между ними; на их фамилию приходится закон больших чисел, вариационное исчисление и уравнение гидродинамики..
• Случайные графы. Как показано в точке об Эрдёше и Реньи, фазовый переход при $c=1$ — это буквально критичность ветвящегося процесса.
• Популяционная генетика. Судьба новой мутации в популяции; классические работы Холдейна и ФишераРональд Фишеранглийский статистик и генетик · 1890–1962Придумал почти всё, чем статистика пользуется сегодня, — дисперсионный анализ, рандомизацию, максимум правдоподобия, p-значение, — работая на сельскохозяйственной опытной станции..
• Теория очередей, распространение информации в сетях, каскады отказов.