Les arbres de Galton-Watson

Peut-être vous êtes-vous déjà amusé à reconstituer votre arbre généalogique sur lequel vous avez reporté les noms de vos ancêtres, proches ou lointains. Mais vous êtes-vous déjà demandé à quoi allait ressembler l'arbre de votre descendance ?

L'arbre des ancêtres est très régulier : à chaque génération chaque branche se divise en deux. Autrement dit le nombre d'ancêtres double à chaque génération remontée. (Du moins à condition qu'il n'y ait pas de mariages entre cousins éloignés ce qui fini inévitablement par arriver si on remonte suffisamment loin. :-° ) Un arbre de descendance peut en revanche être beaucoup plus irrégulier car si chacun a deux parents, le nombre d'enfants peut quant à lui beaucoup varier !

Nous allons voir qu'il est possible de décrire mathématiquement ces arbres de descendance. Comme il n'est bien entendu pas possible de prédire l'avenir, ce modèle est un modèle probabiliste, c'est-à-dire qu'il utilise la théorie des probabilités pour évaluer les chances des différents scénarios possibles. Ces arbres aléatoires sont appelés les arbres de Galton-Watson.

Quelques prérequis sont conseillés pour la lecture de ce cours. Tout d'abord il est recommandé d'avoir déjà quelques bases en probabilités ; même si tout est expliqué de zéro, le modèle n'est à mon avis pas le plus simple pour débuter en probas. Ensuite il est préférable de savoir étudier une fonction (dérivée, sens de variation,...) Si ce n'est pas le cas vous pouvez malgré tout suivre ce cours mais vous serez obligé de me faire confiance au moment où ce sera nécessaire. ;) Enfin, à quelques endroits je détaillerais quelques calculs rigoureux qui s'adressent à des étudiants post-bac ayant déjà de bonnes bases en théorie des probabilités. Cependant, ces calculs seront toujours accompagnés d'explications intuitives pour que tout le monde puisse suivre même en sautant les calculs !

Francis Galton

L'histoire des arbres de Galton-Watson commence en 1873 lorsque le scientifique britannique Francis Galton se pose la question de l'évolution des noms de famille des lords anglais. Il s'inquiète de voir certains de ces noms disparaître après que leurs derniers représentants sont morts sans laisser de descendance. Il décide alors de poser sa question dans le journal Educational Times et reçoit peu de temps après une réponse avec la solution du révérend Henry William Watson.

Depuis, les arbres de Galton-Watson (on a donné au modèle le nom de ses deux inventeurs) sont devenus des objets classiques de la théorie des probabilités et ont été étudiés en long en large et en travers avec de nombreuses variantes.

Dans ce mini-cours je vous propose simplement d'étudier le modèle de base de Galton et Watson et de voir comment il est possible de répondre à la question de départ : quelle est la probabilité pour que les noms des lords anglais ne s'éteignent pas. Ou plus généralement la probabilité pour que la descendance d'un individu (vous par exemple ;) ) ne s'éteigne pas.

Bien, il est temps de rentrer dans le vif du sujet : comment définit-on un arbre de Galton-Watson ?

Avant de construire des arbres sur plusieurs générations, nous allons nous concentrer sur le nombre d'enfants d'un seul individu. Évidemment, tout le monde n'a pas le même nombre d'enfants, c'est donc à ce stade qu'il faut faire intervenir les probabilités.

On notera donc $p_n$ la probabilité pour un individu d'avoir $n$ enfants. Ici, $n$ est un entier naturel : il n'est pas possible d'avoir un nombre négatif ou un nombre à virgule d'enfants ! :p Par contre, $n$ peut-être égal à 0 : il est possible de ne pas avoir d'enfants.

En bref, on a une suite de probabilités :

• $p_0$ est la probabilité de ne pas avoir d'enfants ;

• $p_1$ est la probabilité d'avoir un seul enfant ;

• $p_2$ est la probabilité d'avoir deux enfants ;

• $p_3$ est la probabilité d'avoir trois enfants ;

• et cætera.

Si par exemple, on regarde les statistiques des années 1960 en France, on obtient les probabilités suivantes :

$p_0=0,10,~~~~p_1=0,18,~~~~p_2=0,40,~~~~p_3=0,22,~~~~p_4=0,07,~~~~p_5=0,03$.

Ce qui signifie que 10% des gens n'ont pas d'enfants, 18% en ont un, 40% en ont deux, 22% en ont trois, 7% en ont quatre et 3% en ont cinq.

Et alors personne n'avait six enfants ou plus dans les années 60 ?

En réalité si. Mais il s'agit d'une minorité et pour plus de simplicité comme je vais me servir de cet exemple dans tout le cours j'ai préféré arrondir. (Comment ça fainéant ? :-° )

Remarquez que la somme de ces probabilités doit être égale à 1 :

$\sum_{n=0}^{+\infty}p_n =1.$

Si vous ne connaissez pas le signe $\Sigma$, il signifie simplement que la somme de tous les $p_n$ est égale à 1. Si vous voulez en savoir plus sur cette notation et la façon dont on l'utilise vous pouvez lire ce chapitre de mon cours Nombres et opérations.

Le fait que cette somme soit égale à 1 signifie qu'un individu a forcément un nombre entier naturel d'enfants (0, 1, 2, 3, 4,...) Comme je l'ai déjà dit, il n'est pas possible d'avoir un nombre négatif ou à virgule d'enfants.

Si on reprend l'exemple des années 60, on a bien : 0,10+0,18+0,40+0,22+0,07+0,03 =1.

Vous remarquerez dans la formule ci-dessus que la somme des $p_n$ va de 0 jusqu'à... l'infini. Cela signifie que pour ce modèle on a pas besoin de limiter le nombre d'enfants par personne et qu'il est tout à fait possible que $p_n$ soit différent de 0 pour n'importe quel nombre $n$.

Par exemple, on peut très bien avoir pour tout $n$ :

$p_n=\frac{1}{2^{n+1}},$

c'est-à-dire $p_0=1/2$, $p_1=1/4$, $p_2=1/8$, $p_3=1/16$ et ainsi de suite chaque terme étant égal à la moitié du précédent. Cette suite vérifie bien l'égalité :

$\sum_{n=0}^{+\infty}p_n =\sum_{n=0}^{+\infty}\frac{1}{2^{n+1}}=1.$

Évidemment dans l'exemple des années 60 ou dans toute autre situation concrète ça ne sert à rien de faire la somme jusqu'à l'infini puisque les $p_n$ sont nuls à partir d'un certain rang (à partir de 6 dans l'exemple). Cependant comme les mathématiciens n'aiment pas faire les choses à moitié, ils préfèrent considérer le cas général où le nombre d'enfants peut-être aussi grand qu'on veut. :p Vous allez voir que ça ne change strictement rien pour l'étude théorique du modèle.

Maintenant que nous avons défini la loi de natalité, nous pouvons enfin construire nos arbres aléatoires. Pour cela, commençons par poser l'ancêtre commun de notre généalogie, que l'on appelle la racine de l'arbre :

Cet ancêtre va alors engendrer un nombre aléatoire d'enfants. Par exemple, il y a une probabilité $p_2$ pour qu'il ait deux enfants :

Puis chacun de ces deux enfants va à son tour avoir des enfants indépendamment. Par exemple, il y a une probabilité $p_1$ pour que le premier ait un enfant et une probabilité $p_0$ pour que le deuxième n'en ait pas. Il y a donc au total une probabilité $p_0\times p_1$ pour que la deuxième génération de l'arbre soit la suivante :

Ensuite on continue sur le même principe. Il y a une probabilité $p_4$ pour que le seul individu de la deuxième génération ait quatre enfants :

Normalement vous devez commencer à comprendre le principe. Allez, une dernière génération. Il y a une probabilité $p_2 p_1 p_0 p_3$ pour que les quatre individus de la troisième génération aient respectivement 2, 1, 0 et 3 enfants.

Bon, on s'arrête ici, mais bien sûr on pourrait continuer ainsi à construire les différentes générations successivement en calculant leurs probabilités.

Si on récapitule tout, la probabilité que les quatre premières générations de l'arbre de Galton-Watson soient celles de l'exemple ci-dessus est égale à

$(p_2) \times (p_1 p_0) \times (p_4) \times (p_2 p_1 p_0 p_3) = p_0^2 p_1^2 p_2^2 p_3 p_4.$

Et si on calcule cette valeur dans le cas particulier des familles de 1960 donné ci-dessus, on trouve que cet arbre a une probabilité égale à environ 0,0000008 ! Évidemment, c'est minuscule : cela fait environ une chance sur 1250000. Mais ce qu'il faut se dire c'est qu'il y a énormément de scénarios possibles. Il est donc normal que chacun d'entre eux soit peu probable.

Sur quatre générations, il n'est pas possible de trouver un arbre ayant une grande probabilité, ne serait-ce que de 1%. Et c'est encore pire sur 5, 6 ou davantage de générations... :(

Mais alors il est nul ton modèle ! Si l'on ne peut pas savoir ce qui se passe à plus d'une chance sur un million, c'est comme si on ne savait rien du tout de ce qui allait se passer ! Donc en fait on ne peut rien savoir de probable sur les arbres de Galton-Watson ?

Mais si, rassurez-vous, nous allons avoir des résultats intéressants ! :p Le problème vient du fait que nous ne nous sommes pas posé les bonnes questions.

Se demander si tel ou tel scénario précis va se produire est une question beaucoup trop pointue. D'autant que concrètement, ce n'est pas vraiment ce qui nous intéresse.

En revanche, il est beaucoup plus pertinent de se poser des questions qui sont à la fois plus larges et qui ont plus de sens comme « Quelle est la probabilité d'avoir encore des descendants dans 1000 générations ? », « Quelle est la probabilité d'avoir au moins trois petits-enfants ? », ou encore la question originelle de Galton « Quelle est la probabilité pour que ma descendance s'éteigne à un moment donné ? »

Ces questions-là ne demandent pas la probabilité d'un scénario précis, mais la probabilité d'un ensemble de scénarios qui vérifient une propriété donnée. Autrement dit, il s'agit de chercher la somme des probabilités de tous les arbres qui ont cette propriété.

Si on le dit de cette façon, la tâche peut paraître fastidieuse : trouver tous les arbres qui vérifient la propriété voulue, puis calculer leurs probabilités et les additionner. Rassurez-vous, ce n'est pas comme cela que l'on va procéder ! Il existe des méthodes bien plus élégantes et efficaces, comme nous allons le voir dans la deuxième partie de ce cours.

Bien, alors maintenant que nous avons posé le modèle, nous allons pouvoir rentrer dans le vif du sujet : l'étude des propriétés générales de l'arbre. Autrement dit, c'est à partir de maintenant qu'on va commencer à faire des calculs. :-°

On sait que le nombre d'enfants d'un individu est aléatoire, oui mais combien en a-t-il en moyenne ?

Voilà une bonne question ! Si on ne peut pas donner précisément le nombre d'enfants, on peut toujours en donner la moyenne, ou en vocabulaire probabiliste, l'espérance qui se note avec la lettre $\mathbb{E}$.

Si vous êtes déjà un habitué des probabilités, cette question ne doit pas vous faire peur et la réponse est immédiate :

$\mathbb{E}\left[\text{nombre d'enfants d'un individu}\right] = \sum_{n=0}^{\infty}n p_n.$

Si au contraire cette formule n'a rien d'évident pour vous, voyons pourquoi elle est vraie en nous penchant sur l'exemple des années 60. Prenons un échantillon de 100 personnes. D'après les probabilités données au début de ce cours, on sait qu'en moyenne sur ces 100 personnes :

• 10 auront 0 enfant ;

• 18 auront 1 enfant ;

• 40 auront 2 enfants ;

• 22 auront 3 enfants ;

• 7 auront 4 enfants ;

• 3 auront 5 enfants.

Par conséquent, le nombre moyen d'enfants de ces 100 personnes réunies est égal à

$0\times 10 + 1 \times 18 + 2\times 40 + 3\times 22 + 4\times 7+ 5\times 3.$

Et pour obtenir le nombre moyen d'enfants d'un seul individu, il reste à diviser ce nombre par 100. On trouve donc :

$\frac{0\times 10 + 1 \times 18 + 2\times 40 + 3\times 22 + 4\times 7+ 5\times 3}{100}=0\times \frac{10}{100} + 1 \times \frac{18}{100} + 2\times \frac{40}{100} + 3\times \frac{22}{100} + 4\times \frac{7}{100}+ 5\times \frac{3}{100}.$

On remarque alors que les fractions correspondent aux probabilités $p_0$, $p_1,$$p_2$, $p_3$, $p_4$ et $p_5$. Le nombre moyen d'enfants d'un individu est donc égal à

$0\times p_0 + 1 \times p_1 + 2\times p_2 + 3\times p_3 + 4\times p_4+ 5\times p_5.$

Cette formule s'arrête à $5\times p_5$, car dans l'exemple le nombre d'enfants ne peut pas être supérieur à 5 mais vous comprenez que dans le cas général, il faut prolonger la formule par $6\times p_6$, $7 \times p_7$, et cætera. La formule générale est donc bien celle annoncée :

$\mathbb{E}\left[\text{nombre d'enfants d'un individu}\right] = \sum_{n=0}^{\infty}n p_n.$

Comme ce nombre va nous être très utile par la suite nous allons lui donner un nom : $m$. On pose donc

$m:=\sum_{n=0}^{\infty}n p_n.$

Si on finit le calcul ci-dessus pour l'exemple des années 60, on trouve $m=2,07$.

Que se passe-t-il pour les générations suivantes ? Combien en moyenne un individu a-t-il de petits-enfants, d'arrière-petits-enfants, d'arrière-arrière-petits-enfants, ...?

De façon intuitive on peut répondre à cette question de la manière suivante : un individu a $m$ enfants en moyenne et chacun de ces enfants a à son tour $m$ enfants. L'individu de départ a donc en moyenne $m\times m = m^2$ petits-enfants.

Puis chacun de ces $m^2$ petits-enfants va avoir en moyenne $m$ enfants, d'où on déduit que notre individu va avoir $m^3$ arrière-petits-enfants. Et ainsi de suite, on comprend qu'en raisonnant de la sorte, l'ancêtre aura en moyenne $m^k$ descendants à la $k$ème génération.

Le raisonnement que nous venons de faire est tout à fait correct. Cependant en mathématiques il est toujours préférable de vérifier par un calcul rigoureux (d'autant que la théorie des probabilités regorge de pièges qui semblent à première vue contraires à l'intuition et au bon sens).

Le calcul suivant s'adresse plutôt à des étudiants post-bac qui ont déjà de bonnes bases en théorie des probabilités. Si vous...