#Génération aléatoire d'arbres binaires (1/2) : espérance de la taille

Génération récursive

Considérons le type suivant de squelette d'arbre binaires : un arbre est soit une feuille F soit un nœud N(g,d)g et d sont deux arbres binaires.

On souhaite générer aléatoirement de tels arbres en faisant en sorte que les arbres ne soient pas trop grands. Une méthode raisonnable est la suivante :

let rec genere () =
    if Random.float 1.0 < p
    then N(genere(), genere())
    else F

où $p \in [0,1]$ est la probabilité de générer des nœuds.

Avec $p = \frac{1}{2}$ on obtient donc une fois sur 2 une feuille ce qui peut sembler beaucoup, mais ici l'objectif final, comme on le verra dans un billet ultérieur, est la génération d'arbres de programmes et cela sera plus proche de ce que l'on veut obtenir.

Espérance de la taille de l'arbre

Notons $T$ la variable aléatoire désignant la taille de l'arbre ainsi généré, c'est-à-dire son nombre de nœuds.

On peut alors calculer l'espérance en conditionnant sur le fait que l'arbre soit une feuille ou non :

$$E(T) = p E(1+ Tg + Td)$$

où $Tg$ et $Td$ sont les variables aléatoires indiquant la taille du sous-arbre gauche et du sous-arbre droit quand l'arbre n'est pas réduit à une feuille.

Par linéarité on a donc $E(T) = p(1+E(Tg)+E(Td))$ or, la récursivité de notre construction assure que $E(T) = E(Tg) = E(Td)$ et on a donc $E(T) = p(1+2E(T))$ soit encore

$$E(T) = \frac{p}{1-2p}$$

Cette formule a l'air assez étrange car pour $p = \frac{1}{2}$ elle n'est pas définie et pour $p > \frac{1}{2}$, l'espérance est négative !

Loi de probabilité de la taille

Afin de mieux comprendre la formule précédente on va essayer d'obtenir la loi de probabilité de la taille.

Notons $t_n = P(T = n)$. On a $t_0 = 1-p$.

Pour obtenir $t_n$, où $n \ge 1$. on peut observer que pour que $N(g,d)$ soit de taille $n$ il faut que $|g|+|d| = n-1$. On a donc $$t_n = p \sum_{k=0}^{n-1} t_k t_{n-k}$$

qui ressemble à la récurrence des nombres de Catalan, ce qui semble assez logique vu qu'ils permettent de dénombrer les arbres binaires d'une taille donnée.

On introduit donc $f(z) = \sum_{n=0}^{+\infty} t_n z^n$ et on remarque à l'aide de la relation de récurrence que $\frac{1}{z}(f(z)-t_0) = p f(z)^2$, donc $f(z)$ est racine de $p z f(z)^2 -f(z) + 1- p = 0$, soit encore $$f(z) = \frac{1 \pm \sqrt{1-4 p (1-p) z}}{2 p z}$$

Pour obtenir la bonne expression de $f(z)$ on calcule la limite en $0$ et on cherche l'expression qui donne $t_0 = 1-p$ et on obtient

$$f(z) = \frac{1 - \sqrt{1-4 p (1-p) z}}{2 p z} = \frac{1}{2pz} \left(1- \sum_{n=0}^{\infty} \binom{1/2}{n} (-4p(1-p)z)^n \right)$$

en développant en série entière et en identifiant le coefficient de $z^n$ on a alors

$$t_n = \frac{1}{n+1} \binom{2n}{n} p^{n} (1-p)^{n+1}$$

Par exemple $t_1 = p(1-p)^2, t_2 = 2 p^2 (1-p)^3, ...$.

Espérance de la taille à partir de la loi de probabilité

On peut alors reprendre notre calcul d'espérance $E(T) = \sum_{n=0}^{\infty} n t_n$. On remarque tout d'abord que $n t_n z^{n-1}$ est exactement le terme dérivé de $t_n z^n$, on aimerait donc écrire que $E(T) = f'(1)$ sous réserve que $f$ soit dérivable en 1. Or, en vertu de la racine, on remarque que $f$ est dérivable partout sauf pour $4p(1-p)=1 \iff p = \frac{1}{2}$.

Mais cela ne signifie pas que la série dérivée soit sommable en 1, pour cela on peut commencer par calculer le rayon de convergence de la série entière $\sum_{n=0}^{\infty} (n+1) t_{n+1} z^n$ :

$$\frac{(n+1)t_{n+1}}{n t_n} = \frac{(n+1)^2}{n(n+2)} \frac{\binom{2n+2}{n+1}}{\binom{2n}{n}} p (1-p) = \frac{ (n+1)(2n+2)(2n+1) p (1-p)}{ n^2 (n+2) } \rightarrow 4 p(1-p)$$

On a donc un rayon de convergence $> 1$ si $p \neq \frac{1}{2}$ et ainsi on a bien

$$E(T) = f'(1) = \frac{2p^2 + 1 - 2p + |1 - 2p|}{2p|1-2p|} = \begin{cases} \frac{p}{1-2p} & \text{si } p < \frac{1}{2} \\ \frac{(1-p)^2}{p(2p-1)} & \text{sinon} \end{cases}$$

Terminaison de l'algorithme

Cette formule de l'espérance a l'avantage de ne garder que des valeurs positives. Par contre, une chose semble étrange : pour $p > \frac{1}{2}$ il assez clair que l'algorithme a peu de chance de terminer. Pourtant, nous avons réussi à associer une espérance dans ce cas.

Implicitement, dans notre calcul de l'espérance, nous avons supposé que $T$ prenait des valeurs finis dans $\mathbb{N}$. Donc, en fin de compte ce qu'on a calculé c'est une espérance conditionnelle : l'espérance de $T$ sachant que l'algorithme termine !

On peut convenir rapidement que l'algorithme termine toujours quand $p < \frac{1}{2}$ et que l'espérance que l'on a calculé est bien l'espérance non conditionnelle. Pour $p > \frac{1}{2}$, l'algorithme ne termine pas et $E(T) = +\infty$.

Mais alors, que dire du cas $p = \frac{1}{2}$ ? Pour cela, on peut introduire $q$ la probabilité que l'algorithme termine. En conditionnant on obtient rapidement $q = 1- p + pq^2$ ce qui donne

$$q = \begin{cases} 1 & \text{si } p < \frac{1}{2} \\ \frac{1-p}{p} & \text{sinon} \end{cases}$$

et on voit donc que $q = 1$ pour $p = \frac{1}{2}$. Donc l'algorithme termine pour $p = \frac{1}{2}$ mais les arbres sont suffisamment grands pour que $E(T) = +\infty$.

Vérification par des calculs

Pour vérifier tous ces résultats, rien de mieux qu'une simulation. Dans le cas où l'algorithme termine c'est assez facile mais quand il peut diverger il faut mettre en place une protection contre les récursions infinis. Naïvement, on peut donc écrire :

exception Stop

let genere_wd n p =
    let compteur = ref 0 in
    let rec aux () =
        incr compteur;
        if !compteur > n
        then raise Stop
        else if Random.float 1.0 < p
             then N(aux (), aux ())
             else F
    in aux ()

Malheureusement, pour des valeurs assez grandes de $n$ on dépasse la capacité de la pile. Une manière de le faire serait donc de remplacer la récursion de aux par une récursion terminale afin de supprimer l'usage de la pile. Pour cela, on utilise des continuations : aux va prendre en accumulateur un arbre partiel sous la forme d'une fonction de type f : arbre -> arbre. Un appel f a permettant de compléter l'arbre et de renvoyer une valeur. Pour initialiser cet accumulateur il suffit de passer la fonction identité.

On obtient ainsi le code suivant :

let genere_wd n p = 
    let compteur = ref 0 in
    let rec aux f = 
        incr compteur;
        if !compteur > n
        then raise Stop
        else
            if Random.float 1.0 < p
            then aux (fun d -> aux (fun g -> f (N(g, d))))
            else f F
    in aux (fun x -> x)

L'ensemble des expressions obtenues précédemment a alors pu être vérifié expérimentalement.