\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection, NoEqCountersInSection,published]{cedram} \usepackage{xups16-01} \setcounter{tocdepth}{2} %\XUPScorrections \graphicspath{{xups16-01_figures}} \let\subsection\Subsection \hyphenation{géné-ra-tion géné-ra-tions par-ti-cu-lier} \datepublished{2024-08-06} \begin{document} \frontmatter \title{Arbres et marches aléatoires} \author[\initial{I.} \lastname{Kortchemski}]{\firstname{Igor} \lastname{Kortchemski}} \address{CNRS \& CMAP, École polytechnique, Université Paris-Saclay} \email{igor.kortchemski@normalesup.org} \urladdr{http://www.normalesup.org/~kortchem/} \thanks{Journées X-UPS 2016. Arbres et marches aléatoires. Éditions de l'École polytechnique, 2016} \begin{abstract} Nous nous intéressons à de grands arbres aléatoires qui décrivent la généalogie d'une population se reproduisant de manière asexuée. Ce modèle a été introduit à la fin du \textsc{xix}\ieme siècle par Bienaymé et Galton \& Watson pour prédire l'extinction des noms nobles en Angleterre. En n'utilisant essentiellement que des outils au programme des classes préparatoires scientifiques, nous étudions la géométrie de ces arbres en les codant par des marches aléatoires conditionnées, que nous analysons à leur tour en utilisant des arguments combinatoires et analytiques. \end{abstract} \maketitle \begin{figure}[htb] \begin{center} \includegraphics[scale=0.5]{stable2.pdf} \caption{\label{fig:stable2}Un grand arbre de Bienaymé-Galton-Watson aléatoire.} \end{center} \end{figure} \tableofcontents \mainmatter \section{Introduction et objectifs} De manière informelle, considérons l'évolution d'une population issue d'un ancêtre, où chaque individu meurt en donnant naissance à un nombre aléatoire d'enfants distribué selon une probabilité fixée $\mu$ (c'est-à-dire que la probabilité d'avoir $i$ enfants est $\mu(i)$), indépendamment des autres individus. Le but de ce texte est d'étudier la structure de l'arbre (planaire et enraciné) généalogique associé, appelé \emph{arbre de Bienaymé-Galton-Watson}, en particulier quand celui-ci est grand, et de donner quelques applications intéressantes. À cet effet, nous n'utiliserons essentiellement que des outils au programme des classes préparatoires scientifiques et n'admettrons pas de résultats délicats. Par exemple, avec des outils probabilistes, nous démontrerons (Corol\-laire \ref{cor:Poisson}) que pour tout $\lambda>0$, $$ \sum_{n \geq 1} \frac{(\lambda n)^{n-1} e^{-\lambda n}}{n!} = \begin{cases} 1 & \textrm{si } \lambda \leq 1\\ s & \textrm{si } \lambda>1, \textrm{ où } s \in{} ]0,1[ \textrm{ vérifie } s=e^{\lambda (s-1)}. \end{cases}$$ Nous verrons que dans un arbre généalogique typique (en un sens qui sera précisé ultérieurement) à $n$ individus, environ la moitié d'individus n'ont pas d'enfants (théorème \ref{thm:feuilles}) et le nombre maximal d'enfants est d'ordre $\log_{2}(n)$. Les techniques développées permettront également de répondre à la Question 809 du numéro 124-1 de la RMS (Exem\-ple~\ref{ex:RMS}). Dans le paragraphe \ref{sec:historique}, nous commençons par présenter un historique et des motivations. Nous verrons en particulier que ces questions s'inscrivent dans la théorie plus générale des limites d'échelles de structures discrètes aléatoires, avec des liens très étroits avec des thématiques de recherche actuelles. Le paragraphe \ref{sec:arbres} donne une définition précise des différents objets considérés, et commence par donner une condition nécessaire et suffisante sur la loi de reproduction $\mu$ qui garantit l'extinction presque sûre de la population. Le paragraphe \ref{sec:codage} introduit la technique la plus importante dans l'étude des arbres de Bienaymé-Galton-Watson, qui est leur codage par des marches aléatoires, dont les propriétés sont généralement bien comprises. Le paragraphe \ref{sec:outils} présente deux outils pour étudier ces marches aléatoires. Le premier outil, le lemme cyclique (théorème \ref{thm:lemmecyclique}), est un joli résultat élémentaire de nature combinatoire. Le deuxième outil, le théorème local limite (théorème \ref{thm:ll}), est un résultat analytique qui implique le théorème central limite. Le paragraphe \ref{sec:applications} combine les paragraphes \ref{sec:codage} et \ref{sec:outils} pour donner des applications concernant la structure d'arbres de Bienaymé-Galton-Watson conditionnés à avoir un grand nombre fixe de sommets.\enlargethispage{\baselineskip}% Finalement, le paragraphe \ref{sec:modeles} présente plusieurs structures discrètes aléatoires qui se révèlent être intimement liées à des arbres de Bienaymé-Galton-Watson, ce qui permet de les étudier en utilisant des résultats déjà connus sur les arbres. \section{Historique et motivations} \label{sec:historique} \subsubsection*{Au début furent les processus de Bienaymé-Galton-Watson} Les prémices des processus de Bienaymé-Galton-Watson remontent au milieu du \textsc{xix}\ieme siècle, où ils sont introduits afin d'estimer la probabilité d'extinction de noms de familles nobles. En 1875, Galton \& Watson \cite {GW75} proposent une approche fondée sur des méthodes de fonctions génératrices. Si la méthode est judicieuse, une erreur s'est glissée dans leur travail (ils concluent que la probabilité d'extinction vaut toujours $1$, voir \cite[Chap.\,9]{Bac11}), et il faut attendre 1930 pour que Steffensen \cite {Ste30} publie une solution complète. Cependant, en 1972, Heyde \& Seneta \cite{HS72} découvrent une note de Bienaymé \cite{Bie45} datant de 1845, où Bienaymé énonce correctement que la probabilité d'extinction vaut $1$ si la moyenne de la loi de reproduction est inférieure à $1$, avec quelques explications, mais sans preuve publiée. Il semble cependant très plausible que Bienaymé ait également trouvé la preuve en utilisant les fonctions génératrices (voir \cite {Kend75} et \cite[Chapitre 7]{Bac11} pour une étude historique détaillée). Dès lors, le comportement asymptotique des processus de branchement en temps grand a suscité de nombreux travaux; nous renvoyons aux ouvrages \cite[\oldS\,12]{LP10} et \cite {AN72} pour un descriptif des résultats en ce sens. \subsubsection*{La naissance de l'arbre brownien} À partir de la deuxième moitié du \textsc{xx}\ieme siècle, différentes communautés se sont intéressées au compor\-te\-ment asymptotique d'arbres aléatoires tirés uniformément au sein d'une certaine classe ou bien conditionnés \og à être grands \fg, en étudiant certaines de leurs caractéristiques. Aux frontières de la combinatoire et de l'informatique, en utilisant des méthodes de fonctions génératrices et de combinatoire analytique, diverses statistiques de ces arbres aléatoires ont été considérées, comme le degré maximal, le nombre de sommets de degré fixé ou encore le profil de l'arbre. Nous renvoyons à l'ouvrage \cite{Drm09} pour un traitement détaillé. \begin{figure}[htb] \centering %%% L'ARBRE \begin{scriptsize} \begin{tikzpicture}[scale=.7] \coordinate (0) at (0,0); \coordinate (1) at (-1.5,1); \coordinate (11) at (-1.5,2); \coordinate (2) at (0,1); \coordinate (21) at (0,2); \coordinate (3) at (1.5,1); % \draw (0) -- (1) -- (11) (0) -- (2) -- (21) (0) -- (3) % ; \draw[fill=black] (0) +(-3pt,-3pt) rectangle +(3pt,3pt) (1) circle (1pt) (2) circle (1pt) (3) circle (1pt) (11) circle (1pt) (21) circle (1pt) ; % % Labels \end{tikzpicture} \qquad \begin{tikzpicture}[scale=.7] \draw[thin,dotted, ->] (0,0) -- (5.5,0); \draw[thin,dotted, ->] (0,0) -- (0,2.5); \coordinate (0) at (0,0); \coordinate (1) at (0.5,1); \coordinate (2) at (1,2); \coordinate (3) at (1.5,1); \coordinate (4) at (2,0); \coordinate (5) at (2.5,1); \coordinate (6) at (3,2); \coordinate (7) at (3.5,1); \coordinate (8) at (4,0); \coordinate (9) at (4.5,1); \coordinate (10) at (5,0); % \draw (0) -- (1) -- (2)--(3)--(4)--(5)--(6)--(7)--(8)--(9)--(10) ; \end{tikzpicture} \end{scriptsize} \quad \includegraphics[scale=0.3]{excursion.pdf} \caption{\label{fig:contour}De gauche à droite: un arbre avec $6$ sommets, sa fonction de contour associée, puis la fonction de contour (convenablement renormalisée en temps et en espace) d'un grand arbre de Bienaymé-Galton-Watson (de loi de reproduction critique et de variance finie), qui converge en loi vers l'excursion brownienne.} \end{figure} Au début des années 1990, au lieu de n'analyser que des propriétés spécifiques, Aldous a eu l'idée d'étudier la convergence de grands arbres aléatoires (enracinés et ordonnés, voir le paragraphe~\ref{sec:def} pour une définition) dans leur globalité. Plus précisément, Aldous \cite {Ald91a} a expliqué comment voir des arbres aléatoires comme des sous-ensembles compacts aléatoires de l'espace $\ell_1$ des suites sommables, et a prouvé dans ce cadre qu'un arbre de Bienaymé-Galton-Watson dont la loi de reproduction est une loi de Poisson de paramètre $1$, conditionné à avoir $n$ sommets, converge, lorsque $n \rightarrow \infty$, vers un sous-ensemble compact aléatoire qu'il a appelé \emph{Continuum Random Tree}, abrégé en CRT en anglais. Un peu plus tard, Aldous \cite {Ald91,Ald93}, a proposé une construction simple du CRT à partir de l'excursion brownienne normalisée $ \mathbbm{e}$ (qui peut être informellement vue comme le mouvement brownien conditionné à revenir en $0$ à l'instant $1$ et à rester positif sur $[0,1]$), et a démontré que la fonction de contour (voir figure~\ref{fig:contour}) renormalisée d'un arbre de Bienaymé-Galton-Watson de loi de reproduction critique (c'est-à-dire de moyenne $1$) et de variance finie, conditionné à avoir $n$ sommets, converge (en loi, dans l'espace des fonctions continues de $[0,1]$ dans $\R$ muni de la topologie de la convergence uniforme), lorsque $n \rightarrow \infty$, vers $ \mathbbm{e}$. Pour cette raison, le CRT est généralement appelé \emph{arbre brownien}, et apparaît ainsi comme un objet limite \emph{universel}, en ce sens que des $ \GW$ arbres de lois de reproduction différentes convergent vers le même objet continu (voir figure~\ref{fig:stable2} pour une représentation d'un grand arbre de Bienaymé-Galton-Watson de loi de reproduction critique et de variance finie). Précisons que l'hypothèse de variance finie, réminiscente du théorème central limite, est cruciale. En 2003, Evans, Pitman \& Winter \cite {EPW06} suggèrent d'utiliser le formalisme des $ \R$-arbres, introduits auparavant à des fins géométriques et algébriques (voir par exemple \cite {Pau89}), et de la topologie de Gromov-Hausdorff, introduite par Gromov \cite {Gro81b} pour démontrer ce qui est connu sous le nom de théorème de Gromov sur les groupes à croissance polynomiale. La distance de Gromov-Hausdorff définit une topologie sur les espaces métriques compacts (vus à isométrie près), ce qui permet de donner un sens à la notion de convergence d'espaces métriques compacts. Ce point de vue, consistant à voir des arbres comme espaces métriques compacts (en équipant simplement l'ensemble de leurs sommets de la distance de graphe) et à étudier leurs limites d'échelle, est maintenant largement utilisé et a permis de donner un cadre naturel et efficace pour étudier des convergences abstraites de graphes aléatoires (qui ne sont pas nécessairement codés par une fonction de type excursion). On parle de \emph{limite d'échelle} lorsqu'on s'intéresse aux limites de grands objets discrets dans leur ensemble après renormalisation.\enlargethispage{\baselineskip}% \subsubsection*{Arbres de Lévy stables} Un pas important a été franchi dans la généralisation des résultats d'Aldous par Le Gall \& Le Jan \cite {LGLJ98} qui ont entre autres étudié un cas particulier de loi de reproduction $\mu$ critique mais de variance infinie: celui où $\mu$ est à queue lourde (la probabilité d'avoir au moins $n$ enfants décroît comme $n^{-\theta}$ lorsque $n \rightarrow \infty$, avec $\theta \in (1,2]$). Il a été démontré \cite {DLG02,Du03,DLG05} que dans ce cas, un arbre de Bienaymé-Galton-Watson de loi de reproduction $\mu$, conditionné à avoir $n$ sommets, converge vers un autre arbre continu limite: l'arbre stable d'indice $\theta$, qui possède des sommets de grands degrés (voir figure~\ref{fig:stables} pour des simulations). \begin{figure}[htb] \begin{center} \includegraphics[scale=0.4]{stable11.jpg} \includegraphics[scale=0.41]{stable15.jpg} \caption{\label{fig:stables}En haut: une simulation d'un arbre stable d'indice $\theta=1.1$ ; en bas: une simulation d'un arbre stable d'indice $\theta=1.5$ (plus $\theta$ est petit, plus les individus ont tendance à avoir davantage d'enfants, ce qui explique l'impression de voir des degrés plus grands lorsque $\theta$ est plus petit).} \end{center} \end{figure} Les arbres stables (en particulier d'indice $\theta=3/2$) jouent un rôle important dans la théorie des limites d'échelle de grandes cartes planaires aléatoires \cite{Kri05,CK13+,MS15}, dont une motivation est de donner un sens à la notion de \og surface deux-dimensionnelle canonique\fg\ \cite{LeGallICM} (voir figure~\ref{fig:cartejoli}). \begin{figure}[htb] \begin{center} \includegraphics[scale=0.07]{chevre.jpg} \caption{\label{fig:cartejoli}Simulation d'une grande triangulation aléatoire de la sphère (due à Nicolas Curien).} \end{center} \end{figure} \subsubsection*{Autres types de conditionnements} Des conditionnements faisant intervenir d'autres quantités que le nombre total de sommets ont été considérés en vue de différentes applications. L'étude asymptotique d'arbres de Bienaymé-Galton-Watson conditionnés à avoir une hauteur au moins $n$ a été initiée par Kesten \cite {Kes86}. Le conditionnement à avoir une hauteur $n$, plus délicat, a été étudié dans \cite {GK99,LG10}. D'autres types de conditionnements faisant intervenir des degrés particuliers ont récemment fait l'objet de plusieurs travaux. Ainsi, Rizzolo \cite {Riz15} a introduit le conditionnement à avoir un nombre fixé d'individus dont le nombre d'enfants appartient à un sous-ensemble fixé de~$ \N^*$, tandis que Broutin \& Marckert \cite{BM14} et Addario-Berry \cite{Add12} considèrent des arbres aléatoires ayant une suite fixée de degrés. \subsubsection*{Arbres de Bienaymé-Galton-Watson non génériques} L'étude des arbres de Bienaymé-Galton-Watson conditionnés non critiques se ramenant souvent au cas critique (voir paragraphe \ref {sec:exp}), les lois de reproduction non critiques ont été longtemps délaissées, et ce n'est que très récemment que Jonsson \& Steffánsson \cite {JS11} ont approfondi le cas où on ne peut pas se ramener à une loi de reproduction critique, cas appelé non-générique. Jonsson \& Steffánsson s'intéressent aux limites locales d'arbres de Bienaymé-Galton-Watson non-génériques conditionnés, et d'autres travaux \cite {Jan12,AD14b,Kor15} ont poursuivi cette étude. Dans le cas où la loi de reproduction est sous-critique et possède une queue lourde (la probabilité d'avoir $n$ enfants décroît comme $n^{-\theta-1}$ lorsque $n \rightarrow \infty$, avec $\theta >1$), un nouveau phénomène survient dans un tel arbre de Bienaymé-Galton-Watson conditionné à avoir un nombre fixe de sommets: il apparaît un unique sommet dont le degré est macroscopique d'ordre $n$ (et tous les autres degrés sont beaucoup plus petits). On parle de \emph{condensation}, voir figure~\ref{fig:condensation}. De tels arbres non génériques avec condensation apparaissent également dans le codage de certaines familles de cartes aléatoires \cite{CK13+,SS15,Add15} (voir le paragraphe~\ref{sec:cartes} pour un exemple). \begin{figure}[htb] \begin{center} \includegraphics[scale=0.3]{nongeneric.pdf} \caption{\label{fig:condensation}Un grand arbre de Bienaymé-Galton-Watson avec phénomène de condensation.} \end{center} \end{figure} \subsubsection*{Universalité de l'arbre brownien} Dans les toutes dernières années, plusieurs travaux ont établi que l'arbre brownien est également la limite d'échelle de différentes classes d'arbres aléatoires non planaires \cite{HM12,PS15}, mais aussi de modèles de graphes aléatoires qui ne sont pas des arbres, comme les triangulations en pile \cite{AM08}, les dissections aléatoires \cite{CHK14}, des quadrangulations aléatoires de la sphère avec un grand bord \cite{Bet15}, des graphes planaires extérieurs \cite{Car14}, des cartes aléatoires planaires biparties avec une face de degré macroscopique \cite{SS15} ou encore des graphes sous-critiques \cite{PSK14}. \section{Arbres de Bienaymé-Galton-Watson} \label{sec:arbres} Avant de considérer l'arbre généalogique de l'évolution de la popu\-lation mentionnée dans l'Introduction, nous allons commencer par étudier le comportement du nombre d'individus à génération $1$, puis à génération $2$, et ainsi de suite. \subsection{Processus de Bienaymé-Galton-Watson} Soit $\mu=(\mu(i): i \geq 0)$ une probabilité sur $\N = \{0,1,\ldots \} $ telle que $\mu(0)+\mu(1)<1$. Considérons une suite $(X_{j}^{(n)})_{j,n \geq0}$ de variables aléatoires indépendantes de même loi $\mu$ (définies sur le même espace de probabilité). On définit de manière récursive la suite $(Z_{n}: n \geq 0)$, appe\-lée \emph{processus de Bienaymé-Galton-Watson de loi de reproduction~$\mu$}, comme suit: $$Z_{0}=1, \qquad \textrm{et pour tout } n \geq 0, \quad Z_{n+1}= \sum_{j=1}^{Z_{n}} X_{j}^{(n)}.$$ Ainsi, $Z_{n}$ modélise le nombre d'individus à la $n$-ième génération d'une population qui part d'un ancêtre et où les individus meurent en donnant naissance à un nombre aléatoire d'enfants distribué suivant la loi $\mu$, indépendamment les uns des autres. Posons $m= \sum_{i \geq 0} i \mu(i) \in{}]0,\infty]$. Le résultat suivant montre que $m \leq 1$ si et seulement si la population s'éteint avec probabilité $1$. \begin{thm}\label{thm:extinction}Avec probabilité $1$, il existe $n \geq 0$ tel que $Z_{n}=0$ si et seulement si $m \leq 1$. \end{thm} \begin{proof}Tout d'abord, remarquons que $Z_{n}$ ne se calcule en n'utilisant que les variables $X_{k}^{(j)}$ telles que $1 \leq j \leq n-1$ et $k \geq 1$, c'est-à-dire qu'il existe une fonction (déterministe) $f_{n}$ telle que \begin{equation} \label{eq:Zn}Z_{n}=f_{n} \bigl( (X^{(j)}_{k}: 1 \leq j \leq n-1,\, k \geq 1) \bigr). \end{equation} Ceci se démontre aisément par récurrence sur $n$. Introduisons maintenant la fonction génératrice $\phi$ de $\mu$: $\phi(z)=\sum_{n \geq 0} \mu(n) z^{n}$, qui est une série entière de rayon de convergence au moins égal à $1$, avec $\phi(0)=\mu(0)$ et $\phi(1)=1$. \subsubsection*{Première étape} On a pour tout $0 \leq s <1$: $$ \phi'(s) = \sum_{i = 1}^{\infty} i \mu(i) s^{i-1}, \qquad \phi''(s)=\sum_{i=2}^{\infty} i (i-1) \mu(i) s^{i-1}.$$ Ainsi $\phi'$ et $\phi$ sont strictement croissantes (on utilise ici le fait que $\mu(0)+\mu(1)<1$ pour $\phi'$). \subsubsection*{Deuxième étape} Introduisons, pour $n \geq 1$ et $0 \leq s \leq 1$, \[ \phi_{n}(s)= \Esb{s^{Z_{n}}}=\sum_{k \geq 0} \Pr{Z_{n}=k} s^{k} \] (ainsi $\phi_{1}=\phi$). Nous allons vérifier que \begin{equation} \label{eq:rec}\phi_{n+1}(s)=\phi_{n}(\phi(s)). \end{equation} En effet, écrivons \begin{align*} \phi_{n+1}(s)&= \EsB{s^{\sum_{j=1}^{Z_{n}} X_{j}^{(n)}}}=\Esbb{s^{\sum_{j=1}^{Z_{n}} X_{j}^{(n)}} \biggl( \sum_{\ell \geq 0} \mathbbm{1}_{Z_{n}=\ell} \biggr) } \\ &= \sum_{\ell \geq 0} \EsB{s^{\sum_{j=1}^{\ell} X_{j}^{(n)}} \mathbbm{1}_{Z_{n}=\ell}}\\ &=\sum_{\ell \geq 0} \Esbb{s^{\sum_{j=1}^{\ell} X_{j}^{(n)}} \mathbbm{1}_{ f_{n} \bigl( (X^{(j)}_{k}: 1 \leq j \leq n-1, k \geq 1) \bigr)=\ell}}\\ &=\sum_{\ell \geq 0} \EsB{s^{\sum_{j=1}^{\ell} X_{j}^{(n)}}} \EsB{\mathbbm{1}_{ f_{n} \bigl( (X^{(j)}_{k}: 1 \leq j \leq n-1, k \geq 1) \bigr)=\ell}} \end{align*} car les deux vecteurs $( X_{j}^{(n)})_{1 \leq j \leq \ell}$ et $ (X^{(j)}_{k})_{1 \leq j \leq n-1, k \geq 1}$ sont indépendants. En utilisant le fait que les variables aléatoires $( X_{j}^{(n)})_{1 \leq j \leq \ell}$ sont indépendantes et de même loi $\mu$, on en déduit que $$ \phi_{n+1}(s)=\sum_{\ell \geq 0} \EsB{s^{X_1^{(1)}}}^{\ell} \Pr{Z_{n}=\ell}=\sum_{\ell \geq 0} \phi(s)^{\ell} \Pr{Z_{n}=\ell} = \phi_{n}(\phi(s)).$$ \subsubsection*{Troisième étape} Notons $q= \Pr{ \exists n \geq 1: Z_{n}=0}$ la probabilité d'extinction de la population. Comme les événements $ \{Z_{n}=0\}$ sont croissants pour l'inclusion, on a par propriété de limite croissante $$q=\PrB{ \bigcup_{n \geq 0} \{Z_{n}=0\} }= \lim_{n \rightarrow \infty} \Pr{Z_{n}=0}= \lim_{n \rightarrow \infty} \phi_{n}(0).$$ \subsubsection*{Quatrième étape} Il s'agit donc d'étudier la limite de $\phi_{n}(0)$ lorsque $n \rightarrow \infty$. Comme $\phi$ est continue sur $[0,1]$ (par exemple d'après le théorème d'Abel radial), la relation \eqref{eq:rec} montre que $ q$ est un point fixe de $\phi$. Posons $h(s)=\phi(s)-s$ pour $s \in [0,1]$. \subsubsection*{Premier cas: $m \leq 1$} Alors $h'(s)= \phi'(s)-1 < \phi'(1)-1 =m-1\leq 0$ par croissance stricte de $\phi'$. Par suite, $h$ est strictement décroissante sur $[0,1]$ et $h(1)=0$. Donc $\phi(s)>s$ pour tout $s \in [0,1[$. Ainsi, $\phi$ ne possède qu'un point fixe qui est $1$, et $q=1$. \subsubsection*{Deuxième cas: $m>1$} Alors $h'(1)=m-1>0$ (avec peut-être même $h'(1)=+\infty$). De plus $h$ est strictement convexe sur $[0,1]$ (car $h''=\phi''$ est strictement positive sur $[0,1]$), $h(0)=\mu(0)>0$ et $h(1)=0$. Il~existe donc un unique $r \in{}]0,1[$ tel que $h(r)=r$, c'est-à-dire $\phi(r)=r$. En effet, puisque $h'(1)>0$, il existe $\epsilon \in{}]0,1[$ tel que $h(1-\epsilon)<0$. D'après le théorème des valeurs intermédiaires ($h$~est continue), il existe $r \in [0, 1-\epsilon]$ tel que $h(r)>0$. Puisque $h$ est strictement convexe, $h<0$ sur $(r,1)$ et $h>0$ sur $(0,r)$. En conclusion, nous avons montré que si $m \leq 1$, alors la probabilité d'extinction $q$ vaut $1$, et si $m>1$, alors la probabilité d'extinction~$q$ est égal au plus petit point fixe de $\phi$, qui est strictement inférieur à~$1$. \end{proof} \begin{rem}L'hypothèse $\mu(0)+\mu(1)<1$ est là pour mettre de côté les cas dégénérés (par exemple, on a $Z_{n}=1$ pour tout $n \geq 0$ dans le cas $\mu(1)=1$). \end{rem} \begin{ex}Si $\mu$ suit une loi de Poisson de paramètre $\lambda>0$, un processus de Bienaymé-Galton-Watson de loi de reproduction $\mu$ s'éteint avec probabilité $1$ si et seulement si $\lambda \leq 1$ (car l'espérance d'une loi de Poisson de paramètre $\lambda$ vaut $\lambda$). \end{ex} \begin{rem}\label{rem:poptotale}Dans le cas $m=1$, on voit aisément que $\Es{Z_{n}}=1$ pour tout $n \geq 0$. Ainsi, si $N=\sum_{n \geq 0} Z_{n}$ désigne la population totale, on voit que $N<\infty$ presque sûrement (car le processus s'éteint avec probabilité $1$), mais que $\Es{N}=\sum_{n \geq 0} \Es{Z_{n}}=\infty$. \end{rem} \begin{ex}Considérons un arbre binaire infini et soit $p \in (0,1)$ un nombre fixé. On garde chaque arête avec probabilité $p$, et on l'enlève avec probabilité $1-p$, indépendamment des autres arêtes. Quelle est la probabilité qu'il existe un chemin infini partant de l'origine? Si on note $Z_{n}$ le nombre de sommets à hauteur $n$ accessibles par des arêtes gardées depuis l'origine, on voit que $(Z_{n})_{n \geq 0}$ a la même loi qu'un processus de Bienaymé-Galton-Watson de loi de reproduction une loi binomiale de paramètres $(2,p)$, qui a donc pour moyenne $2p$ et fonction génératrice $\phi(s)=(1-p)^{2}+2p(1-p)s+p^{2} s^{2}$. Ainsi, lorsque $p \leq 1/2$, la probabilité qu'il existe un chemin infini partant de l'origine est nulle, et lorsque $p>1/2$, elle est égale à $ \frac{2p-1}{p^{2}}$ (car d'après le théorème \ref{thm:extinction} elle vaut $1-s$, où $s \in [0,1]$ est la plus petite solution positive de $\phi(s)=s$, qui est $(1-p)^{2}/p^{2}$). \end{ex} \begin{defn} Si $\mu$ une probabilité sur $\N$ telle que $\mu(0)+\mu(1)<1$, on dit que $$\mu \text{ est } \begin{cases} \emph{sous-critique}\\ \emph{critique}\\ \emph{sur-critique} \end{cases} \quad\text{si}\quad\sum_{i \geq 0} i \mu(i) \begin{cases} {}< 1,\\ {} = 1, \\ {} > 1. \end{cases} $$ La terminologie de \emph{criticalité} provient du fait que la probabilité d'extinction présente une transition de phase lorsque $\sum_{i \geq 0} i \mu(i)$ passe d'une valeur inférieure à $1$ à une valeur supérieure à $1$. \end{defn} Nous allons maintenant donner un cadre formel qui permette d'étudier non seulement les tailles des générations, mais également la structure généalogique sous-jacente. \subsection{Arbres plans enracinés} \label{sec:def} Nous suivons le formalisme introduit par Neveu \cite {Nev86} pour défi\-nir les arbres ordonnés enracinés. On désigne par $\mathcal{U}$ l'ensemble des \emph {étiquettes}: $$\mathcal{U}=\bigcup_{n=0}^{\infty} (\N^*)^n,$$ où, par convention, $(\N^*)^0=\{\emptyset\}$. Ainsi, un élément de $\mathcal{U}$ est une suite $u=u_1 \cdots u_j$ d'entiers strictement positifs. Par définition, la~\emph{génération} (ou \emph{hauteur}) de $u=u_1 \cdots u_j$, notée $|u|$, est l'entier $j$. Lorsque $u=u_1 \cdots u_j$ et $v=v_1 \cdots v_k$ sont des éléments de $\mathcal{U}$, on note $uv=u_1 \cdots u_j v_1 \cdots v_k$ la concaténation de $u$ et $v$. En particulier, on a $u \emptyset=\emptyset u = u$. Finalement, un \emph{arbre ordonné enraciné} $ \tau$ (on dit parfois aussi \emph{arbre plan enraciné} ou \emph{arbre planaire enraciné}) est un sous-ensemble fini de $\mathcal{U}$ vérifiant les trois conditions suivantes: \begin{itemize} \item[(i)] $\emptyset \in \tau$, \item[(ii)] si $v \in \tau$ et $v=uj$ pour un certain $j \in \N^*$, alors $u \in \tau$, \item[(iii)] pour tout $u \in \tau$, il existe $k_u(\tau) \in \N $ tel que, pour chaque $j \in \N^*$, $uj \in \tau$ si et seulement si $1 \leq j \leq k_u(\tau)$. \end{itemize} \begin{figure}[htb] \centering %%% L'ARBRE \begin{scriptsize} \begin{tikzpicture} \coordinate (0) at (0,0); \coordinate (1) at (-1.5,1); \coordinate (11) at (-1.5,2); \coordinate (2) at (0,1); \coordinate (21) at (0,2); \coordinate (3) at (1.5,1); % \draw (0) -- (1) -- (11) (0) -- (2) -- (21) (0) -- (3) % ; \draw[fill=black] (0) +(-2pt,-2pt) rectangle +(2pt,2pt) (1) circle (1pt) (2) circle (1pt) (3) circle (1pt) (11) circle (1pt) (21) circle (1pt) ; % Labels \draw (0) node[below] {$\emptyset$} (1) node[above left] {$1$} (2) node[above left] {$2$} (3) node[above left] {$3$} (11) node[above left] {$11$} (21) node[above left] {$21$} ; \end{tikzpicture} \end{scriptsize} \caption{Un exemple d'arbre $\tau$, où $\tau= \{\emptyset,1,11,2,21,3\}$.} \end{figure} Dans toute la suite, par \emph{arbre} nous entendons toujours arbre ordonné enraciné fini. L'ensemble des arbres est noté $ \T$. Nous visualiserons souvent les sommets d'un arbre $ \tau$ comme les individus d'une population dont $ \tau$ est l'arbre généalogique et $\emptyset$ est l'ancêtre (la racine). À~ce titre, pour $ u \in \tau$, nous appellerons $k_u ( \tau)$ le \emph{nombre d'enfants} de~$u$, et noterons $k_u$ quand l'arbre $\tau$ est implicite. La taille totale de~$ \tau$, ou~nombre total de sommets, sera noté $|\tau|=\Card(\tau)$. Une \emph{feuille} de~$\tau$ est un sommet $u \in \tau$ tel que $k_u( \tau)=0$. Finalement, pour $j \geq 1$, une \emph{forêt} de $j$ arbres est un élément de $ \T^j$. \subsection{Arbres aléatoires} \subsubsection{Arbres de Bienaymé-Galton-Watson} Nous définissons maintenant une probabilité sur l'ensemble des arbres de telle sorte qu'en comptant le nombre de sommets à générations données on retrouve le processus de Bienaymé-Galton-Watson. \begin{defn}Soit $\mu$ une probabilité sur $\N$ telle que $\mu(0)+\mu(1)<1$ et $\sum_{k \geq 0} k \mu(k) \leq 1$. On pose, pour tout $\tau \in \T$, \begin{equation} \label{eq:Pmu}\P_{\mu}(\tau)= \prod_{u \in \tau} \mu(k_{u}). \end{equation} \end{defn} Intuitivement, \eqref{eq:Pmu} traduit le fait que les différents nombres d'enfants sont indépendants (à cause du produit) et suivent la même loi $\mu$. \begin{propo}\label{prop:Pmi}La formule \eqref{eq:Pmu} définit une probabilité $\P_{\mu}$ sur $\T$. \end{propo} Avant de prouver ce résultat, mentionnons qu'en toute rigueur il faudrait préciser la tribu considérée sur $\T$. Ici, comme $\T$ est dénombrable, on prend naturellement l'ensemble des parties de $\T$ comme tribu, et nous ne nous attarderons plus sur les questions de mesurabilité (il~faut cependant faire un peu plus attention si on travaille avec des arbres infinis). \begin{proof}[Démonstration de la proposition \ref{prop:Pmi}] La seule chose à démontrer est que $\Prmu{\T}=1$. À cet effet, nous allons construire explicitement une variable aléatoire dont la loi est $\P_{\mu}$ en utilisant le théorème \ref{thm:extinction}. Considérons une collection $(X_{u}: u \in \mathcal{U})$ de variables aléatoires indépendantes et de même loi $\mu$ (définies sur le même espace de probabilité). On pose ensuite $$ \mathcal{T} \coloneqq \left\{u_{1} \cdots u_{n }\in \mathcal{U}: u_{i} \leq X_{u_{1} u_{2} \cdots u_{i-1}} \textrm{ pour tout } 1 \leq i \leq n \right\}$$ (intuitivement, $X_{u}$ représente le nombre d'enfants de $u \in \mathcal{U}$, s'il est effectivement dans l'arbre). Par suite, $ \mathcal{T}$ est un arbre plan enraciné aléatoire (possiblement infini). Posons \hbox{$Z_{n}= \Card ( \{u \in \mathcal{T}: |u|=n \})$}. Alors, par définition de $ \mathcal{T}$, on voit que $(Z_{n}:n \geq 0)$ a la loi d'un processus de Bienaymé-Galton-Watson de loi de reproduction $\mu$, qui, d'après le théorème \ref{thm:extinction}, s'éteint presque sûrement. Ainsi, avec probabilité $1$, $ \mathcal{T}$ est fini. Mais pour un arbre $\tau \in \mathbb{T}$ fixé, on a $$ \Pr{ \mathcal{T}=\tau }= \Pr{X_{u} = k_{u}(\tau) \textrm{ pour tout } u \in \tau}= \prod_{u \in \tau} \mu(k_{u})=\Prmu{\tau}.$$ Donc $1=\sum_{\tau \in \mathbb{T}}\Pr{ \mathcal{T}=\tau }=\sum_{\tau \in \mathbb{T}} \Prmu{\tau}$, d'où le résultat. \end{proof} \begin{rem}\label{rem:surcritique}Lorsque $\sum_{i \geq 0} i \mu(i)>1$, mentionnons qu'il est possible de définir une probabilité $\Pmu$ sur les arbres plans enracinés (non nécessairement finis) tels que la formule \eqref{eq:Pmu} demeure pour des arbres~$\tau$ finis. Cependant, comme nous ne nous intéresserons qu'à des arbres finis, nous ne rentrerons pas dans ces considérations. \end{rem} Dans la suite, par arbre de Bienaymé-Galton-Watson de loi de reproduction $\mu$ (ou plus simplement $\GW_{\mu}$ arbre) on entend un arbre aléatoire (c'est-à-dire une variable aléatoire définie sur un espace probabilisé à valeurs dans $\T$) dont la loi est $\Pmu$. On pourra aussi parler d'arbre de Bienaymé-Galton-Watson (ou de $\GW$ arbre) lorsque la loi de reproduction est implicite. Un des objectifs est de comprendre le comportement de \og grands \fg\ $\GW$ arbres. Pour cela, nous allons forcer les arbres à être grands en les conditionnant à avoir un grand nombre fixe de sommets (on peut bien entendu envisager d'autres types de conditionnements). Plus précisément, si $ \mathcal{T}$ est un $\GW_{\mu}$ arbre et si $n \geq 1$ est un entier tel que $\Pr{| \mathcal{T} |=n}>0$, par $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets on entendra un arbre aléatoire (c'est-à-dire une variable aléatoire à valeurs dans $\T$) dont la loi est la loi conditionnelle de $ \mathcal{T}$ sachant que $ |\mathcal{T}| =n$. Ou encore, on dira que $ \mathcal{T}_{n}$ est un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets si pour tout $\tau \in \T$ on a $$\Pr{ \mathcal{T}_{n}=\tau }= \Pr{ \mathcal{T}=\tau\bigm| |\mathcal{T}|=n },$$ ou, de manière équivalente, si pour tout arbre $\tau$ avec $n$ sommets on a \begin{equation} \label{eq:condi}\Pr{ \mathcal{T}_{n}=\tau }= \frac{\Pr{ \mathcal{T}=\tau }}{\Pr{| \mathcal{T} |=n}}. \end{equation} Bien entendu, $\Pr{ \mathcal{T}_{n}=\tau }=0$ si $\tau$ est un arbre qui n'a pas $n$ sommets. \subsubsection{Classes combinatoires d'arbres} Plusieurs classes d'arbres aléatoires à $n $ sommets (souvent appelées \og classes combinatoires \fg) peuvent être réalisées comme BGW arbres conditionnés à avoir $n$ sommets pour des lois de reproduction particulières. \begin{ex}Soit $\mu$ la probabilité définie par $\mu(i)=1/2^{i+1}$ pour tout $i \geq 0$. Soit, pour tout $n \geq 1$, $ \mathcal{T}_{n}$ un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets. Alors $ \mathcal{T}_{n}$ suit la loi uniforme sur l'ensemble des arbres à $n$ sommets. En effet, si $\tau$ est un arbre à $n$ sommets, il suffit de démontrer que $\Pr{ \mathcal{T}_{n}=\tau}$ ne dépend que de $n$. Compte tenu de \eqref{eq:condi}, il suffit de montrer que $ \Pr{\mathcal{T}=\tau}$ ne dépend que de $n$, où $ \mathcal{T}$ est un $\GW_{\mu}$ arbre. Mais $$\Pr{ \mathcal{T}=\tau }=\prod_{u \in \tau} \frac{1}{2^{k_{u}+1}}= 2^{- \sum_{u \in \tau} (k_{u}+1) }= 2^{-2n+1}, $$ où on a utilisé le fait que $\sum_{u \in \tau} k_{u}+1$ est égal au nombre de sommets d'un arbre $\tau$, d'où le résultat. \end{ex} \begin{ex}Soit $\mu$ la probabilité définie par $\mu(0)=\mu(2)=1/2$. Soit, pour tout $n \geq 1$ impair, $ \mathcal{T}_{n}$ un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets (on se restreint à des entiers impairs car le nombre de sommets d'un arbre binaire est toujours impair). Alors $ \mathcal{T}_{n}$ suit la loi uniforme sur l'ensemble des arbres binaires à $n$ sommets (ceci se démontre exactement comme dans l'exemple précédent). \end{ex} L'exemple qui suit concerne les arbres enracinés étiquetés non ordonnés et montre que les $\GW$ arbres peuvent être utiles pour étudier des arbres qui ne sont pas forcément planaires. Par définition, un arbre enraciné étiqueté non ordonné avec $n$ sommets est un arbre avec $n$ sommets, dont un est distingué (la racine), où l'ordre des enfants des sommets n'a pas d'importance et où les étiquettes des sommets forment l'ensemble $ \{1,2, \ldots,n\}$ (voir figure~\ref{fig:no} pour un exemple). Si~$\tau$ est un arbre enraciné ordonné, on note $\widehat{\tau}$ l'arbre enraciné ordonné étiqueté \emph{aléatoire} obtenu en étiquetant les sommets de $\tau$ de manière uniforme (il y a $n!$ manières de le faire). Si $\tau$ est un arbre enraciné ordonné étiqueté, on note $\mathsf{Forme}(\tau)$ l'arbre enraciné étiqueté non ordonné obtenu à partir de $\tau$ en oubliant l'ordre des enfants de chaque sommet. \begin{figure}[htb] \begin{center} \includegraphics[scale=1]{arbresetiquetes.pdf} \caption{\label{fig:no}Les deux arbres de gauche représentent le même arbre enraciné étiqueté non ordonné. L'arbre le plus à droite est l'arbre enraciné $ \{\emptyset,1,2,21,22\}$. Il n'y a qu'un seul étiquetage de celui-ci qui le rende identique aux deux arbres de gauche.} \end{center} \end{figure} \begin{ex}\label{ex:Poisson}Soit $\mu$ la probabilité définie par $\mu(i)= e^{-1} /i!$ pour tout $i \geq 0$ (c'est une loi de Poisson de paramètre $1$). Soit, pour tout $n \geq 1$, $ \mathcal{T}_{n}$ un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets. Alors $ \form(\widehat{\mathcal{T}}_{n})$ suit la loi uniforme sur l'ensemble des arbres étiquetés enracinés non ordonnés à $n$ sommets. En effet, soit $\tau^{\ast}_{0}$ est un arbre étiqueté enraciné non ordonné à $n$ sommets. Compte tenu de \eqref{eq:condi}, il suffit de montrer que $ \P(\form(\mathcal{\widehat{T}})=\nobreak\tau^{\ast}_{0})$ ne dépend que de $n$, où $ \mathcal{T}$ est un $\GW_{\mu}$ arbre. Notons $\mathbb{T}_{\tau^{\ast}_{0}}$ l'ensemble des arbres enracinés ordonnés étiquetés qui peuvent être obtenus en ordonnant les enfants de chaque sommet de $\tau^{\ast}_{0}$ (il y en a $\prod_{u \in \tau^{\ast}_{0}}{k_{u} !}$). Alors $$ \Prb{\form(\mathcal{\widehat{T}})=\tau_{0}^{\ast}}= \sum_{\tau^{\ast} \in \mathbb{T}_{\tau^{\ast}_{0}}} \Prb{ \mathcal{\widehat{T}}= \tau^{\ast}}.$$ Or, pour $\tau^{\ast} \in \mathbb{T}_{\tau^{\ast}_{0}}$, $$ \Prb{ \mathcal{\widehat{T}}= \tau^{\ast}}= \frac{1}{n!} \prod_{u \in \tau_{0}^{\ast}} \mu(k_{u}).$$ En effet, dire que $ \widehat{\mathcal{T}}= \tau^{\ast}$ revient à dire que $ \widehat{\mathcal{T}}$ est égal à $\tau^{\ast}$ (vu en tant qu'arbre enraciné ordonné non étiqueté), et il y a ensuite un seul étiquetage possible parmi les $n!$ possibles. Ainsi, en injectant l'expression explicite de $\mu$, $$\Prb{ \mathcal{\widehat{T}}= \tau^{\ast}}= \frac{1}{n!} e^{-n} \prod_{u \in \tau_{0}^{\ast}}\frac{1}{k_{u} !}=\frac{1}{n!} e^{-n} \prod_{u \in \tau^{\ast}_{0}}\frac{1}{k_{u} !}.$$ Ainsi, $ \P(\mathcal{\widehat{T}}= \tau^{\ast})$ ne dépend pas du choix de $\tau^{\ast} \in \mathbb{T}_{\tau^{\ast}_{0}}$, de sorte que $$\Prb{\form(\mathcal{\widehat{T}})=\tau_{0}^{\ast}}= \biggl( \prod_{u \in \tau^{\ast}_{0}}{k_{u} !} \biggr) \cdot \biggl( \frac{1}{n!} e^{-n} \prod_{u \in \tau^{\ast}_{0}}\frac{1}{k_{u} !} \biggr) = \frac{e^{-n}}{n!},$$ ce qui implique le résultat voulu. Par ailleurs, ce raisonnement montre que si $\tau^{\ast}_{0}$ est un arbre étiqueté enraciné non ordonné à $n$ sommets, alors \begin{equation} \label{eq:cardp}\frac{1}{\Pr{ |\mathcal{T}|=n }} \cdot \frac{e^{-n}}{n!}= \Prb{\form(\mathcal{\widehat{T}}_{n})=\tau^{\ast}_{0}} = \frac{1}{\Card(\mathbb{T}^{\ast}_{n})}, \end{equation} où $\T^{\ast}_{n}$ est l'ensemble des d'arbres étiquetés enracinés non ordonnés à $n$ sommets. Plus tard (Corollaire \ref{cor:Poisson}), nous calculerons la probabilité $\Pr{ |\mathcal{T}|=n }$ pour en déduire que $\Card(\mathbb{T}^{\ast}_{n})=n^{n-1}$. \end{ex} Nous renvoyons à \cite[Section 10]{Jan12} pour d'autres exemples. \subsubsection{Phénomènes de périodicité} Soit $\mu$ une probabilité sur $\N$ telle que $\mu(0)+\mu(1)<1$ et $\mu(0)>0$. Comme nous allons conditionner les $\GW_{\mu}$ arbres à avoir un nombre fixe de sommets, il est naturel de se demander si on peut caractériser les entiers $n \geq 1$ tels que $\Pr{| \mathcal{T} |=n}>0$. \begin{defn}La \emph{période} de $\mu$ est le plus grand entier $h \geq 1$ tel que $ \{i \geq 1: \mu(i)>0\} \subset h \Z$. On dit que $\mu$ est \emph{apériodique} si la période de~$\mu$ est $1$ (ou, de manière équivalente, si le plus grand diviseur commun des entiers $i \geq 1$ tels que $\mu(i)>0$ vaut $1$). \end{defn} Par exemple, une loi de Poisson est apériodique, mais la loi de reproduction $\mu$ telle que $\mu(0)=\mu(2)=1/2$ a pour période $2$. Il est clair que si $\mu$ a pour période $h$, alors $ \{n \geq 1: \Pr{| \mathcal{T}|=n }>0\} \subset 1+h\Z$. \begin{propo}\label{prop:per}Soit $\mu$ une loi de reproduction de période $h$ et telle que $\mu(0)>0$. Alors pour tout $n \geq 1$ suffisamment grand, on a $ \Pr{| \mathcal{T}|=hn+1 }>0$. En particulier, si $\mu$ est apériodique, alors $\Pr{| \mathcal{T}|=n}>0$ pour tout $n$ suffisamment grand. \end{propo} \begin{proof}Soit $h \geq 1$ la période de $\mu$. Par définition de $h$, le plus grand diviseur commun des entiers $i \geq 1$ tels que $\mu(hi)>0$ vaut~$1$. Il existe donc deux entiers $i,j \geq 1$ tels que $\mu(hi)>0$, $\mu(hj)>0$ et $\mathrm{PGCD}(i,j)=1$. Posons $N=ij$ et fixons $n \geq N$. Soit $0 \leq b \leq i-1$ l'entier tel que $bj \equiv n \bmod i$ (qui existe bien car $i$ et $j$ sont premiers entre eux). Il existe alors $a \in \Z$ tel que $n-bj=ai$. Or $bj0$. \end{proof} En pratique, dans la suite, on se restreindra toujours à des lois de reproduction apériodiques pour simplifier (mais tous les résultats s'adaptent aisément dans le cas périodique). \subsubsection{Arbres simplement générés et familles exponentielles} \label{sec:exp} La famille des arbres de Bienaymé-Galton-Watson conditionnés à avoir un nombre fixe de sommets se trouve être un cas particulier de la famille d'arbres simplement générés, qui ont été introduits dans la communauté combinatoire par Meir \& Moon \cite {MM78}. On considère une suite $\boldsymbol {w}= ( w_k)_ {k \geq 0}$ de réels positifs telle que $ w_0>0$ et telle qu'il existe $k>1$ avec $w_k>0$ (on dira que $\boldsymbol {w}$ est une suite de poids). Notons, pour tout $n \geq 1$, $ \mathbb {T}_n$ l'ensemble des arbres (plans et enracinés) à $n$ sommets. Pour tout $ \tau \in \mathbb {T}$, on définit le poids $w ( \tau)$ de $ \tau$ par: $$w ( \tau)= \prod_ {u \in \tau} w_ {k_u( \tau)}.$$ On pose alors pour $n \geq 1$: $$Z_n = \sum_ { \tau \in \mathbb {T}_n} w ( \tau).$$ Pour tout $ n \geq 1$ tel que $Z_n \neq 0$, soit $ \mathcal {T}^{\bw}_n$ un arbre aléatoire à valeurs dans $ \T_n$ tel que pour tout $ \tau \in \T_n$:\vspace*{-.2\baselineskip}\enlargethispage{.3\baselineskip}% $$ \Pr {\mathcal {T}^{\bw}_n= \tau} = \frac{ w ( \tau)}{Z_n}.$$ L'arbre aléatoire $ \mathcal{T}^{\bw}_n$ est dit \emph{simplement généré}. Compte tenu de \eqref{eq:Pmu} (et de la remarque \ref{rem:surcritique}), il apparaît que les $\GW$ arbres conditionnés par le nombre de sommets sont un cas particulier d'arbres simplement générés. Il se trouve qu'il existe des suites de poids $\bw$ et $\widetilde{\bw}$ différentes mais telles que les arbres $\mathcal {T}^{\bw}_n$ et $\mathcal {T}^{\widetilde{\bw}}_n$ ont la même loi. En effet: \begin{lem}\label{lem:tiltage}Soient $a>0$ et $ \lambda>0$ tel que $Z(\lambda)= \sum_ {i \geq 0} \lambda^ i w_{i}< \infty$. On pose $\widetilde{w}_{i}= a \lambda^ i w_{i}$ pour \mbox{$ i \geq 0$} (on parle de \og tiltage exponentiel \fg). Alors les deux arbres aléatoires $\mathcal {T}^{\bw}_n$ et $\mathcal {T}^{\widetilde{\bw}}_n$ ont la même loi. \end{lem} \begin{proof}En posant $\widetilde{Z}_{n}= \sum_ { \tau \in \mathbb {T}_n} \widetilde{w} ( \tau)$ on a, par définition de~$\mathcal {T}^{\bw}_n$, pour tout $\tau \in \T_{n}$:\vspace*{-3pt} \begin{align*} \Prb {\mathcal {T}^{\widetilde{\bw}}_n= \tau} = \frac{1}{\widetilde{Z}_{n}} \cdot \prod_{u \in \tau} a \lambda^{k_{u}} w_{k_{u}}&= \frac{a^{n} \lambda^{n-1}}{\widetilde{Z}_{n}} \prod_{u \in \tau} w_{k_{u}}\\[-2pt] &= \frac{a^{n} \lambda^{n-1} Z_{n}}{\widetilde{Z}_{n}}\Pr {\mathcal {T}^{\bw}_n= \tau}, \end{align*} où on a utilisé le fait que $\sum_{u \in \tau} k_{u}=n-1$. En sommant sur tous les arbres $\tau \in \T_{n}$, il en découle que $$ \frac{a^{n} \lambda^{n-1} Z_{n}}{\widetilde{Z}_{n}}=1,$$ ce qui donne le résultat voulu. \end{proof} Voyons maintenant comment appliquer le lemme \ref{lem:tiltage} aux $\GW$ arbres. Considérons une loi de reproduction $\mu$ telle que $$0<\mu(0)+\mu(1)<1.$$ Soit $ \lambda>0$ un paramètre fixé tel que $$Z(\lambda)= \sum_ {i \geq 0} \mu(i) \lambda^ i < \infty.$$ On pose ${\mu}^ {( \lambda)}(i)= \mu({i}) \lambda^ i /Z(\lambda)$ pour \mbox{$ i \geq 0$}. Le lemme \ref{lem:tiltage} montre qu'un $\GW_ \mu$ arbre conditionné à avoir $n$ sommets a la même loi qu'un $\GW_ { {\mu}^ {( \lambda)}}$ arbre conditionné à avoir $n$ sommets. On dit que $ \mu$ et~${\mu}^ {( \lambda)}$ appartiennent à la même \emph{famille exponentielle}. Remarquons que le passage de $\mu$ à $\mu^{(\lambda)}$ change la moyenne de la loi de reproduction, car celle de $\mu^{(\lambda)}$ vaut $$ \frac{1}{Z({\lambda})} \sum_{i=0}^{\infty} i \mu({i}) \lambda^{i}.$$ Ainsi, s'il existe $ \lambda>0$ tel que $ Z( \lambda)< \infty$ et ${\mu}^ {( \lambda)}$ soit critique, alors étudier un BGW arbre non critique conditionné à avoir un nombre fixe de sommets revient à étudier un BGW arbre critique conditionné à avoir un nombre fixe de sommets (cette technique a été introduite par Kennedy \cite {Ken75}). Il est clair qu'on ne peut pas toujours se ramener à l'étude d'un BGW arbre critique: on dit alors que $ \mu$ est \emph{non-générique} (par exemple si $ \mu$ est sous-critique et le rayon de convergence de $ \sum \mu(i) z^i$ vaut $1$). Dans ce cas des phénomènes intéressants surviennent, comme des phénomènes de condensation (voir figure~\ref{fig:condensation}). Finalement, en utilisant le lemme \ref{lem:tiltage}, il est possible de montrer que si $ \mathcal {T}^{\bw}_n$ est un arbre simplement généré associé à la suite de poids~$\boldsymbol {w}$, alors il existe une loi de reproduction $ \mu$ telle que $ \mathcal {T}^{\bw}_n$ a la même loi qu'un $ \GW_ \mu$ arbre conditionné à avoir $n$ sommets si et seulement si le rayon de convergence de $ \sum w_i z^i$ est strictement positif (voir \cite[Section 4]{Jan12} pour une preuve). \section{Codage par des marches aléatoires} \label{sec:codage} L'outil le plus important dans l'étude des arbres de BGW est leur codage par des marches aléatoires, dont les propriétés sont généralement bien comprises. L'idée d'utiliser un codage par une fonction pour étudier des arbres aléatoires remonte à Harris \cite {Har52}, et a été popularisée par Le Gall \& Le Jan \cite{LGLJ98} et Bennies \& Kersting \cite{BK00}. Plus généralement, cela donne également une manière d'étudier des limi\-tes de grands arbres aléatoires car il existe de nombreuses stratégies disponibles permettant de prouver des convergences fonctionnelles. Dans toute cette partie, on fixe une loi de reproduction $\mu$ telle que $0<\mu(0)+\mu(1)<1$. \subsection{Codage par la marche de {\L}ukasiewicz} Pour coder un arbre par une marche, on commence par définir un ordre sur ses sommets. Pour cela, on considère l'ordre lexicographique~$\prec$ sur l'ensemble des étiquettes $ \mathcal{U}$, pour lequel $v \prec w$ s'il existe $z \in \mathcal{U}$ avec $v = z(v_1, \dots, v_n)$, $w = z(w_1, \dots, w_m)$ et $v_1 < w_1$. Pour un arbre $\tau \in \T$, on note $u_{0}, u_{1}, \ldots, u_{|\tau|-1}$ ses sommets ordon\-nés dans l'ordre lexicographique, et on rappelle que $k_{u}$ désigne le nombre d'enfants d'un sommet $u$. \begin{defn} La \emph{marche de {\L}ukasiewicz} \hbox{$ \W( \tau)\!=\! ( \W_n( \tau), 0\!\leq\! n\! \leq\! |\tau|)$} de $ \tau$ est définie par $ \W_0( \tau)=0$ et, pour $0 \leq n \leq |\tau|-1$: $$ \W_ {n+1}( \tau)= \W_n( \tau)+k_ {u_{n}}( \tau)-1.$$ \end{defn} \begin{figure}[htb] \centering %%% L'ARBRE \begin{scriptsize} \begin{tikzpicture}[scale=.66] \coordinate (0) at (0,0); \coordinate (1) at (-1.5,1); \coordinate (11) at (-1.5,2); \coordinate (2) at (0,1); \coordinate (21) at (0,2); \coordinate (3) at (1.5,1); \coordinate (31) at (.5,2); \coordinate (32) at (1.25,2); \coordinate (321) at (1.25,3); \coordinate (3211) at (.75,4); \coordinate (3212) at (1.75,4); \coordinate (33) at (1.75,2); \coordinate (34) at (2.5,2); % \draw (0) -- (1) -- (11) (0) -- (2) -- (21) (0) -- (3) (3) -- (31) (3) -- (32) (3) -- (33) (3) -- (34) (32) -- (321) -- (3211) (321) -- (3212) ; % \draw[fill=black] (0) circle (1pt) (1) circle (1pt) (2) circle (1pt) (3) circle (1pt) (32) circle (1pt) (321) circle (1pt) (11) circle (1pt) (21) circle (1pt) (31) circle (1pt) (33) circle (1pt) (34) circle (1pt) (3211) circle (1pt) (3212) circle (1pt) ; % % Labels \draw (0) node[below] {$0$} (1) node[left] {$1$} (11) node[left] {$2$} (2) node[left] {$3$} (21) node[left] {$4$} (3) node[below] {$5$} (31) node[above] {$6$} (32) node[above left] {$7$} (321) node[left] {$8$} (3211) node[above] {$9$} (3212) node[above] {$10$} (33) node[above] {$11$} (34) node[above] {$12$} ; \end{tikzpicture} % \quad % %%% LA MARCHE \begin{tikzpicture}[scale=.66] \draw[thin, ->] (0,0) -- (.75*14,0); \draw[thin, ->] (0,-1.5) -- (0,3.5); %\foreach \x in {2, 4, ..., 12} \foreach \x in {1, 2, ..., 13} \draw (.75*\x,.05)--(.75*\x,-.05) (.75*\x,0) node[below] {$\x$}; \foreach \x in {-1, 0, 1, ..., 3} \draw (.05,\x)--(-.05,\x) (0,\x) node[left] {$\x$}; % Points \draw[fill=black] (0, 0) circle (1.25pt) (.75*1, 2) circle (1.25pt) (.75*2, 2) circle (1.25pt) (.75*3, 1) circle (1.25pt) (.75*4, 1) circle (1.25pt) (.75*5, 0) circle (1.25pt) (.75*6, 3) circle (1.25pt) (.75*7, 2) circle (1.25pt) (.75*8, 2) circle (1.25pt) (.75*9, 3) circle (1.25pt) (.75*10, 2) circle (1.25pt) (.75*11, 1) circle (1.25pt) (.75*12, 0) circle (1.25pt) (.75*13, -1) circle (1.25pt) ; \end{tikzpicture} \end{scriptsize} \caption{\label{fig:marche_Luka}Un arbre (avec ses sommets étiquetés dans l'ordre lexicographique) et sa marche de {\L}ukasiewicz associée.} \end{figure} Voir figure~\ref{fig:marche_Luka} pour un exemple. Avant de voir que la marche de {\L}ukasiewicz code de manière bijective les arbres, nous avons besoin d'introduire une notation. Pour $n \geq 1$, on pose \begin{multline*} \overline{\mathcal{S}}{}^{(1)}_{n}= \{(x_{1}, \ldots,x_{n}) \in \{-1,0,1, \ldots\}^n: x_{1}+ \cdots+x_{n}=-1 \\ \textrm{ et } x_{1}+ \cdots+x_{j}>-1 \textrm{ pour tout } 1 \leq j \leq n-1\}. \end{multline*} Si $\bx=(x_{1}, \ldots,x_{n}) \in \overline{\mathcal{S}}{}^{(k)}_{n}$ et $\by =(y_{1}, \ldots,y_{m}) \in \overline{\mathcal{S}}{}^{(k')}_{m}$, on écrit $\bx \by = (x_{1}, \ldots,x_{n},y_{1}, \ldots,y_{m})$ pour la concaténation de $\bx$ et $\by$. En~particulier, $\bx \by \in \overline{\mathcal{S}}{}^{(k+k')}_{n+m}$. Si $\bx \in \overline{\mathcal{S}}{}^{(k)}$, on peut aussi remarquer qu'on peut écrire $\bx=\bx_{1} \bx_{2} \cdots \bx_{k}$ avec $\bx_{i} \in \overline{\mathcal{S}}{}^{(1)}$ pour tout $1 \leq i \leq k$ d'une unique manière. \begin{propo}\label{prop:codage}Pour tout $n \geq 1$, l'application $\Phi_{n}$ définie par \begin{align*} \Phi_{n}: \T_{n} &\longrightarrow \overline{\mathcal{S}}{}^{(1)}_{n} \\ \tau &\longmapsto \left( k_{u_{i-1}}-1: 1 \leq i \leq n \right) \end{align*} est une bijection. \end{propo} Si $\tau \in \T$, on pose $\Phi(\tau)=\Phi_{|\tau|}(\tau)$. La proposition \ref{prop:codage} montre que la marche de {\L}ukasiewicz code bien les arbres (car les incréments de la marche de {\L}ukasiewicz de $\tau$ sont les éléments de $\Phi(\tau)$), et qu'on a aussi $ \mathcal{W}_{|\tau|}(\tau)=-1$. \begin{proof}Soit $\tau \in \T_{n}$. Vérifions d'abord que $\Phi_{n}(\tau) \in \overline{\mathcal{S}}{}^{(1)}_{n} $. Pour tout $1 \leq j \leq n$, on a \begin{equation} \label{eq:quantite}\sum_{i=1}^{j} \left( k_{u_{i-1}}-1 \right) = \sum_{i=1}^{j} k_{u_{i-1}}-j. \end{equation} On remarque que la somme $\sum_{i=1}^{j} k_{u_{i-1}}$ compte le nombre d'enfants de $u_{0},u_{1}, \ldots,u_{j-1}$. Si $j-k \textrm{ pour tout } 1 \leq j \leq n-1\}. \end{multline*} De même, la marche de {\L}ukasiewicz d'une forêt est définie à partir de la concaténation des sauts des marches de {\L}ukasiewicz des arbres de cette forêt. \subsection{Marche de {\L}ukasiewicz d'un BGW arbre} Nous allons maintenant identifier la loi de la marche de {\L}ukasiewicz d'un BGW arbre. Considérons $(W_{n})_{n \geq 0}$ une marche aléatoire sur $\Z$ telle que $W_{0}=0$ et dont la loi des sauts est donnée par $\Pr{W_{1}=k}= \mu(k+1)$ pour tout $k \geq -1$. Autrement dit, pour $n \geq 1$, on a $$W_{n}=X_{1}+ \cdots+X_{n},$$ où les variables aléatoires $(X_{i})_{i \geq 1}$ sont indépendantes et de même loi donnée par $\Pr{X_{1}=k}=\mu(k+1)$ pour tout $k \geq -1$. Cette marche aléatoire jouera un rôle absolument crucial dans la suite. Pour tout $j \geq 1$, on définit $$\zeta_{j} = \inf \{n \geq 1: W_{n}=-j\},$$ qui est le premier temps de passage de la marche aléatoire en $-j$ (qui peut a priori être infini !). \begin{propo}\label{prop:vect}Soit $ \mathcal{T}$ un $\BGW_{\mu}$ arbre aléatoire. Alors les vecteurs aléatoires (de longueur aléatoire) $$ \left( \W_{0}( \mathcal{T}), \W_{1}( \mathcal{T} ), \ldots, \W_{ |\mathcal{T}| }( \mathcal{T}) \right) \qquad \textrm{et} \qquad (0,W_{1}, \ldots, W_{\zeta_{1}})$$ ont la même loi. \end{propo} \begin{proof}On fixe $n \geq 1$ et des entiers $x_{1}, \ldots,x_{n} \geq -1$. On pose \begin{align*} A&=\Pr{\W_{1}( \mathcal{T} )\!=\!x_{1}, \W_{2}( \mathcal{T} )\!-\!\W_{1}( \mathcal{T} )\!=\!x_{2}, \ldots, \W_{n}( \mathcal{T} )\!-\!\W_{n-1}( \mathcal{T} )\!=\!x_{n} }\\ B &=\Pr{W_{1}\!=\!x_{1}, W_{2}-W_{1}\!=\!x_{2}, \ldots, W_{n}-W_{n-1}\!=\!x_{n}} \end{align*} et nous allons montrer que $A=B$. Tout d'abord, si $(x_{1}, \ldots, x_{n}) \not \in \overline{\mathcal{S}}{}^{(1)}_{n}$, on a $A=B=0$. Sinon, on~a $(x_{1}, \ldots, x_{n}) \in \overline{\mathcal{S}}{}^{(1)}_{n}$ et d'après la proposition \ref{prop:codage} on peut considérer l'arbre $\tau$ dont la marche de {\L}ukasiewicz est $(0,x_{1}, x_{1}+x_{2}, \ldots)$. On~a~alors, d'après \eqref{eq:Pmu}, $$A= \Pr{ \mathcal{T}=\tau }= \prod_{u \in \tau} \mu(k_{u})= \prod_{i=1}^{n}\mu(x_{i}+1),$$ et \begin{align*} B& = \Pr{W_{1}=x_{1}, W_{2}-W_{1}=x_{2}, \ldots, W_{n}-W_{n-1}=x_{n}, \zeta_{1}=n}\\ &= \Pr{W_{1}=x_{1}, W_{2}-W_{1}=x_{2}, \ldots, W_{n}-W_{n-1}=x_{n}}\\ &= \prod_{i=1}^{n}\mu(x_{i}+1). \end{align*} Pour la deuxième égalité, on a utilisé l'égalité des événements \begin{multline*} \{W_{1}=x_{1}, W_{2}-W_{1}=x_{2}, \ldots, W_{n}-W_{n-1}=x_{n}, \zeta_{1}=n\}\\ = \{W_{1}=x_{1}, W_{2}-W_{1}=x_{2}, \ldots, W_{n}-W_{n-1}=x_{n}\} \end{multline*} qui provient du fait que $(x_{1}, \ldots, x_{n}) \in \overline{\mathcal{S}}{}^{(1)}_{n}$. Ainsi, $A=B$, ce qui conclut la preuve. \end{proof} On en déduit immédiatement: \begin{cor}\label{cor:lienGWmarches} Les assertions suivantes sont satisfaites. \begin{enumerate} \item[(i)] Soit $ \mathcal{T}$ un $\BGW_{\mu}$ arbre aléatoire. Alors $ |\mathcal{T}|$ a la même loi que~$\zeta_{1}$. \item[(ii)] Pour tout $n \geq 1$ tel que $\Pr{ |\mathcal{T}|=n }>0$, soit $ \mathcal{T}_{n}$ un $\BGW_{\mu}$ arbre aléatoire conditionné à avoir $n$ sommets. Alors la marche de {\L}ukasiewicz de $ \mathcal{T}_{n}$ a la même loi que la loi conditionnelle de $(W_{0},W_{1}, \ldots, W_{n})$ sachant que $ \zeta_{1}=n$. Ou, de manière équivalente, pour toute fonction $F:\Z^{n+1} \rightarrow \R$ on a $$\Esb{F\bigl(\W_{0}( \mathcal{T}_{n}), \W_{1} ( \mathcal{T}_{n}), \ldots, \W_{n}( \mathcal{T}_{n})\bigr)}\!=\! \Es{F(W_{0}, W_{1}, \ldots, W_{n}) \big| \zeta_{1}=n}\!.$$ \end{enumerate} \end{cor} \begin{proof}La première assertion découle du fait que si deux vecteurs aléatoires de longueur aléatoire ont la même loi, alors leurs longueurs ont la même loi. Pour (ii), on remarque que la preuve de la proposition \ref{prop:vect} montre que pour tout $\boldsymbol{z} \in \Z^{n}$, on a \begin{multline*} \Pr{(\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})) =\boldsymbol{z}, |\mathcal{T}|=n }\\ = \Pr{ (W_{0}, \ldots, W_{n})= \boldsymbol{z}, \zeta_{1}=n}. \end{multline*} Le résultat voulu s'obtient en divisant cette égalité par l'égalité $\Pr{ | \mathcal{T}|=n }= \Pr{\zeta_{1}=n}$. \end{proof} Ainsi, étudier les BGW arbres aléatoires conditionnés à avoir un nombre de sommets fixé revient à étudier des marches aléatoires conditionnées à toucher $-1$ pour la première fois à un temps fixé. \subsubsection*{Extension aux forêts} Les considérations précédents s'étendent similairement aux forêts: \begin{cor}\label{cor:lienGWmarchesforets} Les assertions suivantes sont vérifiées. \begin{enumerate} \item[(i)] Soit $ \mathcal{F}_{k}$ une forêt de $k$ $\BGW_{\mu}$ arbre aléatoires. Alors $ |\mathcal{F}_{k}|$ a la même loi que $\zeta_{k}$. \item[(ii)] Pour tout $n \geq 1$ tel que $\Pr{| \mathcal{F}_{k}|=n }>0$, soit $ \mathcal{F}_{k,n}$ une forêt de $k$ $\BGW_{\mu}$ arbre aléatoires conditionnée à avoir $n$ sommets. Alors la marche de {\L}ukasiewicz de $ \mathcal{F}_{k,n}$ a la même loi que la loi conditionnelle de $(W_{0},W_{1}, \ldots, W_{n})$ sachant que $ \zeta_{k}=n$. \end{enumerate} \end{cor} \begin{rem}\label{rem:moy}Si $\mu$ est une loi de reproduction de moyenne $m$, on~a $ \Es{W_{1}}= m-1$. De plus, si $\mu$ a une variance finie $\sigma^{2}$, alors \hbox{$\Es{W_{1}^{2}}-\Es{W_{1}}^{2}=\sigma^{2}$}. En effet, $$ \Es{W_{1}}= \sum_{i \geq -1} i \mu(i+1)=\sum_{i \geq 0} (i-1) \mu(i)=m-1$$ et \begin{multline*} \Es{W_{1}^{2}}-\Es{W_{1}}^{2}= \sum_{i \geq 0} (i-1)^{2} \mu(i) - (m-1)^{2}\\ = \Big( \sum_{i \geq 0} i^{2} \mu(i)-2m+1 \Big) -m^{2}+2m-1=\sigma^{2}. \end{multline*} \end{rem} En particulier, $(W_{n})_{n \geq 0}$ est une marche aléatoire centrée si et seulement si $m=1$ (c'est-à-dire si la loi de reproduction est critique). \section{Outils pour étudier les marches aléatoires} \label{sec:outils} D'après les résultats de la partie précédente, étudier un $\GW$ arbre conditionné à avoir un nombre de sommets fixe revient à étudier une marche aléatoire sur $\Z$ issue de $0$, qui ne fait des sauts négatifs que d'amplitude en valeur absolue au plus $1$, et qui est conditionnée à toucher $-1$ en un temps fixe. Une difficulté majeure de ce conditionnement est qu'il n'est pas \emph{local}, en ce sens qu'il ne dépend pas que du comportement de la marche à un instant fixé, mais de toute la trajectoire. Pour surmonter cette difficulté, nous allons transformer ce conditionnement non local en un conditionnement local (simplement être en $-1$ en un temps fixe) en utilisant un résultat combinatoire: le~lemme cyclique. Ensuite, pour étudier ce nouveau conditionnement local, nous aurons besoin du théorème local limite. \subsection{Lemme cyclique} Cette partie est inspirée d'un cours de M2 de Grégory Miermont. Pour $1 \leq k \leq n$, on pose $$ \mathcal{S}^{(k)}_{n} \coloneqq \{ (x_{1}, \ldots,x_{n}) \in \{-1,0,1, \ldots\}^n: x_{1}+ \cdots+ x_{n}=-k \},$$ de sorte que \begin{multline*} \overline{\mathcal{S}}{}^{(k)}_{n}\\ = \{(x_{1}, \ldots,x_{n}) \in \mathcal{S}^{(k)}_{n}: x_{1}+ \cdots+x_{j}>-k \textrm{ pour tout } 1 \leq j \leq n-1\}. \end{multline*} On pose également $$ \mathcal{S}^{(k)}= \bigcup_{n \geq 1} \mathcal{S}^{(k)}_{n}, \qquad \overline{\mathcal{S}}{}^{(k)}= \bigcup_{n \geq 1} \overline{\mathcal{S}}{}^{(k)}_{n}.$$ Dans la suite, on identifie un élément de $\Z/n\Z$ avec son unique représentant dans $ \{0,1, \ldots,n-1\} $. Pour $\bx=(x_{1}, \ldots,x_{n}) \in \mathcal{S}^{(k)}_{n}$ et $i\in \Z/n\Z$, on pose $$\bx^{(i)}= (x_{i+1}, \ldots, x_{i+n}),$$ où l'addition des indices est considérée modulo $n$. On dit que $\bx^{(i)}$ est obtenu à partir de $\bx$ par permutation cyclique. On peut remarquer que $ \mathcal{S}^{(k)}_{n}$ est stable par permutations cycliques. \begin{defn}Pour $\bx \in \mathcal{S}_{n}^{(k)}$, on pose $$I_{\bx}= \left\{i \in \Z/n\Z: \bx^{(i)} \in \overline{\mathcal{S}}{}^{(k)}_{n} \right\}.$$ \end{defn} Nous renvoyons à la figure~\ref{fig:cyclique} pour un exemple. Remarquons que si $\bx \in \mathcal{S}_{n}^{(k)}$ et $i \in \Z/n\Z$, alors $ \Card(I_{\bx})= \Card(I_{\bx^{(i)}})$. \begin{figure}[htb] \centering \begin{scriptsize} \hspace*{-.7cm} \begin{tikzpicture}[scale=.52] \draw[thin, ->] (0,0) -- (.75*12.5,0); \draw[thin, ->] (0,-3.6) -- (0,1.2); \foreach \x in {1, 2, ..., 12} \draw (.75*\x,.05)--(.75*\x,-.05) (.75*\x,0) node[below] {$\x$}; \foreach \x in {-4,-3,-2,-1, 0, 1} \draw (.05,.8*\x)--(-.05,.8*\x) (0,.8*\x) node[left] {$\x$}; % Points \draw[fill=black] (0, 0) circle (1.25pt) (.75*1, .8) circle (1.25pt) (.75*2, 0) circle (1.25pt) (.75*3, -.8) circle (1.25pt) (.75*4, -1.6) circle[radius=2.5pt] (1.25pt) (.75*5, -2.4) circle[radius=4pt] (1.25pt) (.75*6, -.8) circle (1.25pt) (.75*7, -1.6) circle (1.25pt) (.75*8, -2.4) circle (1.25pt) (.75*9, -3.2) circle[radius=2pt] (1.25pt) (.75*10, -3.2) circle (1.25pt) (.75*11, -1.6) circle (1.25pt) (.75*12, -2.4) circle (1.25pt) ; \end{tikzpicture} %\quad %\hspace*{-.95cm} \begin{tikzpicture}[scale=.52] \draw[thin, ->] (0,0) -- (.75*12.5,0); \draw[thin, ->] (0,-3.6) -- (0,2); \foreach \x in {1, 2, ..., 12} \draw (.75*\x,.05)--(.75*\x,-.05) (.75*\x,0) node[below] {$\x$}; \foreach \x in {-4,-3,-2,-1, 0, 1,2} \draw (.05,.8*\x)--(-.05,.8*\x) (0,.8*\x) node[left] {$\x$}; % Points \draw[fill=black] (0, 0) circle[radius=3pt] (1.25pt) (.75*1, 1.6) circle (1.25pt) (.75*2, .8) circle (1.25pt) (.75*3, 0) circle (1.25pt) (.75*4, -.8) circle (1.25pt) (.75*5, -.8) circle (1.25pt) (.75*6, .8) circle (1.25pt) (.75*7, 0) circle (1.25pt) (.75*8, .8) circle (1.25pt) (.75*9, 0) circle (1.25pt) (.75*10, -.8) circle (1.25pt) (.75*11, -1.6) circle (1.25pt) (.75*12, -2.4) circle (1.25pt) ; \end{tikzpicture} \end{scriptsize} \caption{\label{fig:cyclique}Si $\bx=(x_{1},x_{2},\ldots)$, on trace $x_{1}+ \cdots+x_{i}$ en fonction de $i$. À gauche, on a pris\\ $\bx=(1,-1,-1,-1,-1,2,-1,-1,-1,0,2,-1) \in S^{(3)}_{13}$,\\ où $I_{\bx}= \{4,5,9\}$. À droite, on a pris $\bx^{(5)}$, qui appartient bien à $\overline{S}^{(3)}_{13}$.} \end{figure} \pagebreak[2] \begin{thm}[Lemme cyclique]\label{thm:lemmecyclique} Pour tout $\bx \!\in\! \mathcal{S}_{n}^{(k)}$, on a \hbox{$\Card(I_{\bx})\!=\!k$}. \end{thm} Ainsi, si on se restreint à $\mathcal{S}^{(k)}$, $I_{\bx}$ dépend de $\bx$, mais son cardinal de dépend pas de $\bx$ ! \begin{proof}On commence par montrer un résultat intermédiaire: nous allons démontrer que $\Card(I_{\bx})$ ne change pas lorsqu'on concatène\enlargethispage{.2\baselineskip}% $$ (a,\underbrace{-1,\ldots,-1}_{{a \textrm{ fois}}})$$ à gauche de $\bx$, où $a \geq 1$ est un entier. Pour le prouver, fixons $\bx=(x_{1}, \ldots,x_{n}) \in \mathcal{S}_{n}^{(k)}$ et notons\vspace*{-.3\baselineskip} $$ \widetilde{\bx}=(a,\underbrace{-1,\ldots,-1}_{{a \textrm{ fois}}}, x_{1}, \ldots,x_{n}).$$ Tout d'abord, il est clair que $0 \in I_{\widetilde{\bx}}$ si et seulement si $0 \in I_{\bx}$. Ensuite, si $0 k$ un entier tel que le lemme cyclique soit vrai pour $ \mathcal{S}_{j}^{(k)}$ avec $j=k, \ldots,n-1$. Soit $\bx=(x_{1}, \ldots,x_{n}) \in \mathcal{S}_{n}^{(k)}$. Comme $\Card(I_{\bx})$ ne change par lorsqu'on permute cycliquement $\bx$ et qu'il existe $i \in \{1,2,\ldots,n\} $ tel que $x_{i} \geq 0$ (car $n>k$), on peut supposer que $x_{1} \geq 0$. Notons $1=i_{1}0$, $$ \sum_{n \geq 1} \frac{(\lambda n)^{n-1} e^{-\lambda n}}{n!} = \begin{cases} 1 & \textrm{si } \lambda \leq 1\\ s & \textrm{si } \lambda>1, \textrm{ où } s \in{}]0,1[ \textrm{ vérifie } s=e^{\lambda (s-1)}. \end{cases}$$ \item[(ii)] Le nombre $ \Card(\T^{\ast}_{n})$ d’arbres étiquetés enracinés non ordonnés à $n$ sommets est $n^{n-1}$. \end{enumerate} \end{cor} \begin{proof} Pour (i), choisissons pour $\mu$ une loi de Poisson de paramètre $\lambda$. Alors $W_{n}+n$ a la même loi qu'une somme de $n$ variables aléatoires de Poisson indépendantes de paramètre $\lambda$, et suit donc une loi de Poisson de paramètre $\lambda n$. En utilisant la proposition \ref{prop:echangeabilite1}, on en déduit: \begin{equation} \label{eq:tp}\Pr{| \mathcal{T}|=n }= \frac{1}{n} \Pr{W_{n}+n=n-1}= \frac{1}{n} e^{-\lambda n} \frac{(\lambda n)^{n-1}}{(n-1)!}. \end{equation} Or $\Pr{| \mathcal{T}|<\infty}= \sum_{n \geq 1} \Pr{ | \mathcal{T}|=n }$. D'après le théorème \ref{thm:extinction}, $\Pr{| \mathcal{T}|<\infty}=1$ si $\lambda \leq 1$, et si $\lambda>1$, $\Pr{| \mathcal{T}|<\infty}$ est le plus petit point fixe de la fonction génératrice $\phi(s)= e^{\lambda (s-1)}$, ce qui implique le résultat. Pour (ii), il suffit de combiner \eqref{eq:cardp} avec \eqref{eq:tp} (avec $\lambda=1$), et on obtient\vspace*{-.5\baselineskip}% \[ \Card(\T_{n}^{\ast})= e^{n} n! \cdot e^{-n} \frac{n^{n-1}}{n!} =n^{n-1}. \qedhere \] \end{proof} Comme il y a $n$ manières de choisir une racine dans un arbre à $n$ sommets, on en déduit que le nombre d'arbres étiquetés non enracinés et non ordonnés à $n$ sommets est $n^{n-2}$, ce qui est connu sous le nom de \emph{Formule de Cayley} (démontrée et généralisée par Cayley en 1889, mais précédemment démontrée sous cette forme par Borchardt en~1860). \begin{proof}[Démonstration de la proposition \ref{prop:echangeabilite1}] L'idée est d'utiliser le fait que la loi d'une famille de variables aléatoires indépendantes et de même loi est invariante par permutations. On commence par écrire, en utilisant le Corollaire \ref{cor:lienGWmarches}(1) que $\Pr{ | \mathcal{T}|=n }=\Pr{\zeta_{1}=n}$. On remarque ensuite que les événements \hbox{$ \{\zeta_{1}=n\}$} et $\{ \boldsymbol{X}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n} \} $ sont égaux, et que les événements \hbox{$ \{W_{n}=-1\}$} et $\{ \boldsymbol{X}_{n} \in {\mathcal{S}}^{(1)}_{n} \} $ sont égaux. Ainsi,\enlargethispage{\baselineskip}% \begin{align*} \mathbb{P}(| \mathcal{T}|&=n)= \Prb{ \boldsymbol{X}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n} } \\[-2pt] &= \frac{1}{n} \sum_{i=1}^{n} \Prb{\bX^{(i)}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}} \ (\textrm{car } \bX^{(i)}_{n} \textrm{ et } \bX_{n} \textrm{ ont même loi}) \\[-2pt] &= \frac{1}{n} \sum_{i=1}^{n} \EsB{ \mathbbm{1}_{\bX_{n} \in {\mathcal{S}}^{(1)}_{n}} \mathbbm{1}_{i \in I_{\bX_{n}}} }\\[-2pt] &(\textrm{car } \bX^{(i)}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n} \textrm{ si et seulement si } \bX_{n} \in {\mathcal{S}}^{(1)}_{n} \textrm{ et } i \in I_{\bX_{n}} ) \\[-2pt] &= \frac{1}{n} \Esbb{ \mathbbm{1}_{W_{n}=-1} \bigg( \sum_{i=1}^{n} \mathbbm{1}_{i \in I_{\bX_{n}}} \bigg) }\\[-4pt] &= \frac{1}{n} \Es{ \mathbbm{1}_{W_{n}=-1}} \quad (\textrm{car } \Card(I_{\bX_{n}})=1 \textrm{ lorsque } W_{n}=-1)\\ &= \frac{1}{n} \Pr{W_{n}=-1}. \end{align*} Ceci conclut. \end{proof} \begin{propo}\label{prop:echangeabilite2}Les assertions suivantes sont vérifiées pour tout entier $n \geq 1$ tel que $\Pr{| \mathcal{T}|=n }>0$: \begin{enumerate} \item[(i)] Soit $F: \Z^{n} \rightarrow \R$ une application invariante par permutations cycliques (c'est-à-dire que $F(\bx)=F(\bx^{(i)})$ pour tout $\bx \in \Z^{n}$ et $i \in\nobreak \Z/n\Z$). Alors\vspace*{-.3\baselineskip} \begin{multline*} \Es{ F(\W_{1}( \mathcal{T})-\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})-\W_{n-1}( \mathcal{T})) \big | | \mathcal{T}|=n }\\ = \Es{F(X_{1}, \ldots,X_{n}) \big| W_{n}=-1}. \end{multline*} \item[(ii)] La loi conditionnelle de\vspace*{-3pt} \[ \left( \W_{1} (\mathcal{T})-\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})-\W_{n-1}( \mathcal{T}) \right) \] sachant que $ |\mathcal{T}|=n $ est égale à la loi de $\boldsymbol{X}^{(i_{\star})}_{n}$ sachant que $W_{n}=-1$, où $i_{\star}$ est l'unique élément de $I_{\boldsymbol{X}_{n}}$. De plus, sous la loi conditionnelle $\Pr{ \ \cdot \ \big | W_{n}=-1}$, les variables aléatoires $\boldsymbol{X}_{n}^{(i_{\star})}$ et $i_{\star}$ sont indépendantes, et $i_{\star}$ suit la loi uniforme sur $ \{0,1, \ldots,n-1\}$. \end{enumerate} \end{propo} Avant de démontrer la proposition \ref{prop:echangeabilite2}, donnons quelques exemples d'applications invariantes par permutations cycliques. Si $\bx=(x_{1}, \ldots,x_{n})$, on peut par exemple penser à $F(\bx)=\max(x_{1}, \ldots,x_{n})$, $F(\bx)=\min(x_{1}, \ldots,x_{n})$, $F(\bx)=x_{1} x_{2} \cdots x_{n}$, $F(\bx)=x_{1}+ \cdots+x_{n}$, ou plus généralement $F(\bx)=x_{1}^{\lambda}+ \cdots+x_{n}^{\lambda}$ avec $\lambda>0$. Si $A \subset \Z$,\vspace*{-3pt}\enlargethispage{2\baselineskip}% $$F(\bx)= \sum_{i=1}^{n} \mathbbm{1}_{x_{i} \in A},$$ qui compte le nombre d'éléments dans $A$, est également invariante par permutations cycliques. Si $F$ est invariante par permutations cycliques et $g: \R \rightarrow \R$ est une fonction, alors $g \circ F$ est également invariante par permutations cycliques. Finalement $F(x_{1},x_{2},x_{3})=(x_{2}-x_{1})^{3}+(x_{3}-x_{2})^{3}+(x_{1}-x_{3})^{3}$ est invariante par permutations cycliques mais pas par permutations. \begin{proof}[Démonstration de la proposition \ref{prop:echangeabilite2}] Pour\,(i), on commence par~écrire, en utilisant le Corollaire \ref{cor:lienGWmarches} (ii) que\vspace*{-.5\baselineskip}% \begin{multline*} \Es{ F(\W_{1}( \mathcal{T})-\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})-\W_{n-1}( \mathcal{T})) \mathbbm{1}_{|\mathcal{T}|=n} }\\ = \Es{F(\bX_{n}) \mathbbm{1}_{\zeta_{1}}=-1}=\Es{F(\bX_{n}) \mathbbm{1}_{\bX_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}}}. \end{multline*} Comme dans la preuve de la proposition \ref{prop:echangeabilite1}, on écrit ensuite\vspace*{-3pt} \begin{align*} \Es{F(\bX_{n}) \mathbbm{1}_{\bX_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}}}&=\frac{1}{n} \sum_{i=1}^{n }\Es{F(\bX_{n}^{(i)}) \mathbbm{1}_{\bX^{(i)}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}} }\\[-5pt] & \hspace*{2.35cm}(\textrm{car } \bX^{(i)}_{n} \textrm{ et } \bX_{n} \textrm{ ont même loi}) \\[-5pt] &=\frac{1}{n} \sum_{i=1}^{n }\Es{F(\bX_{n}) \mathbbm{1}_{\bX^{(i)}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}} }\\[-2pt] & \textrm{(invariance de $F$ par permutations cycliques)} \\[-5pt] &=\frac{1}{n} \Esbb{F(\bX_{n}) \mathbbm{1}_{W_{n}=-1} \bigg( \sum_{i=1}^{n} \mathbbm{1}_{\bX^{(i)}_{n} \in \overline{\mathcal{S}}{}^{(1)}_{n}} \bigg) }\\[-5pt] &=\frac{1}{n} \Es{F(X_{1}, \ldots,X_{n}) \mathbbm{1}_{W_{n}=-1}}. \end{align*} Le résultat voulu s'obtient en divisant l'égalité \begin{multline*} \Es{ F(\W_{1}( \mathcal{T})-\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})-\W_{n-1}( \mathcal{T})) \mathbbm{1}_{|\mathcal{T}|=n} }\\ =\frac{1}{n} \Es{F(X_{1}, \ldots,X_{n}) \mathbbm{1}_{W_{n}=-1}} \end{multline*} par l'égalité $\Pr{ | \mathcal{T}|=n }= \frac{1}{n} \Pr{W_{n}=-1}$. Pour (ii), encore en utilisant le Corollaire \ref{cor:lienGWmarches} (ii), on voit que la loi conditionnelle de $ \left( \W_{1} (\mathcal{T})-\W_{0}( \mathcal{T}), \ldots, \W_{n}( \mathcal{T})-\W_{n-1}( \mathcal{T}) \right) $ sachant que $ |\mathcal{T}|=n $ est égale à la loi de $\bX_{n}$ sachant que $\zeta_{1}=n$. Fixons maintenant $\bx \in \overline{\mathcal{S}}{}^{(1)}_{n}$. En remarquant que les événements \hbox{$ \{\bX_{n}=\bx, \zeta_{1}=n\}$} et $ \{\bX_{n}=\bx,W_{n}=-1\}$ sont identiques, écrivons \begin{equation} \begin{split} \Pr{ \bX_{n}=\bx, \zeta_{1}=-1}&=\Pr{ \bX_{n}=\bx,W_{n}=-1}\\ &= \frac{1}{n} \sum_{i=1}^{n} \Pr{ \bX_{n}^{(i)}=\bx,W_{n}=-1}\\ &= \frac{1}{n} \Esbb{\mathbbm{1}_{W_{n}=-1} \bigg( \sum_{i=1}^{n} \mathbbm{1}_{\bX_{n}^{(i)}=\bx} \bigg) }\\ &= \frac{1}{n} \Es{\mathbbm{1}_{W_{n}=-1} \mathbbm{1}_{\bX_{n}^{(i_{\star})}=\bx} }\\ &= \frac{1}{n} \Pr{\bX_{n}^{(i_{\star})}=\bx, W_{n}=-1}. \end{split} \label{eq:star} \end{equation} En divisant ceci par l'égalité $\Pr{ \zeta_{1}=n }= \frac{1}{n} \Pr{W_{n}=-1}$, on en déduit que $$\Pr{ \bX_{n}=\bx \big | \zeta_{1}=n }= \Pr{\bX_{n}^{(i_{\star})}=\bx \big| W_{n}=-1},$$ ce qui montre la première partie de (ii). En ce qui concerne la deuxième partie, fixons $k \in \{0,1,\ldots,n-1\}$ et $\bx \in \overline{\mathcal{S}}{}^{(1)}_{n}$. En remarquant que les événements $ \{i_{\star}=k,\bX_{n}^{(i_{\star})}=\bx, W_{n}=-1 \} $ et $ \{\bX^{(k)}_{n} =\bx,W_{n}=-1\} $ sont identiques (car $ \Card(I_{\bX_{n}})=1$ lorsque $W_{n}=-1$ d'après le lemme cyclique), on a donc \begin{align*} \mathbb{P}(i_{\star}=k,&\bX_{n}^{(i_{\star})}=\bx,W_{n}=-1)= \Prb{\bX^{(k)}_{n} =\bx,W_{n}=-1}\\ &= \Pr{\bX_{n} =\bx,W_{n}=-1} \quad (\textrm{car } \bX_{n} \textrm{ et } \bX^{(k)}_{n} \textrm{ ont même loi})\\ &= \frac{1}{n} \Prb{\bX_{n}^{(i_{\star})}=\bx, W_{n}=-1} \quad (\textrm{par } \eqref{eq:star}) \end{align*} En divisant les deux termes de l'égalité par $\Pr{W_{n}=-1}$, on en déduit que $$ \Prb{i_{\star}=k,\bX_{n}^{(i_{\star})}=\bx \big| W_{n}=-1 }= \frac{1}{n} \cdot \Prb{\bX^{(i_{\star})} =\bx \big| W_{n}=-1}.$$ En sommant sur toutes les valeurs de $\bx \in \overline{\mathcal{S}}{}^{(1)}_{n}$ possibles, on obtient que $\Pr{i_{\star}=k \big| W_{n}=-1}= \sfrac{1}{n}$ (qui est bien la loi uniforme sur $ \{0,1,\ldots,n-1\}$) puis \begin{multline*} \Prb{i_{\star}=k,\bX_{n}^{(i_{\star})}=\bx \big| W_{n}=-1 }\\ = \Pr{i_{\star}=k \big| W_{n}=-1}\cdot \Prb{\bX^{(i_{\star})} =\bx \big| W_{n}=-1}, \end{multline*} ce qu'il fallait démontrer. \end{proof} \begin{rem} En pratique, la proposition \ref{prop:echangeabilite2} est utile pour simuler la marche de {\L}ukasiewicz d'un $\GW_{\mu}$ arbre conditionné à avoir un nombre fixe de sommets. En effet, on commence par simuler la marche aléatoire $(W_{n})_{n \geq 0}$ conditionnée par l'événement $W_{n}=-1$. Ceci peut se faire en temps linéaire en $n$: on commence par tirer le nombre de sauts d'amplitude $-1$ (cette loi se calcule aisément), puis le nombre de sauts d'amplitude $0$, etc., puis on ordonne ces sauts par une permutation uniforme (voir \cite{Dev12}). Ensuite, on trouve l'indice $i_{\star}$ où cette marche atteint pour la première fois son minimum global sur $ \{1,2, \ldots,n\}$, et on renvoie la marche obtenue en lisant les incréments à partir de l'indice $i_{\star}$. \end{rem} \begin{rem}\label{rem:forets}La preuve de la proposition \ref{prop:echangeabilite2} s'adapte aisément au cas des forêts, et permet de montrer que si $ \mathcal{F}_{k}$ est une forêt de $k$ $\GW_{\mu}$ arbre aléatoires indépendants, alors: \begin{enumerate} \item[(1)] On a $\Pr{ | \mathcal{F}_{k}|=n }= \frac{k}{n} \Pr{W_{n}=-k}$. \item[(2)] Soit $F: \Z^{n} \rightarrow \R$ une application invariante par permutations cycliques (c'est-à-dire que $F(\bx)=F(\bx^{(i)})$ pour tout $\bx \in \Z^{n}$ et $i \in \Z/n\Z$). Alors \begin{multline*} \Es{ F(\W_{1}( \mathcal{F}_{k})-\W_{0}(\mathcal{F}_{k}), \ldots, \W_{n}(\mathcal{F}_{k})-\W_{n-1}(\mathcal{F}_{k})) \big | |\mathcal{F}_{k}|=n }\\ = \Es{F(X_{1}, \ldots,X_{n}) \big| W_{n}=-k}. \end{multline*} \end{enumerate} Notons qu'on retrouve la proposition \ref{prop:echangeabilite2} en prenant $k=1$. \end{rem} \subsection{Le théorème local limite} Compte tenu de la proposition \ref{prop:echangeabilite1}, il est naturel de vouloir étudier le comportement de $\Pr{W_{n}=-1}$ lorsque $n \rightarrow \infty$. Nous allons le faire en utilisant le théorème local limite, que nous allons d'abord énoncer et démontrer avec des outils analytiques. \begin{defn}On dit qu'une marche aléatoire $(Z_{n})_{n \geq 0}$ est \emph{apériodique} si le plus grand entier $h \geq 0$ tel que $\Pr{Z_{1} \in c+h \Z}=1$ pour un certain entier $c$ est $h=1$. \end{defn} Remarquons que si $\mu$ est une loi de reproduction apériodique, alors sa marche aléatoire associée $(W_{n})_{n \geq 0}$ est apériodique. En effet, si $\Pr{W_{1} \in c+h \Z}=1$, comme $\Pr{W_{1}=-1}>0$, on doit avoir $c=-1$ (modulo $h$). Mais alors \[ \{i \geq 1: \Pr{W_{1}+1=i}>0 \}= \{i \geq 1: \mu(i)>0\}, \] d'où le résultat. \begin{thm}[Théorème Local Limite] \label{thm:ll} On suppose que $(Z_{n})_{n \geq 0}$ est apériodique, que $\Es{Z_{1}^{2}}<\infty$ et que $\sigma^{2} \coloneqq \Es{Z_{1}^{2}}-\Es{Z_{1}}^{2} \in{}]0,\infty[$. Alors, en notant $a=\Es{Z_{1}}$,\vspace*{-.2\baselineskip}\enlargethispage{\baselineskip}% $$ \sup_{k \in \Z} \bigg| \sqrt{n} \Pr{Z_{n}=k}- \frac{1}{\sqrt{2\pi \sigma^{2}}} \exp \bigg( - \frac{1}{2} \Big( \frac{k-an}{\sigma \sqrt{n}} \Big)^{2} \bigg) \bigg| \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad 0.$$ \end{thm} Mentionnons déjà que le théorème local limite implique le théorème central limite. En effet, en supposant pour simplifier que $a=0$, \begin{align*} \PrB{u \leq \frac{Z_{n}}{\sigma \sqrt{n}} \leq v}&= \sum_{k=\lceil u \sigma \sqrt{n} \rceil }^{\lfloor v \sigma \sqrt{n} \rfloor} \Pr{Z_{n}=k}\\ &= \int_{\lceil u \sigma \sqrt{n} \rceil}^{\lfloor v \sigma \sqrt{n} \rfloor+1} \Pr{Z_{n}= \lfloor x \rfloor } dx\\ &=\int_{\lceil u \sigma \sqrt{n} \rceil/(\sigma \sqrt{n})}^{(\lfloor v \sigma \sqrt{n} \rfloor+1)/ (\sigma \sqrt{n})} \sigma \sqrt{n} \Pr{Z_{n}= \lfloor x \sigma \sqrt{n} \rfloor } dx \\ & \displaystyle \mathop{\longrightarrow}_{n \rightarrow \infty} \int_{u}^{v} \frac{1}{\sqrt{2\pi}} e^{- \frac{1}{2} x^{2}} dx, \end{align*} où la dernière convergence découle du théorème de convergence dominée dont les hypothèses sont satisfaites grâce au théorème local limite. Avant de démontrer le théorème \ref{thm:ll}, on commence par un lemme. \begin{lem}\label{lem:module}Pour tout $t \in \R$, on pose $\phi(t)= \Esb{e^{itZ_{1}}}$. Si $(Z_{n})_{n \geq 0}$ est une marche aléatoire apériodique, alors $|\phi(t)| <1$ pour tout $t \in {}]0,2\pi[$. \end{lem} \begin{proof}Raisonnons par l'absurde en supposant l'existence d'un $t_{0} \in {}]0,2\pi[$ tel que $|\phi(t_{0})|=1$. Il existe donc $a \in \R$ tel que $\Esb{e^{i t_{0} Z_{1}}}= e^{i t_{0} a }$, ou encore $ \Esb{e^{it_{0}(Z_{1}-a)}}=1$. D'après la formule de transfert, on en déduit que $$ \sum_{k \in \Z} \Pr{Z_{1}=k} \cos(t_{0}(k-a))=1.$$ Il en découle que $\cos(t_{0}(k-a))=1$ pour tout $k \in \Z$ tel que $\Pr{Z_{1}=k}>0$. Ainsi, si $\Pr{Z_{1}=k}>0$, alors $k \in a+ \frac{2 \pi}{ t_{0}} \Z$. Par hypothèse d'apériodicité, on a $ \sfrac{2 \pi}{t_{0}} \leq 1$. Contradiction. \end{proof} \begin{proof}[Démonstration du théorème \ref{thm:ll}]Quitte à considérer $Z_{n}-an$ au lieu de $Z_{n}$, on suppose que $a=0$. Tout d'abord, remarquons que $ \Esb{e^{i t Z_{n}}}= \phi(t)^{n}$ car les sauts de $(Z_{n})$ sont indépendants. D'après la formule de transfert, $$\Esb{e^{it Z_{n}}}= \sum_{j \in \Z} e^{itj} \Pr{Z_{n}=j}.$$ Comme cette série converge normalement, on en déduit que $$\Pr{Z_{n}=k} = \frac{1}{2 \pi} \int_{-\pi}^{\pi} e^{-itk} \Esb{e^{itZ_{n}}} {\d}t= \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{-itk} \phi(t)^{n} {\d}t.$$ Ainsi, en supposant que $u$ est choisi de sorte que $u \sigma \sqrt{n}$ soit entier, on~a \begin{align*} \sigma \sqrt{n} \Pr{Z_{n}=u \sigma \sqrt{n}}&= \frac{\sigma \sqrt{n}}{2 \pi} \int_{-\pi}^{\pi} e^{- i t u \sigma \sqrt{n}} \phi(t)^{n} {\d}t\\ &= \frac{1}{2\pi} \int^{\pi \sigma \sqrt{n}}_{-\pi \sigma \sqrt{n}} e^{- i t u} \phi \Big( \frac{t}{\sigma \sqrt{n}} \Big)^{n} {\d}t. \end{align*} Or pour tout $v \in \R$ on a $$ \frac{1}{\sqrt{2\pi}} e^{- \frac{1}{2} v^{2}}= \frac{1}{2 \pi} \int_{-\infty}^{\infty} e^{-i t v -vt^{2}/2}{\d}t,$$ voir par exemple l'exercice 4 de \cite[Chapitre 3.4]{Gou08}. Ainsi, pour tous $A>0$ et $0< \epsilon \leq 1$ fixés, pour $n$ suffisamment grand, \begin{multline*} \left| \sigma \sqrt{n} \Pr{Z_{n}=u \sigma \sqrt{n}} - \frac{1}{\sqrt{2\pi}} e^{- \frac{1}{2} u^{2} }\right|\\ \leq \frac{1}{2 \pi} (|I^{(1)}_{A}(u,n)| + |I^{(2)}_{\epsilon,A}(u,n)|+|I^{(3)}_{\epsilon}(u,n)|+|I^{(4)}_{A}(u)|), \end{multline*} où \begin{align*} I^{(1)}_{A}(u,n)&=\int_{-A}^{A} e^{-i t u} \Big( \phi \Big( \frac{t}{\sigma \sqrt{n}} \Big)^{n}- e^{-t^{2}/2} \Big) {\d}t,\\ I^{(2)}_{\epsilon,A}(u,n)&= \int_{A<|t|< \epsilon \sigma \sqrt{n}} e^{-itu} \phi \Big( \frac{t}{\sigma \sqrt{n}} \Big)^{n}{\d}t, \\ I^{(3)}_{\epsilon}(u,n)&=\int_{\epsilon \sigma \sqrt{n}<|t|<\pi \sigma \sqrt{n}} \phi \Big( \frac{t}{\sigma \sqrt{n}} \Big)^{n} {\d}t,\\ I^{(4)}_{A}(u)&= \int_{|t|>A} e^{-itu - t^{2}/2}{\d}t . \end{align*} Nous allons montrer que pour tout $\epsilon'>0$ fixé, il existe $A>0$ et $0< \epsilon \leq 1$ tels que pour tout $n$ suffisamment grand, pour tout $u \in \R$ (toujours tel que $u \sigma \sqrt{n}$ est entier), \begin{equation} |I^{(1)}_{A}(u,n)| \leq \epsilon',\, |I^{(2)}_{\epsilon,A}(u,n)| \leq \epsilon',\, |I^{(3)}_{\epsilon}(u,n)| \leq \epsilon',\, |I^{(4)}_{A}(u)| \leq\epsilon'. \end{equation} Tout d'abord, puisque $\sigma^{2}<\infty$, on peut écrire \begin{equation} \label{eq:phi0}\phi(t)=1- \frac{t^{2} \sigma^{2}}{2}+ t^{2} \eta(t^{2}) \end{equation} avec $\eta$ une fonction continue telle que $\eta(0)=0$. \subsubsection*{Majoration de $|I^{(1)}_{A}(u,n)|$} On peut écrire $$I^{(1)}_{A}(u,n)= \int_{-A}^{A} f_{n}(u,t) {\d}t$$ avec $|f_{n}(u,t)| \leq 1+ e^{-t^{2}/2}$ pour tout $u \in \R$, $t \in [-A,A]$, $n \geq 1$ et $\sup_{u \in \R} |f_{n}(u,t)| \rightarrow 0$ lorsque $n \rightarrow \infty$ par \eqref{eq:phi0}. Ainsi, par convergence dominée, pour tout $A>0$ fixé, $|I^{(1)}_{A}(u,n)| \rightarrow 0$ uniformément en $u$ lorsque $n \rightarrow \infty$. \subsubsection*{Majoration de $|I^{(4)}_{A}(u)|$} On a $|I^{(4)}_{A}(u)| \leq 2 \int_{A}^{\infty} e^{-t^{2}/2} {\d}t$. On peut donc choisir $A>0$ suffisamment grand pour que $|I^{(4)}_{A}(u)| \leq \epsilon'$ pour tout $u \in \R$. \subsubsection*{Majoration de $|I^{(3)}_{\epsilon}(u,n)|$} D'après le lemme \ref{lem:module}, on a $|\phi(t)| <1$ pour tout $t \in {}]0,2\pi[$. Il existe donc $c>0$ tel que $ \left| \phi \left( \sfrac{t}{\sigma \sqrt{n}} \right) \right| \leq e^{-c}$ pour tout $\epsilon \sigma \sqrt{n}<|t| < \pi \sigma \sqrt{n}$. Ainsi, pour tout $u \in \R$, $$|I^{(3)}_{\epsilon}(u,n)| \leq 2 \int_{\epsilon \sigma \sqrt{n}}^{\pi \sigma \sqrt{n}} e^{-cn} {\d}t \leq 2 \pi \sigma \sqrt{n}\, e^{-cn}.$$ Ainsi, pour tout $\epsilon>0$ fixé, pour tout $n$ suffisamment grand, on a $|I^{(3)}_{\epsilon}(u,n)| \leq \epsilon'$ pour tout $u \in \R$. \subsubsection*{Majoration de $|I^{(2)}_{\epsilon,A}(u,n)|$} Montrons que $|\phi(t)| \leq \exp ( - \sfrac{t^{2} \sigma^{2}}{4})$ pour tout $|t|$ suffisamment petit. D'après le développement limité de $\exp$ au voisinage de $0$, il suffit de montrer que $|\phi(t)|=1 - \frac{\sigma^{2}}{2} t^{2}+o(t^{2})$. À~cet effet, d'après \eqref{eq:phi0}, on a \begin{align*} |\phi(t)|^{2}= \phi(t) \overline{\phi(t)}&= \Big( 1- \frac{t^{2} \sigma^{2}}{2}+ t^{2} \eta(t^{2}) \Big) \Big( 1- \frac{t^{2} \sigma^{2}}{2}+ t^{2} \overline{ \eta(t^{2})} \Big)\\ &=1- \sigma^{2} t^{2}+o(t^{2}), \end{align*} d'où $|\phi(t)|=1 - \frac{\sigma^{2}}{2} t^{2}+o(t^{2})$. Finalement, si $\epsilon>0$ est choisi suffisamment petit, on a, pour tout $u \in \R$, $$|I^{(2)}_{\epsilon,A}(u,n)| \leq 2 \int_{A}^{\epsilon \sigma \sqrt{n}} \Big( e^{ -( \frac{t}{\sigma \sqrt{n}})^{2} \cdot \frac{\sigma^{2}}{4} } \Big)^{n} {\d}t \leq 2 \int_{A}^{\infty} e^{- \frac{t^{2} }{4}} {\d}t.$$ On peut donc choisir $\epsilon>0$ suffisamment petit et $A>0$ suffisamment grand pour que pour tout $n$ suffisamment grand, on a $|I^{(2)}_{\epsilon,A}(u,n)| \leq \epsilon'$ pour tout $u\in \R$. Ceci conclut la preuve. \end{proof} Mentionnons que prendre une marche aléatoire apériodique n'est pas très restrictif: si $h \geq 1$ est le plus grand entier tel que l'on ait $\Pr{Z_{1} \in c+h \Z}=1$ pour un certain entier $c$, le théorème \ref{thm:ll} reste vrai en remplaçant $k$ par $cn+hk$ (et cela provient simplement d'une application du théorème \ref{thm:ll} à la marche aléatoire apériodique $((Z_{n}-cn)/h)_{n \geq 0}$). Donnons tout de suite une première application de ce résultat: \begin{thm}\label{thm:equivtaille}Soit $\mu$ une loi de reproduction critique, apériodique, telle que $\mu(0)+\mu(1)<1$ et qui soit de variance finie $\sigma^{2}$. Si $ \mathcal{T}$ est un $\GW_{\mu}$ arbre aléatoire, on a $$\Pr{| \mathcal{T}|=n } \quad \mathop{\sim}_{n \rightarrow \infty} \quad \frac{1}{\sqrt{2 \pi \sigma^{2}}} \cdot \frac{1}{n^{3/2}}.$$ \end{thm} \begin{proof}D'après la proposition \ref{prop:echangeabilite1}, on a $\Pr{ | \mathcal{T}|=n }= \frac{1}{n} \Pr{W_{n}=-1}$. On a vu à la remarque \ref{rem:moy} que $\Es{W_{1}}=0$ (car $\mu$ est critique) et que la variance de $W_{1}$ vaut $\sigma^{2}$. D'après le théorème local limite, on peut donc écrire $$\Pr{W_{n}=-k}= \frac{1}{\sqrt{2 \pi \sigma^{2} n}} e^{- \frac{1}{2}( - \frac{k}{\sigma \sqrt{n}})^{2} }+ \frac{\epsilon(k,n)}{\sigma \sqrt{n}},$$ où $\sup_{k} \epsilon(k,n) \rightarrow 0$ lorsque $n \rightarrow \infty$. On en déduit que $$\Pr{W_{n}=-1} \quad \mathop{\sim}_{n \rightarrow \infty} \quad \frac{1}{\sigma \sqrt{2 \pi}} \cdot \frac{1}{\sqrt{n}}.$$ Le résultat annoncé en découle. \end{proof} Remarquons que $ \Es{ | \mathcal{T}| }= \sum_{n \geq 1} n \cdot \Pr{ | \mathcal{T}|=n } = \infty$ d'après l'équivalent du théorème \ref{thm:equivtaille}, ce qui est cohérent avec la remarque \ref{rem:poptotale}. \begin{rem}Il est possible de raffiner le théorème local limite en démontrant (voir \cite[Chap.\,7]{Spi76}) que \begin{multline*} \sup_{k \in \Z} \max \biggl( 1,\\ \Big( \frac{k\!-\!an}{\sqrt{n}} \Big)^{2} \Big) \cdot \Big | \sigma \sqrt{n} \Pr{Z_{n}\!=\!k}- \frac{1}{\sqrt{2\pi}} \exp \Big(\! - \frac{1}{2} \Big( \frac{k\!-\!an}{\sigma \sqrt{n}} \Big)^{2} \Big) \Big |\biggr) \\ \mathop{\longrightarrow}_{n \rightarrow \infty}\quad 0, \end{multline*} qui est intéressant pour de très grandes valeurs de $|k|$. \end{rem} Finalement, mentionnons que le terme \og local \fg\ du théorème local limite provient du fait que, pour une variable aléatoire réelle $X$, l'étude d'événements de type $ \{X \in \Delta \}$ avec $\Delta$ un intervalle \emph{borné} est fréquemment appelée \emph{locale} en théorie des probabilités. \section{Applications: quelques propriétés des arbres de Bien\-aymé-Galton-Watson conditionnés} \label{sec:applications} Nous voyons maintenant comment les outils introduits dans la Sec.~\ref{sec:outils} permettent d'étudier la structure de BGW arbres conditionnés à avoir un nombre fixe de sommets. Dans toute cette partie, on fixe une loi de reproduction critique apériodique $\mu$ telle que $\mu(0)+\mu(1)<1$ et qui soit de variance finie~$\sigma^{2}$. On note $ \mathcal{T}$ un $\GW_{\mu}$ arbre aléatoire, et on rappelle que $(W_{n})_{n \geq 0}$ est une marche aléatoire issue de $0$ et dont la loi des sauts est donnée par $\Pr{W_{1}=i}=\mu(i+1)$ pour tout $i \geq -1$. On suppose implicitement qu'on travaille avec des entiers $n$ suffisamment grands pour que $\Pr{| \mathcal{T}|=n }>0$ (ce qui est possible grâce à la proposition \ref{prop:per}), et on note $ \mathcal{T}_{n}$ un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets. Dans cette partie, nous utilisons le codage de $ \mathcal{T}_{n}$ par une marche aléatoire conditionnée pour étudier le comportement du degré de la racine, du nombre de feuilles et du degré maximal lorsque $n \rightarrow \infty$. \subsection{Degré de la racine} \begin{thm}\label{thm:racine}Soit $k \geq 0$ un entier. Alors $$ \Pr{ k_{\emptyset}( \mathcal{T}_{n})=k } \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad k \mu(k).$$ \end{thm} \begin{proof}Remarquons que dire que la racine de $ \mathcal{T} $ a $k$ enfants et que $ | \mathcal{T}|=n$ revient à dire que la racine de $ \mathcal{T} $ a $k$ enfants, sur lesquels est greffée une forêt de $k$ arbres (indépendants) dont la taille totale est $n-1$. Ainsi, en notant $ \mathcal{F}_{k}$ une forêt de $k$ $\GW_{\mu}$ arbres indépendants, d'après la remarque \ref{rem:forets}, $$ \Pr{ k_{\emptyset}( \mathcal{T}_{n})=k } = \frac{\mu(k) \Pr{|\mathcal{F}_{k}|=n-1}}{\Pr{| \mathcal{T}|=n }} = \mu(k) \frac{ \frac{k}{n-1}\Pr{W_{n-1}=-k}}{ \frac{1}{n} \Pr{W_{n}=-1}}.$$ Le même raisonnement que dans la preuve du théorème \ref{thm:equivtaille} montre que \[ \Pr{W_{n}=-1}\ \mathop{\sim}_{n \rightarrow \infty}\ \frac{1}{\sigma \sqrt{2 \pi}} \cdot \frac{1}{\sqrt{n}},\quad \Pr{W_{n}=-k}\ \mathop{\sim}_{n \rightarrow \infty}\ \frac{1}{\sigma \sqrt{2 \pi}} \cdot \frac{1}{\sqrt{n}}, \] ce qui implique le résultat voulu. \end{proof} Le théorème \ref{thm:racine} établit la convergence en loi de l'arbre $ \mathcal{T}_{n}$ coupé à la première génération. Plus généralement, il est possible de construire un arbre aléatoire infini $ \mathcal{T}_{\infty}$, constitué d'une épine dorsale infinie sur laquelle sont greffés des $\GW_{\mu}$ arbres indépendants, telle que pour tout $r \geq 1$, l'arbre $ \mathcal{T}_{n}$ coupé à la génération $r$, converge en loi vers vers l'arbre $ \mathcal{T}_{\infty}$ coupé à la génération $r$. On dit que $ \mathcal{T}_{n}$ converge en loi vers $ \mathcal{T}_{\infty}$ pour la topologie locale (locale, car celle-ci ne capture que ce qui se passe à horizon fini de la racine). Ce résultat est dû à Kesten \cite{Kes86} (sous une forme un peu différente), voir également \cite{AD14a,AD14b} pour des extensions récentes. \subsection{Concentration du nombre de feuilles} Notons $\lambda(\tau)$ le nombre de feuilles d'un arbre $\tau$. Le résultat suivant montre essentiellement qu'un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets possède environ $\mu(0) n$ feuilles avec très grande probabilité, et que ce nombre de feuilles satisfait à un théorème central limite. \begin{thm}\label{thm:feuilles}Les assertions suivantes sont vérifiées. \begin{enumerate} \item[(i)] Pour tout $\epsilon>0$, $$ \PrB{ \Big| \frac{\lambda( \mathcal{T}_{n}) }{\mu(0) n} - 1 \Big | > \epsilon } \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad 0.$$ \item[(ii)] Pour tout $u0$, $\Es{Z_{1}^{2}}<\infty$ et~\hbox{$\Es{Z_{1}}=0$}. Soit également $k_{0} \in \Z$ un entier fixé. Notons $Z_{n}=X_{1}+ \cdots+X_{n}$ et $L_{n}= \Card( \{1 \leq i \leq n: X_{i}=-1\}$. Alors, en posant $p=\Pr{Z_{1}=-1}$: \begin{enumerate} \item[(i)] Pour tout $\epsilon>0$, $$ \PrB{ \Big | \frac{L_{n}}{p n} - 1 \Big | > \epsilon \ \big| \ Z_{n}=k_{0} } \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad 0.$$ \item[(ii)] Pour tout $u \epsilon} \leq \frac{\mathsf{Var}(L_{n})}{p^{2} n^{2}} = \frac{1-p}{p n}.$$ Donc \begin{align*} \PrB{ \Big | \frac{\ L_{n} }{p n} - 1 \Big | > \epsilon \ \big| \ Z_{n}=k_{0}} &\leq \frac{\Pr{ \left| \frac{\ L_{n} }{p n} - 1 \right| > \epsilon}}{\Pr{Z_{n}=k_{0}}}\\ &\leq \frac{1-p}{p n} \cdot \frac{1}{\Pr{Z_{n}=k_{0}}}. \end{align*} Comme $\Pr{Z_{n}= k_{0}} \sim \frac{1}{\sigma \sqrt{2 \pi}} \cdot \frac{1}{\sqrt{n}}$ lorsque $n \rightarrow \infty$, on obtient le résultat voulu (en utilisant des inégalités de grandes déviations de type Cramér à la place de l'inégalité de Bienaymé-Tchebychev, on peut montrer que la convergence a lieu exponentiellement vite en $n$). Pour (ii), on commence par écrire, pour $k_{0} \leq k \leq n$, $$\Pr{L_{n}=k, Z_{n}=k_{0}} = \Pr{S_{n}=k} \Pr{Z'_{n-k}=k-k_{0}},$$ où $(Z'_{n})_{n \geq 0}$ est une marche aléatoire issue de $0$ dont la loi des sauts est la loi de $Z_{1}$ sachant que $Z_{1}\!\neq\! -1$ (et donc \hbox{$\Pr{Z'_{1}\!=\!i}\!=\!\Pr{Z_{1}\!=\!i}/(1\!-\!p)$} pour $i \geq 0$) et $S_{n}$ est une variable binomiale de paramètres $(n,p)$ indépendante. Essentiellement, cette écriture revient simplement à choisir les $k$ positions où $-1$ apparaît parmi les $n$ sauts de $Z_{n}$ (voir \cite[Prop.\,1.6]{Kor12} pour une preuve). Un petit calcul montre que la variance de $S_{1}$ vaut $p(1-p)$ et que \begin{equation} \label{eq:var}\Es{Z'_{1}}= \frac{p}{1-p},\qquad \mathsf{Var}(Z'_{1})= \frac{\sigma^{2}-p}{1-p}- \Big( \frac{p}{1-p} \Big)^{2}. \end{equation} Pour simplifier, on suppose dans la suite que $(Z'_n)_{n\geq 0}$ est apériodique (le cas périodique s'étudie de la même manière et est laissé au lecteur). Ensuite, écrivons \begin{align*} \mathbb{P}\Big(u \leq \frac{ L_{n}-p n }{ \sqrt{n}} &\leq v \ \big| \ Z_{n}=k_{0}\Big) = \sum_{k=\lceil pn+ u \sqrt{n} \rceil }^{ \lfloor pn+ v \sqrt{n} \rfloor} \Pr{L_{n}=k \ \big| \ Z_{n}=k_{0}} \\ &=\int_{\lceil pn+ u \sqrt{n} \rceil }^{\lfloor pn+ v \sqrt{n} \rfloor+1} \Pr{L_{n}= \lfloor x \rfloor \ \big| \ Z_{n}=k_{0}} {\d}x\\ &= \sqrt{n }\int_{u+o(1)}^{v+o(1)} \Pr{L_{n}= \lfloor pn+ \sqrt{n} x \rfloor \ \big| \ Z_{n}=k_{0}}{\d}x. \end{align*} Posons, pour $x \in [u-1,v+1]$, \begin{multline*} f_{n}(x) = \sqrt{n}\,\Pr{L_{n}= \lfloor pn+ \sqrt{n} x \rfloor \ \big| \ Z_{n}=k_{0}} \\ = \frac{\sqrt{n} \cdot \Pr{S_{n}= \lfloor pn+ \sqrt{n} x \rfloor } \cdot \Pr{\!Z'_{n- \lfloor pn+ \sqrt{n} x \rfloor }= \lfloor pn+ \sqrt{n} x \rfloor -k_{0}}}{\Pr{Z_{n}=k_{0}}}. \end{multline*} Une triple application du théorème local limite (avec les trois marches aléatoires $(S_{n})$, $(Z'_{n})$ et $(Z_{n})$) montre que \[ \sup_{n \geq 1}\sup_{x \in [u-1,v+1]} f_{n}(x)<\infty, \] et aussi que pour tout $x \in [u-1,v+1]$ fixé on a, en d'abord notant $\sigma_{0}^{2}= \mathsf{Var}(Z'_{1})$ pour simplifier l'écriture puis en injectant sa valeur donnée par \eqref{eq:var}, \begin{multline*} f_{n}(x) \mathop{\longrightarrow}_{n \rightarrow \infty} \frac{1}{\sqrt{2 \pi p(1-p)}}\ e^{- \frac{ x^{2}}{2p(1-p)}} \cdot \frac{1}{\sqrt{2 \pi (1-p)\sigma_{0}^{2}}}\ e^{- \frac{ x^{2}}{2(1-p)^{3} \sigma_{0}^{2}}} \cdot \sqrt{2\pi \sigma^{2}}\\ = \sqrt{ \frac{ \sigma^{2}}{2 \pi p(1-p)^{2} \sigma_{0}^{2}}}\ e^{- \frac{1}{(1-p^{2)}} \cdot ( \frac{1}{\sigma_{0}^{2}}+ \frac{1}{p}-1) \frac{x^{2}}{2}}= \frac{1}{\sqrt{2 \pi s^{2}}}\ e^{- \frac{x^{2}}{2 s^{2}}}, \end{multline*} avec $s^{2}=p(1-p) - \sfrac{p^{2}}{\sigma^{2}}$. Le résultat en découle par application du théorème de convergence dominée (les détails techniques de la fin de la preuve sont laissés au lecteur). \end{proof} \begin{ex}[Question Q809 de Daniel Saada, RMS 124-1]\label{ex:RMS} On note $F_{n}$ l’ensemble des applications de $\llbracket 1,n \rrbracket \coloneqq \{1,2, \ldots,n\}$ dans $\llbracket 1,n \rrbracket $, muni de la probabilité uniforme. On note $Y_{n}$ la variable aléatoire définie sur $F_{n}$ par $Y_{n}(f)=\Card(f(\llbracket 1,n \rrbracket))$. Des essais numériques montrent que la loi de $Y_{n}$ est très bien approchée par une loi normale. Est-il exact que $(Y_{n}-\Es{Y_{n}})/\sqrt{n}$ tend vers une loi normale ? Kolchin a démontré que $(Y_{n}-\Es{Y_{n}})/\sqrt{n}$ converge vers une loi normale centrée et de variance $ \frac{e-2}{e^{2}}$ \cite[Th.\,1.5.1]{Kol86}) en traduisant le problème en terme d'occupation d'urnes. Nous présentons son idée en reformulant cela dans le langage des marches aléatoires. Notons $A^{(i)}_{n}(f)=\Card(f^{-1}( \{i\}))$ et considérons $(P_{1}, \ldots,P_{n})$ des variables aléatoires indépendantes de Poisson de paramètre $1$ (ainsi $\Pr{P_{1}=i}=e^{-1}/i!$ pour $i \geq 0$). Alors on voit que les vecteurs $$(A^{(1)}_{n}, \ldots, A^{(n)}_{n}) \quad \textrm{et} \quad (P_{1}, \ldots,P_{n}) \quad \textrm{ sachant que } P_{1}+\cdots+P_{n}=n$$ ont la même loi (en effet, si un entier a $k$ antécédents, il y a $k!$ manières de les \og renuméroter\fg et nous laissons les détails au lecteur). Par ailleurs,\vspace*{-5pt} $$Y_{n}(f)=\Card( \{1 \leq i \leq n: A_{n}^{(i)}(f)=0\}).$$ Ainsi, en notant $(W_{n})_{n \geq 0}$ une marche aléatoire dont la loi des sauts est $P_{1}-1$ et $L_{n}= \Card( \{1 \leq i \leq n: X_{i}=-1\})$, on voit que $$n-Y_{n} \quad \textrm{et} \quad L_{n} \textrm{ sachant que } W_{n}=0$$ ont la même loi. Le résultat en découle immédiatement en utilisant la proposition \ref{prop:tcl} (ii) (avec $Z_{1}=P_{1}-1$ et $k_{0}=0$). \end{ex} \subsection{Degré maximal} Pour un arbre $\tau$, on note $\Delta(\tau)= \max_{ u \in \tau} k_{u}(\tau)$ le nombre maximal d'enfants d'un sommet de $\tau$. \begin{thm}\label{thm:degre} Il existe une constante $C$ (qui dépend de $\mu$) telle que pour tout $k,n \geq 1$ \begin{align*} \Pr{\Delta( \mathcal{T}_{n}) \leq k } &\leq C \left( 1- \mu([k+1,\infty[ \right)^{\nd},\\ \Pr{ \Delta(\mathcal{T}_{n}) \geq k } &\leq C \cdot \left( 1- (1-\mu( [k, \infty[)^{\nd+1} \right). \end{align*} \end{thm} Ces inégalités indiquent que le nombre maximal d'enfants $ \mathcal{T}_{n}$ se comporte \og presque \fg\ comme le maximum de $n$ variables aléatoires indépendantes de même loi $\mu$. Avant de démontrer ce résultat, donnons tout de suite une application concernant le degré maximal d'un arbre uniforme à $n$ sommets. \begin{cor}Soit $ \mathcal{T}_{n}$ un arbre uniforme à $n$ sommets. Alors pour tout $\epsilon>0$, $$\PrB{ \Big| \frac{\Delta( \mathcal{T}_{n})}{ \log_2(n)} -1 \Big | > \epsilon } \quad \mathop{\longrightarrow}_{n \rightarrow \infty} \quad 0$$ \end{cor} Ceci provient directement du théorème \ref{thm:degre} appliqué avec $k= (1\pm\epsilon) \log_{2}(n)$ car, comme on l'a vu, $ \mathcal{T}_{n}$ peut être réalisé comme un $\GW_{\mu}$ arbre conditionné à avoir $n$ sommets, avec $\mu(i)=2^{-i-1}$ pour $i \geq 0$. \skpt \begin{proof}[Démonstration du théorème \ref{thm:degre}] Tout d'abord, remarquons que $\Delta(T)-1$ est égal au plus grand incrément de $\W(T)$. Or le plus grand élément d'un vecteur est invariant par permutations cycliques. En posant $M_{m}^{n}= \max_{m \leq i \leq n} X_{i}$, on en déduit grâce à la proposition \ref{prop:echangeabilite2}~(i) que pour toute fonction $F: \Z \rightarrow \R$, \begin{equation} \label{eq:delta}\Es{F(\Delta( \mathcal{T}_{n})-1) }= \Es{F(M_{1}^{n}) \mid W_{n}=-1 }. \end{equation} Dans la suite de la preuve, $C$ désigne une constante indépendante de~$n$ mais qui peut changer de ligne en ligne. \subsubsection*{Borne inférieure} Par \eqref{eq:delta}, \begin{align*} \Pr{\Delta(\mathcal{T}_{n})-1 \leq k}&=\Pr{M_{1}^{n} \leq k \mid W_{n}=-1 } \\ &=\frac{\Pr{M_{1}^{n} \leq k, W_{n}=-1 }}{\Pr{W_{n}=-1}} \\ &\leq\frac{\Prb{M_{1}^{\lfloor n/2 \rfloor} \leq k,W_{n}=-1}}{\Pr{W_{n}=-1}}. \end{align*} Notons $\phi_{n}(j)=\Pr{W_{n}=j}$. Alors, en utilisant l'indépendance de $(X_{1}, \ldots,X_{\nd})$ et de $(X_{\nd+1}, \ldots,X_n)$, on a $${\Prb{M_{1}^{\lfloor n/2 \rfloor} \leq k,W_{n}=-1}}=\EsB{ \mathbbm{1}_{M_{1}^{\lfloor n/2 \rfloor} \leq k} \cdot \phi_{n-\lfloor n/2 \rfloor} \left( -1-W_{\lfloor n/2 \rfloor} \right) }.$$ Mais, d'après le théorème local limite, $\sup_{k \in \Z} \phi_{n}(k) \leq \sfrac{C}{\sqrt{n}}$ pour tout $n \geq 1$. Comme $\Pr{W_{n}=-1} \sim C/\sqrt{n}$, on en déduit que \begin{multline*} \Pr{\Delta(\mathcal{T}_{n}) \leq k} \leq C \cdot \Pr{M_{1}^{\lfloor n/2 \rfloor} \leq k-1}\\ =C \cdot \Pr{\max(X_{1}+1, \ldots,X_{\lfloor n/2 \rfloor}+1) \leq k}\\ = C \left( 1- \mu([k+1,\infty[ \right)^{\nd}. \end{multline*} \subsubsection*{Borne supérieure} On écrit \begin{align*} \mathbb{P}(M_{1}^{n} \geq {}& k \mid W_{n}=-1)\\ &= \Prb{M_{1}^{\nd} \geq k \textrm{ ou } M_{\nd+1}^n \geq k \mid W_{n}=-1 } \\ &\leq \frac{\Prb{M_{1}^{\nd} \geq k, W_{n}=-1 }}{\Pr{W_{n}=-1}} +\frac{\Prb{ M_{\nd+1}^{n} \geq k, W_{n}=-1 }}{\Pr{W_{n}=-1}} \end{align*} Comme $(X_{1}, X_{2},\ldots, X_{n})$ et $(X_{n},X_{n-1}, \ldots,X_{1})$ ont la même loi, la quantité $\Prb{ M_{\nd+1}^{n} \geq k, W_{n}=-1 }$ est égale à $$\Prb{M_{1}^{n-\nd} \geq k,W_{n}=-1 }.$$ Comme pour la borne inférieure, le théorème local limite nous amène à la majoration $$\Pr{M_{1}^{n} \geq k-1 \mid W_{n}=-1 } \leq C \cdot \left( 1- (1-\mu( [k, \infty[)^{\nd+1} \right) $$ car $\nd \leq n-\nd\leq \lfloor n/2 \rfloor +1$. Ainsi, \begin{multline*} \Pr{ \Delta( \mathcal{T}_{n}) \geq k }=\Pr{M_{1}^{n} \geq k-1 \mid W_{n}=-1 }\\ \leq C \cdot \left( 1- (1-\mu( [k, \infty[)^{\nd+1} \right), \end{multline*} ce qui conclut la preuve. \end{proof} \section{Applications à d'autres modèles} \label{sec:modeles} Dans cette dernière partie, nous présentons plusieurs structures discrètes aléatoires qui se révèlent être intimement liées à des arbres de Bienaymé-Galton-Watson, ce qui permet de les étudier en utilisant des résultats déjà connus sur les arbres. Les trois premiers modèles (partitions non croisées, arbres non croisés et dissections) sont des instances de configurations planes non croisées, qui sont des objets obtenus à partir des racines $n$-ièmes complexes de l'unité en les reliant par des segments qui ne peuvent pas se couper. \subsection{Partitions non croisées} Une \emph{partition} de $[n] \coloneqq \{1,2, \ldots,n\}$ est une collection de sous-ensembles deux à deux disjoints, appelés \emph{blocs}, dont l'union est $[n]$. La \emph{taille} d'un bloc est son cardinal. Une partition \emph{non croisée} de $[n]$ est une partition des racines $n$-ièmes de l'unité telle que les enveloppes convexes de ses blocs sont deux à deux disjointes. Pour tout entier $n \geq 1$, on note $ \NC_{n}$ l'ensemble des partitions non croisées de $[n]$. Les partitions non croisées ont été introduites par Kreweras \cite {Kre72}, et sont devenues un objet combinatoire standard. Elles apparaissent dans beaucoup de contextes différents, comme en topologie en basses dimensions, en théorie géométrique des groupes et en probabilités libres (voir l'article de survol \cite{McC06}). Une bijection entre $\NC_{n}$ et l'ensemble $\T_{n+1}$ des arbres à $n+1$ sommets due à Dershowitz \& Zaks \cite{DZ86} permet d'étudier les partitions non croisées grâce aux arbres. Celle-ci est très simple ; partant d'un arbre $\tau \in \T_{n+1}$, donnons la partition non croisée associée. Soient $\varnothing = u(0) \prec u(1) \prec \dots \prec u(n)$ les sommets de $\tau$ donnés dans l'ordre lexicographique. La partition $P(\tau)$ est définie par: \begin{itemize} \item[$\ast$] $i, j \in [n]$ appartiennent au même bloc de $P(\tau)$ si et seulement si $u(i)$ et $u(j)$ ont le même parent dans $\tau$. \end{itemize} Voir la figure \ref{fig:pnc} pour un exemple. %%%%%%%%%%%%%%%%%%%%%%%%%%% %%% PARTITION ET ARBRE DE GW %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htb] \begin{scriptsize} %%% L'ARBRE DE GW %%% \begin{tikzpicture}[scale=0.9] \coordinate (0) at (0,0); \coordinate (1) at (-1.5,1); \coordinate (11) at (-1.5,2); \coordinate (2) at (0,1); \coordinate (21) at (0,2); \coordinate (3) at (1.5,1); \coordinate (31) at (.5,2); \coordinate (32) at (1.25,2); \coordinate (321) at (1.25,3); \coordinate (3211) at (.75,4); \coordinate (3212) at (1.75,4); \coordinate (33) at (1.75,2); \coordinate (34) at (2.5,2); % \draw (0) -- (1) -- (11) (0) -- (2) -- (21) (0) -- (3) (3) -- (31) (3) -- (32) (3) -- (33) (3) -- (34) (32) -- (321) -- (3211) (321) -- (3212) ; % \draw[fill=black] (0) +(-2pt,-2pt) rectangle +(2pt,2pt) (1) circle (1pt) (2) circle (1pt) (3) circle (1pt) (32) circle (1pt) (321) circle (1pt) (11) circle (1pt) (21) circle (1pt) (31) circle (1pt) (33) circle (1pt) (34) circle (1pt) (3211) circle (1pt) (3212) circle (1pt) ; % % Labels \draw (0) node[below] {$0$} (1) node[below left] {$1$} (11) node[above left] {$2$} (2) node[left] {$3$} (21) node[above left] {$4$} (3) node[below right] {$5$} (31) node[above] {$6$} (32) node[above right] {$7$} (321) node[left] {$8$} (3211) node[above] {$9$} (3212) node[above] {$10$} (33) node[above right] {$11$} (34) node[above right] {$12$} ; \end{tikzpicture} % \qquad \qquad % %%% LA PARTITION %%% \begin{tikzpicture} \draw[ultra thin, dashed] (0,0) circle (2); % \foreach \x in {1, 2, ..., 12} \coordinate (\x) at (-\x*360/12: 2); % \foreach \x in {1, 2, ..., 12} \draw [fill=black] (\x) circle (1pt) (-\x*360/12: 2*1.15) node {\x} ; \filldraw[pattern=north east lines] (1) -- (3) -- (5) -- cycle (6) -- (7) -- (11) -- (12) -- cycle (9) -- (10) ; \end{tikzpicture} \end{scriptsize} \caption{\label{fig:pnc} Un arbre $\tau$ et sa partition non croisée associée $P(\tau) = \{\{1, 3, 5\}, \{2\}, \{4\}, \{6, 7, 11, 12\}, \{8\}, \{9, 10\}\}$.} \end{figure} Une propriété importante de cette bijection est que les tailles des blocs sont les nombres d'enfants des sommets de l'arbre associé, de sorte que des questions portant sur les tailles des blocs de grandes partitions non croisées aléatoires se reformulent en des questions portant sur les nombres d'enfants des sommets de l'arbre aléatoire associé. En particulier, une partition non croisée uniforme à $n$ sommets peut être réalisée comme image d'un arbre uniforme à $n+1$ sommets, et donc d'un $\GW_{\mu}$ arbre conditionné à avoir $n+1$ sommets (voir \cite{KM15a} pour des détails). \subsection{Arbres non croisés} Par définition, un arbre non croisé à $n$ sommets est un arbre dont les sommets sont les racines $n$-ièmes de l'unité et dont les arêtes sont des segments qui ne se coupent pas intérieurement. À un arbre non croisé, on peut associer de manière naturelle un arbre plan, appelé sa \emph{forme} (voir figure~\ref{fig:arbres}). \begin{figure}[ht] \centering \hfill \begin{footnotesize} \hfill % %%% LA VERSION NON-CROISÉE \begin{tikzpicture}[scale=0.9] \draw[dotted] (0,0) circle (2); % \foreach \x in {0, 1, 2, ..., 16} \coordinate (\x) at (-\x*360/17: 2); % \foreach \x in {1, 1, 2, ..., 16} \draw[fill=black] (\x) circle (1pt); \draw (-0*360/17: 2*1.15) node {0} (-1*360/17: 2*1.15) node {1} (-2*360/17: 2*1.15) node {2} (-3*360/17: 2*1.15) node {3} (-4*360/17: 2*1.15) node {4} (-5*360/17: 2*1.15) node {5} (-6*360/17: 2*1.15) node {6} (-7*360/17: 2*1.15) node {7} (-8*360/17: 2*1.15) node {8} (-9*360/17: 2*1.15) node {9} (-10*360/17: 2*1.15) node {10} (-11*360/17: 2*1.15) node {11} (-12*360/17: 2*1.15) node {12} (-13*360/17: 2*1.15) node {13} (-14*360/17: 2*1.15) node {14} (-15*360/17: 2*1.15) node {15} (-16*360/17: 2*1.15) node {16} ; \draw(0) node [rectangle, scale=.5, fill=black, draw]{}; \draw (0) -- (1) (1) -- (2) (1) -- (5) (5) -- (4) (5) -- (3) (5) -- (6) (0) -- (8) -- (7) (0) -- (10) (10) -- (9) (10) -- (11) (10) -- (15) (10) -- (16) (11) -- (14) -- (13) (14) -- (12) ; \end{tikzpicture} % \hfill %%% L'ARBRE PLANAIRE \begin{tikzpicture}[scale=0.9] \coordinate (0) at (0,0); \coordinate (1) at (-2,1); \coordinate (11) at (-2.75,2); \coordinate (12) at (-1.25,2); \coordinate (121) at (-2,3); \coordinate (122) at (-1.25,3); \coordinate (123) at (-.5,3); \coordinate (2) at (0,1); \coordinate (21) at (0,2); \coordinate (3) at (2,1); \coordinate (31) at (1,2); \coordinate (32) at (1.75,2); \coordinate (321) at (1.75,3); \coordinate (3211) at (1.25,4); \coordinate (3212) at (2.25,4); \coordinate (33) at (2.25,2); \coordinate (34) at (3,2); % \draw (0) -- (1) (1) -- (11) (1) -- (12) (12) -- (121) (12) -- (122) (12) -- (123) (0) -- (2) -- (21) (0) -- (3) (3) -- (31) (3) -- (32) (3) -- (33) (3) -- (34) (32) -- (321) -- (3211) (321) -- (3212) ; % \draw[fill=black] % (0) circle (1pt) (1) circle (1pt) (11) circle (1pt) (12) circle (1pt) (121) circle (1pt) (122) circle (1pt) (123) circle (1pt) (2) circle (1pt) (3) circle (1pt) (32) circle (1pt) (321) circle (1pt) (21) circle (1pt) (31) circle (1pt) (33) circle (1pt) (34) circle (1pt) (3211) circle (1pt) (3212) circle (1pt) ; \draw(0) node [rectangle, scale=.5, fill=black, draw]{}; % % Labels \draw (0) node[below] {0} (1) node[below] {1} (11) node[left] {2} (12) node[below] {3} (121) node[above] {4} (122) node[above] {5} (123) node[above] {6} (2) node[left] {7} (21) node[left] {8} (3) node[below] {9} (31) node[left] {10} (32) node[left] {11} (321) node[left] {12} (3211) node[above] {13} (3212) node[above] {14} (33) node[right] {15} (34) node[right] {16} ; \end{tikzpicture} % \hfill{} \end{footnotesize} \caption{Un arbre non croisé (avec ses sommets numérotés dans l'ordre horaire) et sa forme, qui est son arbre plan associé (avec ses sommets numérotés dans l'ordre lexicographique).} \label{fig:arbres} \end{figure} Marckert \& Panholzer \cite{MP02} ont prouvé que la forme d'un arbre non croisé uniforme à $n$ sommets est un $\GW$ arbre conditionné à avoir $n$ sommets, mais légèrement modifié (la racine a une loi de reproduction différente $\mu_{\emptyset}(k)=2 \cdot 3^{-k}$ avec $k \geq 1$, et $\mu(k)=4 (k+1) 3^{-(k+2)} $ avec $k \geq 0$ pour les autres sommets), ce qui a permis d'étudier les arbres non croisés uniformes grâce aux techniques des $\GW$ arbres conditionnés. Voir \cite{CK14,KM15b} pour d'autres applications. \subsection{Dissections} Pour tout entier $n \geq 3$, notons $P_{n}$ le polygone formé par les racines $n$-ièmes complexes de l'unité. Par définition, une \emph{dissection} de~$P_{n}$ est l'union des côtés de~$P_{n}$ et d'une collection de diagonales dont deux quelconques ne peuvent pas se croiser intérieurement. \begin{figure}[htb] \centering \includegraphics[scale=0.7]{dissectionpdf2} \caption{\label{fig:dual} L'arbre dual d'une dissection de $P_{8}$, qui a $7$ feuilles.} \end{figure} À une dissection de $P_{n}$ correspond naturellement un arbre dual avec $n-1$ feuilles (voir figure~\ref{fig:dual}). Dans \cite{Kor11}, il est démontré que l'arbre dual d'une dissection uniforme de $P_{n}$ est un $\GW_{\mu}$ arbre conditionné à avoir $n-1$ feuilles (et non plus un nombre fixé de sommets comme précédemment), où $$\mu(0)= 2- \sqrt{2}, \qquad \mu(1)=0, \qquad \mu(k)= \Big( \frac{2-\sqrt{2}}{2} \Big)^{k-1} \textrm{ pour } k \geq 2.$$ En utilisant des résultats sur les BGW arbres conditionnés à avoir un nombre fixé de feuilles \cite{Riz15,Kor12}, on peut obtenir divers résultats intéressants concernant les dissections aléatoires \cite{CKdissections,CK14,CHK15}. \subsection{Composantes \texorpdfstring{$2$}{2}-connexes de cartes planaires aléatoires} \label{sec:cartes} Nous présentons ici très rapidement le récent article \cite{Add15}, et nous y renvoyons le lecteur pour davantage de précisions. Par définition, une \emph{carte planaire} est un plongement propre d'un graphe fini connexe dans la sphère, vu à homéomorphismes préservant l'orientation près. On dessine souvent les cartes planaires dans le plan par projection stéréographique. Une carte planaire est dite \emph{enracinée} si une arête orientée est distinguée (ceci est utile pour briser les symétries), voir figure~\ref{fig:carte} pour un exemple. On dit qu'une carte planaire $M$ est séparable s'il est possible de disconnecter $M$ en enlevant un sommet de $M$. Si $M$ n'est pas séparable, on dit qu'elle est $2$-connexe. Soit $\mathcal{M}_{n}$ une carte planaire enracinée aléatoire, choisie uniformément au hasard parmi toutes les cartes planaires enracinées à $n$ arêtes (c'est bien un ensemble fini: on~peut démontrer qu'il y en a $\frac{2 \cdot 3^n (2n)!}{(n+2)!n!}$). Que dire de la taille de la plus grande composante $2$-connexe de $\mathcal{M}_{n}$ (mesurée en nombre d'arêtes) ? Plusieurs travaux se sont intéressés à cette question, et Addario-Berry \cite{Add15} a récemment proposé une approche probabiliste, qui permet de retrouver des résultats précédemment obtenus par des outils très techniques de combinatoire analytique \cite{BFS01}. Plus précisément, une décomposition arborescente récursive d'une carte planaire enracinée en composantes $2$-connexes est naturelle: on regarde d'abord la plus grande composante $2$-connexe qui contient la racine, puis on regarde les composantes $2$-connexes maximales adjacentes dans les \og coins \fg\ de celle-ci et ainsi de suite, ce qui nous fournit \emph{l'arbre des blocs $2$-connexes} d'une carte planaire enracinée (voir figure~\ref{fig:blocs}). \begin{figure}[ht] \centering \begin{tabular}{ccc} \includegraphics[width=0.4\linewidth]{carte.pdf} && \includegraphics[width=0.4\linewidth]{carte-decomp.pdf}\\ \subcap{fig:carte} & \quad & \subcap{fig:carte-decomp} \\[0.3cm] \includegraphics[width=0.4\linewidth]{carte-decomp-num.pdf} && \includegraphics[width=0.4\linewidth]{carte-tree.pdf}\\ \subcap{fig:carte-decomp-num} &\quad & \subcap{fig:carte-arbre} \end{tabular} \caption{ \textbf{(a)} Une carte planaire enracinée $M$. \textbf{(b)} La décomposition arborescente de $M$ en blocs $2$-connexes. \textbf{(c)} Numérotation de ces blocs. \textbf{(d)} L'arbre $T(M)$ associé, où les feuilles correspondent à des blocs \og vide \fg.} \label{fig:blocs} \end{figure} Pour une carte enracinée $M$, on note $T(M)$ son arbre des blocs $2$-connexes (voir figure~\ref{fig:carte-arbre} pour un exemple et \cite{Add15} pour une définition formelle). Si $M$ est une carte planaire enracinée avec $n$ arêtes, on voit que $T(M)$ a $2n$ arêtes, et donc $2n+1$ sommets. D'autre part, chaque $u \in T(M)$ qui n'est pas une feuille code un bloc $2$-connexe dans $M$, dont le nombre d'arêtes est le nombre d'enfants de $u$ divisé par $2$. Rappelons que $\mathcal{M}_{n}$ désigne une carte aléatoire choisie uniformément parmi toutes celles à $n$ arêtes. Il se trouve que $T(\mathcal{M}_{n})$ est un $\GW_{\mu}$ arbre conditionné à avoir $2n+1$ sommets, avec $\mu(i)=0$ si $i$ est impair. En posant $\nu(i)=\mu(2i)$ pour $i \geq 0$, en utilisant une formule exacte concernant l'énumération des cartes $2$-connexes avec $n$ arêtes (il~y~en~a $\frac{2(3n-3)!}{n! (2n-1)!}$), on trouve que $$\sum_{i \geq 0} i \nu(i)= \frac{2}{3}, \qquad \nu(n) \quad \mathop{\sim}_{n \rightarrow \infty} \quad \sqrt{ \frac{8}{27\pi}} \cdot n^{-5/2}.$$ Nous sommes donc face à une loi de reproduction sous-critique et à queue lourde. Comme mentionné à la fin du paragraphe \ref{sec:historique}, il s'agit d'un cas où un phénomène de condensation apparaît: lorsque $n \rightarrow \infty$, avec probabilité tendant vers $1$, il va exister un sommet dans $T(\mathcal{M}_{n})$ ayant un nombre macroscopique d'enfants (de l'ordre de $2n/3$ en fait), ce qui se traduit par l'existence d'une unique composante $2$-connexe macroscopique de $\mathcal{M}_{n}$ ayant $n/3$ arêtes. \backmatter \bibliographystyle{jepalpha+eid} \bibliography{xups16-01} \end{document}