<figure><img src="image_1.png" /></figure>

HAL
open science

# Random generation of combinatorial objects: Hadamard product under Boltzmann distributions

Nasr-Allah Hitar

► To cite this version:

Nasr-Allah Hitar. Random generation of combinatorial objects: Hadamard product under Boltzmann distributions. Laboratoire bordelais de recherche en informatique (LaBRI), Domaine universitaire, 351 cours de la Libération, 33405 Talence. 2025. hal-05170185

HAL Id: hal-05170185

https://hal.science/hal-05170185v1

Submitted on 18 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Génération aléatoire des objets combinatoires :
produit de Hadamard sous loi de Boltzmann

## Auteur :

Nasr-allah HITAR

LABORATOIRE BORDELAIS DE RECHERCHE EN INFORMATIQUE
UNIVERSITÉ DE BORDEAUX
BORDEAUX-INP – ENSEIRB-MATMECA

Sous la direction de : M.Philippe DUCHON
# Génération aléatoire des objets combinatoire : produit de Hadamard sous loi de Boltzmann

Nasr-allah, Hitar

July 17, 2025

## Abstract

Nous étudions la génération aléatoire d'objets combinatoires sous loi de Boltzmann. Nous concentrons sur la simulation des produits de Hadamard, en utilisent l'approche classique de Duchon et en grâce aux techniques de boîte noire de Sportiello pour la génération des objets suivant des distributions de Boltzmann dans des constructions de produits de Hadamard.

## Introduction

La génération aléatoire d'objets combinatoires constitue un outil fondamental en informatique théorique, avec des applications allant du test d'algorithmes à la simulation de structures discrètes aléatoire et complexes. Parmi les paradigmes existants, la génération de Boltzmann [Duc+04], initiée par Duchon, Flajolet, Louchard et Schaeffer, offre un cadre élégant pour une génération non biaisée où la taille des objets est contrôlée par un paramètre réel $x$.

Ce travail se concentre sur le problème de générer des paires $(a, b) \in \mathcal{A} \times \mathcal{B}$ avec des tailles identiques $|a| = |b|$ – équivalent à générer le produit de Hadamard $\mathcal{H} = \mathcal{A} \odot \mathcal{B}$ dont la série génératrice est $H(x) = \sum_{n \ge 0} a_n b_n x^n$. Bien que l'approche classique par rejet fournisse une solution de ce problème, sa complexité temporelle évolue inversement à la probabilité de succès $P(|a|=|b|)$, devenant plus difficile en terme de complexité pour les grands objets.

Nous présentons une analyse complète de techniques améliorées, notamment la méthodologie en boîte noire de Sportiello [Spo16] en appliquant cette méthodologie à des objets combinatoire sous Boltzmann (arbre, mot d'une langage régulier ..etc). Cette méthodologie de Sportiello [Spo16] exploite la poissonnisation de taille des objets générée aléatoire afin de paramétreser la compléxité de l'algorithme pour une meilleur efficacité. En découplant les contraintes de taille via des distributions de Poisson et en optimisant les paramètres $(\lambda, \mu)$, nous développons les algorithmes de la génération aléatoire avec étude d'espérance de complexité tout en garantissant une génération de la distribution souhaitée. L'analyse théorique des distributions de taille, propriétés des moments et conditions de terminaison est complétée par des implémentations pratiques des constructions combinatoires (unions, produits, séquences) et leurs générateurs de Boltzmann.

**Remerciements.** Je tiens à exprimer ma profonde gratitude à M. Philippe Duchon pour sa proposition de ce sujet et son encadrement expert, ses conseils précieux et ses retours perspicaces tout au long de ce stage de recherche. Ses travaux fondateurs sur la génération de Boltzmann ont fourni le cadre essentiel à cette étude. Je remercie également le Laboratoire Bordelais de Recherche en Informatique (LaBRI) pour son environnement de recherche exceptionnel. Un merci particulier à mes collègues stagiaires du LaBRI pour leur camaraderie et nos discussions stimulantes durant nos heures de bureau partagées – notre atmosphère collaborative a grandement enrichi cette expérience de recherche.
Notations

$\mathscr{C}, \mathcal{A}, \mathcal{B}$ Classes combinatoires

$|\gamma|$ Taille d'un objet combinatoire $\gamma$

$\mathscr{C}_n$ Ensemble des objets de taille $n$ dans $\mathscr{C}$

$c_n, a_n, b_n$ Cardinalité de $\mathscr{C}_n, \mathcal{A}_n, \mathcal{B}_n$ respectivement

$\rho_{\mathscr{C}}$ Rayon de convergence de la série génératrice

$\mathbb{P}_x$ Loi de Boltzmann paramétrée par $x$

$C(x), \hat{C}(x)$ Séries génératrices (ordinaire/exponentielle) :

$$
C(x) = \sum_{\gamma \in \mathscr{C}} x^{|\gamma|}, \quad \hat{C}(x) = \sum_{\gamma \in \mathscr{C}} \frac{x^{|\gamma|}}{|\gamma|!}
$$

$\mathscr{A} \odot \mathscr{B}$ Produit de Hadamard

$$
\mathcal{A} \odot \mathcal{B} = \bigcup_{n \ge 0} (A_n \times B_n)
$$

$N^{(k)}$ Moment factoriel d'ordre $k$ :

$$
\begin{align*}
\mathbb{E}_x[N^{(k)}] &= \mathbb{E}_x[N(N-1)\cdots(N-k+1)] \\
&= \frac{x^k C^{(k)}(x)}{C(x)}
\end{align*}
$$

Arbre étiqueté Arbre avec labels distincts sur les nœuds

(Série génératrice exponentielle $\hat{C}(x)$)

Arbre non étiqueté Arbre sans distinction des labels

(Série génératrice ordinaire $C(x)$)

$\mathcal{U}([0, 1])$ Loi uniforme continue sur $[0, 1]$

$\mathcal{P}(\lambda)$ Loi de Poisson de paramètre $\lambda$

Geom($p$) Loi géométrique de paramètre $p$

$C_n$ Nombre de Catalan d'ordre $n$

$F_n$ $n$-ième nombre de Fibonacci

$\lambda, \mu$ Paramètres de Poisson (technique Sportiello)

$C_n^A \sim \mathcal{P}(\lambda p_n), \quad C_n^B \sim \mathcal{P}(\mu q_n)$ Compteurs de valeurs

$P_{\text{succès}}$ Probabilité de succès (algorithme Sportiello)
# Contents

Notations 3

1 Structures combinatoires et principes de la génération de Boltzmann 5

1.1 Définitions fondamentales 5

1.2 Propriétés des séries génératrices 5

1.3 Propriétés statistiques de la taille 5

1.4 Constructions combinatoires fondamentales 6

1.5 Algorithmes de simulation 7

1.6 Exemple : Génération d'arbres binaires et mots de Fibonacci 10

1.6.1 Arbres binaires 10

1.6.2 Langage de Fibonacci 11

2 Algorithme optimal pour le produit de Hadamard (version moins naïve) 15

2.1 Simulation des algorithmes 20

2.2 Produit de Hadamard sous loi de Boltzmann 22

2.2.1 Générateurs de Boltzmann spécifiques 22

2.2.2 Étude asymptotique des espérances 23

2.2.3 Optimisation par poissonisation (Sportiello) 23
# 1 Structures combinatoires et principes de la génération de Boltzmann

## 1.1 Définitions fondamentales

**Définition 1 (Classe combinatoire)** Une classe combinatoire $\mathcal{C}$ est un ensemble dénombrable d'objets discrets munis d'une application taille $| \cdot | : \mathcal{C} \to \mathbb{N}$. On note $\mathcal{C}_n = \{\gamma \in \mathcal{C} : |\gamma| = n\}$ l'ensemble des objets de taille n, l'ensemble $\mathcal{C}_n$ doit être fini $\forall n \in \mathbb{N}$.

**Définition 2 (Loi de Boltzmann)** Pour une classe combinatoire $\mathcal{C}$ et un paramètre $x > 0$, la loi de Boltzmann est définie par (Duchon, Flajolet, Louchard, Schaeffer – 2004): [Duc+04]

* **Structures non-étiquetées:**

$$ \mathbb{P}_x(\gamma) = \frac{x^{|\gamma|}}{C(x)}, \quad C(x) = \sum_{\gamma \in \mathcal{C}} x^{|\gamma|} = \sum_{n \ge 0} c_n x^n $$

* **Structures étiquetées:**

$$ \mathbb{P}_x(\gamma) = \frac{x^{|\gamma|} / |\gamma|!}{\hat{C}(x)}, \quad \hat{C}(x) = \sum_{\gamma \in \mathcal{C}} \frac{x^{|\gamma|}}{|\gamma|!} $$

où $C(x)$ et $\hat{C}(x)$ sont les séries génératrices ordinaires et exponentielles.

**Définition 3 (Générateur de Boltzmann)** Un générateur de Boltzmann $\Gamma\mathcal{C}(x)$ est un algorithme qui produit des objets $\gamma \in \mathcal{C}$ suivant la loi $\mathbb{P}_x$. Les objets de même taille sont générés uniformément.

**Proposition 1 (Domaine de définition)** Le paramètre $x$ doit appartenir à $[0, \rho_{\mathcal{C}})$ où $\rho_{\mathcal{C}}$ est le rayon de convergence de $C(x)$.

## 1.2 Propriétés des séries génératrices

**Remarque 1 (Évaluation efficace)** Le calcul numérique des séries génératrices peut être réalisé par des méthodes itératives (Newton) avec une complexité inférieure à l'extraction des coefficients. [PSS12]

## 1.3 Propriétés statistiques de la taille

**Proposition 2 (Loi de la taille)** Soit $N$ la variable aléatoire représentant la taille d'un objet généré. Alors:

$$ \mathbb{P}_x(N = n) = \frac{c_n x^n}{C(x)} \\ \mathbb{E}_x[u^N] = \frac{C(ux)}{C(x)} $$

**Proposition 3 (Moments factoriels)** Les moments factoriels s'expriment analytiquement:

$$ \mathbb{E}_x[N^{(k)}] = \frac{x^k C^{(k)}(x)}{C(x)} $$

Les moments ordinaires se déduisent via les nombres de Stirling:

$$ \mathbb{E}_x[N^k] = \sum_{i=1}^{k} \binom{k}{i} \mathbb{E}_x[N^{(i)}] $$
**Proposition 4 (Monotonie)** L'espérance $\mathbb{E}_x[N]$ est strictement croissante sur $[0, \rho_\epsilon)$. Pour générer de grands objets, on choisit $x$ proche de $\rho_\epsilon$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Modulation de la distribution des tailles par le paramètre de Boltzmann $x$ pour des langages finis. pris de Pivoteau (2008) [Piv08].</figcaption></figure>

## 1.4 Constructions combinatoires fondamentales

**Définition 4 (Opérations de base)** Les opérations combinatoires élémentaires induisent des séries génératrices et des générateurs spécifiques:

<table><caption>Table 1: Constructeurs combinatoires et leurs générateurs de Boltzmann [Duc+04]</caption><thead><tr><th>Construction combina-toire</th><th>Spécification du générateur</th></tr></thead><tbody><tr><td>Classe singleton C = {ω}</td><td>ΓC(x) → ω</td></tr><tr><td>Union disjointe C = A + B</td><td>ΓC(x) = <span style="font-size: 2em; vertical-align: middle;">{</span> ΓA(x) prob A(x)/(A(x) + B(x))<br>ΓB(x) sinon</td></tr><tr><td>Produit cartésien C = A × B</td><td>ΓC(x) = (ΓA(x), ΓB(x))</td></tr><tr><td>Séquence C = SEQ(A)</td><td>ΓC(x) = (K ~ Geom(A(x)), K instances de ΓA(x))</td></tr></tbody></table>

<table><caption>Table 2: Séries génératrices pour les constructions combinatoires [Duc+04]</caption><thead><tr><th>Construction combina-toire</th><th>Série génératrice</th></tr></thead><tbody><tr><td>Union disjointe C = A + B</td><td>C(x) = A(x) + B(x)</td></tr><tr><td>Séquence C = SEQ(A)</td><td>C(x) = (1 - A(x))<sup>-1</sup></td></tr><tr><td>Multiensemble C = MSET(A)</td><td>C(x) = exp(∑<sub>k=1</sub><sup>∞</sup> <sup>(-1)<sup>k+1</sup></sup>/<sub>k</sub> A(x<sup>k</sup>))</td></tr><tr><td>Cycle C = CYC(A)</td><td>C(x) = ∑<sub>k=1</sub><sup>∞</sup> <sup>φ(k)</sup>/<sub>k</sub> log(1 - A(x<sup>k</sup>))<sup>-1</sup></td></tr></tbody></table>
## 1.5 Algorithmes de simulation

Cette section présente les algorithmes fondamentaux pour la génération aléatoire en générale afin d'étudier la génération sous loi de Boltzmann. Les constructions combinatoires de base (singleton, union, produit, séquence) sont implémentées via des générateurs probabilistes.

**Théorème 1 (Théorème fondamental de la simulation)** Soit $X$ une variable aléatoire à valeurs dans $\mathbb{R}^d$ de loi $\mu$ absolument continue par rapport à une mesure dominante $\lambda$. Alors il existe un algorithme permettant de simuler $X$ à partir de variables aléatoires uniformes indépendantes.

**Théorème 2 (Fonction quantile)** Soit $F_X$ une fonction de répartition continue strictement croissante. Définissons la fonction quantile :

$$Q(u) = \inf\{x \in \mathbb{R} : F_X(x) \geq u\}, \quad u \in (0, 1)$$

Alors $Q$ vérifie :

$$F_X(Q(u)) = u \qquad (1)$$

$$Q(F_X(x)) = x \qquad (2)$$

**Preuve 1** L'équation (1) découle de la définition et de la continuité à droite. L'équation (2) résulte de la stricte croissance et continuité.

**Algorithm 1** Simulation par transformation inverse

**Require:** $F_X^{-1}$ : fonction quantile de la loi cible

**Ensure:** $X$ : variable aléatoire suivant $F_X$

1: Générer $U \sim U([0, 1])$

▷ Variable uniforme

2: $X \leftarrow F_X^{-1}(U)$

▷ Application de la fonction quantile

3: return $X$

**Théorème 3 (Correction de l'algorithmme)** Pour tout $x \in \mathbb{R}$, $P(X \leq x) = F_X(x)$

**Preuve 2** Soit $U \sim U([0, 1])$ et $X = F_X^{-1}(U)$. Alors :

$$ \begin{aligned} P(X \leq x) &= P(F_X^{-1}(U) \leq x) \\ &= P(U \leq F_X(x)) \quad (\text{par monotonie de } F_X \text{ et propriété (1)}) \\ &= F_X(x) \quad (\text{car } P(U \leq u) = u \text{ pour } U \sim U([0, 1])) \end{aligned} $$

La deuxième égalité utilise la propriété fondamentale :

$$\{\omega : F_X^{-1}(U(\omega)) \leq x\} = \{\omega : U(\omega) \leq F_X(x)\}$$

qui est vraie car :

∴ Si $u \leq F_X(x)$, alors $F_X^{-1}(u) \leq x$ par définition de l'infimum

∴ Si $F_X^{-1}(u) \leq x$, alors $u \leq F_X(F_X^{-1}(u)) \leq F_X(x)$ par croissance de $F_X$

Dans la suite, on va appliquer cette théorème pour des lois classique (Bernoulli, Géometrique, Poisson ...)
**Algorithm 2** Loi de Bernoulli

**Require:** $p \in [0, 1]$ (probabilité de succès)

**Ensure:** $b \in \{0, 1\}$ (résultat du tirage)

1: Générer $u \sim \text{Uniforme}(0, 1)$

2: **if** $u < p$ **then**

3: **return** 1

4: **else**

5: **return** 0

6: **end if**

▷ Succès

▷ Échec

**Algorithm 3** Loi Géométrique

**Require:** $p \in [0, 1)$ (probabilité de succès)

**Ensure:** $k \in \mathbb{N}$ (nombre de succès consécutifs)

1: $k \leftarrow 0$

2: **while** Bernoulli($p$) = 1 **do**

3: $k \leftarrow k + 1$

4: **end while**

5: **return** $k$

**Algorithm 4** Simulation de Poisson par méthode de rejet (Knuth)

**Require:** $\lambda > 0$

**Ensure:** $X \sim \mathcal{P}(\lambda)$

1: $L \leftarrow e^{-\lambda}$

2: $k \leftarrow 0$

3: $p \leftarrow 1$

4: **repeat**

5: $k \leftarrow k + 1$

6: Générer $U_k \sim \mathcal{U}([0, 1])$

7: $p \leftarrow p \times U_k$

8: **until** $p \le L$

9: **return** $k - 1$

**Algorithm 5** Générateur Singleton ($C = \{\omega\}$)

**Require:** $\omega$ (objet unique)

**Ensure:** Objet combinatoire

1: **return** $\omega$

**Théorème 4** [*Duc+04*] soit $(C, |\cdot|)$ une classe combinatoire, **non étiquetée** , telle que la construction $C$ définie récursivement par : $\varepsilon, \mathcal{Z}, +, \times, \text{SEQ}, \text{CYC}, \text{MSET}$ alors : le générateur de Boltzmann $\Gamma C$ opère en temps linéaire par rapport à $|\cdot|$.
**Algorithm 6** Générateur d'Union ($\mathcal{C} = \mathcal{A} + \mathcal{B}$)

**Require:**

$\Gamma_A$ (générateur pour $\mathcal{A}$)

$\Gamma_B$ (générateur pour $\mathcal{B}$)

$A(x)$ (valeur de la série génératrice)

$B(x)$ (valeur de la série génératrice)

$x$ (paramètre de Boltzmann)

**Ensure:** Objet de $\mathcal{A}$ ou $\mathcal{B}$

1: $p \leftarrow A(x)/(A(x) + B(x))$

2: **if** Bernoulli($p$) = 1 **then**

3: **return** $\Gamma_A(x)$

4: **else**

5: **return** $\Gamma_B(x)$

6: **end if**

**Algorithm 7** Générateur de Produit ($\mathcal{C} = \mathcal{A} \times \mathcal{B}$)

**Require:**

$\Gamma_A$ (générateur pour $\mathcal{A}$)

$\Gamma_B$ (générateur pour $\mathcal{B}$)

$x$ (paramètre de Boltzmann)

**Ensure:** Paire ordonnée d'objets

1: $a \leftarrow \Gamma_A(x)$

2: $b \leftarrow \Gamma_B(x)$

3: **return** $(a, b)$

**Algorithm 8** Générateur de Séquence ($\mathcal{C} = \text{SEQ}(\mathcal{A})$)

**Require:**

$\Gamma_A$ (générateur pour $\mathcal{A}$)

$A(x)$ (valeur de la série génératrice)

$x$ (paramètre de Boltzmann)

**Ensure:** Liste d'objets

1: $k \leftarrow \text{Géométrique}(A(x))$

▷ Nombre de composantes

2: Initialiser liste vide $L$

3: **for** $i \leftarrow 1$ **à** $k$ **do**

4: $a \leftarrow \Gamma_A(x)$

5: Ajouter $a$ à $L$

6: **end for**

7: **return** $L$

<table><caption>Table 3: Complexité des générateurs de Boltzmann</caption><thead><tr><td>Opération</td><td>Coût moyen</td></tr></thead><tbody><tr><td>Singleton</td><td>O(1)</td></tr><tr><td>Union</td><td>O(1) + coût de la branche choisie</td></tr><tr><td>Produit</td><td>O(1) + coût(ΓA) + coût(ΓB)</td></tr><tr><td>Séquence</td><td>E[k] · coût(ΓA)</td></tr></tbody></table>
Remarque 2 La complexité des algorithmes dépend fortement au l’évaluation de la série génératrices. Les constructions récursives nécessitent une analyse soigneuse de la terminaison.

# 1.6 Exemple : Génération d'arbres binaires et mots de Fibonacci

## 1.6.1 Arbres binaires

Les opérations combinatoires précédentes permettent de construire des générateurs pour diverses structures. Considérons la classe $\mathcal{B}$ des arbres binaires définis récursivement :

* Un arbre vide (taille 0), ou

* Un nœud racine avec deux sous-arbres

L'équation combinatoire correspondante :

$$ \mathcal{B} = \{\epsilon\} + \bullet \times \mathcal{B} \times \mathcal{B} $$

donne la série génératrice :

$$ B(z) = 1 + zB(z)^2 = \frac{1 - \sqrt{1 - 4z}}{2z} $$

dont le développement en série :

$$ B(z) = 1 + \sum_{n=1}^{\infty} C_n z^n, \quad |z| < \frac{1}{4} $$

fait apparaître les nombres de Catalan $C_n = \binom{2n}{n}$.

**Proposition 5 (Bijection combinatoire)** *Les nombres de Catalan énumèrent :*

* Les arbres binaires à n nœuds internes

* Les expressions parenthésées valides de longueur 2n

**Exemple (n=3)** : Les 5 expressions valides :

(())() ()()() ()()() ()()() ((()))

La bijection provient du parcours infixe : nœud → (sous-gauche sous-droit).

Sous Boltzmann, la probabilité de générer un arbre de taille n est :

$$ \mathbb{P}(|\mathcal{T}| = n) = \frac{C_n z^n}{B(z)} $$

Le paramètre $z \in [0, \frac{1}{4})$ contrôle la distribution des tailles.
### 1.6.2 Langage de Fibonacci

Considérons le langage $\mathcal{F}$ sur l'alphabet $\Sigma = \{a, b\}$ sans deux $a$ consécutifs, décrit par l'expression rationnelle $(b | ab)^*(a | \epsilon)$. Sa spécification combinatoire est donnée par :

$$ \mathcal{F} = \{\epsilon\} \cup \{a\} \cup \{b\} \times \mathcal{F} \cup \{a\} \times \{b\} \times \mathcal{F} $$

**Proposition 6 (Série génératrice)** La série génératrice de $\mathcal{F}$ satisfait l'équation :

$$ F(z) = 1 + z + zF(z) + z^2F(z) $$

d'où l'on déduit :

$$ F(z) = \frac{1+z}{1-z-z^2} = \sum_{n \ge 0} f_n z^n $$

avec $f_n = F_{n+2}$ où $F_n$ est la suite de Fibonacci (définie par $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, $F_3 = 2$, ...).

**Interprétation combinatoire :**

* $f_0 = 1$ : mot vide $\epsilon$

* $f_1 = 2$ : mots "a", "b"

* $f_2 = 3$ : mots "bb", "ab", "ba" (le mot "aa" est interdit)

* $f_3 = 5$ : mots "bbb", "abb", "bab", "bba", "aba"

**Théorème fondamental** Tout langage régulier admet une série génératrice qui est une fraction rationnelle, c'est-à-dire un quotient de deux polynômes. Ce résultat découle de la clôture des langages réguliers sous les opérations rationnelles et de la correspondance avec les automates finis.

**Automate fini déterministe** Le langage $\mathcal{F}$ est reconnu par l'automate fini suivant :

<figure><img src="image_3.png" /></figure>

**Description des états :**

* $q_0$ : état initial et final, correspond aux mots se terminant par $b$ ou au mot vide

* $q_1$ : état final, correspond aux mots se terminant par $a$

**Calcul de la série génératrice via l'automate** Soient $S_0(z)$ et $S_1(z)$ les séries génératrices associées aux états $q_0$ et $q_1$ respectivement. Ces séries comptent les mots reconnus en partant de chaque état. On établit le système d'équations :

$$ S_0(z) = 1 + zS_0(z) + zS_1(z) $$

$$ S_1(z) = zS_0(z) $$
**Méthode générale :**

∴ Le terme 1 dans $S_0(z)$ : le mot vide (qui est accepté)

∴ $zS_0(z)$ : lecture d'un b (de longueur 1) et on reste dans l'état $q_0$

∴ $zS_1(z)$ : lecture d'un a (de longueur 1) et transition vers $q_1$

∴ Dans $S_1(z)$ : à partir de $q_1$, on ne peut lire qu'un b (de longueur 1) qui nous ramène à $q_0$

En substituant $S_1(z)$ dans la première équation :

$$S_0(z) = 1 + zS_0(z) + z(zS_0(z)) = 1 + zS_0(z) + z^2S_0(z)$$

d'où :

$$S_0(z)(1 - z - z^2) = 1 \implies S_0(z) = \frac{1}{1 - z - z^2}$$

et

$$S_1(z) = z \cdot \frac{1}{1 - z - z^2}$$

La série génératrice du langage est la somme des séries des états finaux :

$$F(z) = S_0(z) + S_1(z) = \frac{1}{1 - z - z^2} + \frac{z}{1 - z - z^2} = \frac{1 + z}{1 - z - z^2}$$

ce qui confirme le résultat obtenu par l'équation combinatoire. Cette série est bien une fraction rationnelle, comme attendu pour un langage régulier.
## Énoncé du problème

Étant données deux classes combinatoires $\mathcal{A}$ et $\mathcal{B}$, concevoir un algorithme pour générer des paires aléatoires $(a, b) \in \mathcal{A} \times \mathcal{B}$ telles que $|a| = |b|$.

## Définition formelle

Le produit de Hadamard $\mathcal{H} = \mathcal{A} \odot \mathcal{B}$ a pour série génératrice :

$$H(x) = \sum_{n=0}^{\infty} a_n b_n x^n$$

où $a_n = |\mathcal{A}_n|$ et $b_n = |\mathcal{B}_n|$ sont les cardinalités des objets de taille $n$.

**Algorithm 9** La génération de produit de Hadamard par série génératrice

**Require:**

$\mathcal{A}, \mathcal{B}$: Classes combinatoires

$x$: Paramètre de Boltzmann ($0 < x < \rho_{\mathcal{H}}$)

**Ensure:** Paire $(a, b) \in \mathcal{A} \times \mathcal{B}$ avec $|a| = |b|$ ou NULL en cas d'échec

1: Calculer $H = \sum_{n=0}^{\infty} a_n b_n x^n$ ▷ Série génératrice complète

2: générer $n \sim \text{ProduitDeHadamard}(\mathbb{P}(N = k) = \frac{a_k b_k x^k}{H}$ pour $k \in \mathbb{N}$)

3: $a \leftarrow \text{GÉNÉRATEURUNIFORME}(\mathcal{A}, n)$

4: $b \leftarrow \text{GÉNÉRATEURUNIFORME}(\mathcal{B}, n)$

5: **if** $a \neq \text{NULL}$ et $b \neq \text{NULL}$ **then**

6: **return** $(a, b)$

7: **end if**

l'algorithme 9 consiste à générer un entier $n \in \mathbb{N}$ suivant la distribution du produit de Hadamard des deux distributions de Boltzmann de la classe de l'entrer afin de générer d'une manière uniforme deux éléments des classes combinatoires $(\mathcal{A}, \mathcal{B})$ de même taille, maintenant le problème dans la manière d'imaginer l'algorithme qui simule la boite noire résultant qui simule bien le produit de Hadamard des deux distributions. On proposons dans cette partie un algorithme naïve qui génère bien le produit de Hadamard sous loi de Boltzmann.

**Algorithm 10** Générateur de paires par rejet pour le produit de Hadamard

**Require:**

$\Gamma\mathcal{A}$ : Générateur de Boltzmann pour la classe $\mathcal{A}$

$\Gamma\mathcal{B}$ : Générateur de Boltzmann pour la classe $\mathcal{B}$

$x$: Paramètre de Boltzmann ($0 < x < \rho_{\mathcal{A}}, \rho_{\mathcal{B}}$)

**Ensure:** Une paire $(a, b) \in \mathcal{A} \times \mathcal{B}$ avec $|a| = |b|$, suivant la distribution conditionnelle de la loi de Boltzmann.

1: $(a, b) \leftarrow (\text{null}, \text{null})$

2: **repeat**

3: $a \leftarrow \Gamma\mathcal{A}(x)$ ▷ Générer $a$ selon la loi de Boltzmann

4: $b \leftarrow \Gamma\mathcal{B}(x)$ ▷ Générer $b$ selon la loi de Boltzmann

5: **until** $|a| = |b|$ **return** $(a, b)$
**Proposition 7** L'algorithme 10 simule bien le produit de Hadamard (correct) , et pour tout entrer l'événement "l'algorithme 10 termine" est presque sur.

**Preuve 3** Soit $(a^*, b^*)$ une paire d'objets de taille $n$ ($|a^*| = |b^*| = n$). La probabilité que l'algorithme retourne cette paire est :

$$
\begin{align*}
\mathbb{P}[(a, b) = (a^*, b^*)] &= \sum_{k=0}^{\infty} \mathbb{P}[k \text{ rejets}] \cdot \mathbb{P}[\text{générer } (a^*, b^*) \text{ à l'itération } k + 1] \\
&= \sum_{k=0}^{\infty} (1 - p_{\text{succ}})^k \cdot \mathbb{P}_x(a = a^*) \mathbb{P}_x(b = b^*)
\end{align*}
$$

où $p_{succ} = \mathbb{P}(|a| = |b|)$ est la probabilité de succès par itération.

Par la loi de Boltzmann :

$$
\mathbb{P}_x(a = a^*) = \frac{x^n}{A(x)}, \quad \mathbb{P}_x(b = b^*) = \frac{x^n}{B(x)}
$$

$$
\text{avec } A(x) = \sum_{\gamma \in A} x^{|\gamma|}, \quad B(x) = \sum_{\gamma \in B} x^{|\gamma|}.
$$

La série géométrique donne :

$$
\mathbb{P}[(a, b) = (a^*, b^*)] = \frac{1}{p_{\text{succ}}} \cdot \frac{x^{2n}}{A(x)B(x)}
$$

La probabilité conditionnelle sachant succès est :

$$
\mathbb{P}[(a, b) = (a^*, b^*) | |a| = |b|] = \frac{\mathbb{P}[(a, b) = (a^*, b^*)]}{p_{\text{succ}}} = \frac{x^{2n}}{A(x)B(x)p_{\text{succ}}}
$$

Or la probabilité théorique dans le produit de Hadamard est :

$$
\mathbb{P}_{\text{Hadamard}}(a^*, b^*) = \frac{x^{|a^*| + |b^*|}}{\sum_k a_k b_k x^{2k}} = \frac{x^{2n}}{H(x^2)}
$$

$$
\text{où } H(z) = \sum_{k=0}^{\infty} a_k b_k z^k.
$$

Puisque $p_{\text{succ}} = \sum_{k=0}^{\infty} \frac{a_k x^k b_k x^k}{A(x) B(x)} = \frac{H(x^2)}{A(x) B(x)}$, on obtient :

$$
\mathbb{P}[(a, b) = (a^*, b^*) | |a| = |b|] = \frac{x^{2n}}{A(x)B(x) \cdot \frac{H(x^2)}{A(x)B(x)}} = \frac{x^{2n}}{H(x^2)} = \mathbb{P}_{\text{Hadamard}}(a^*, b^*)
$$

terminaison : Soit $p_{\text{succ}} = \mathbb{P}(|a| = |b|) > 0$. Le nombre d'itérations T suit une loi géométrique

:

$$
\mathbb{P}(T = k) = (1 - p_{\text{succ}})^{k-1} p_{\text{succ}} \quad \text{pour } k = 1, 2, 3, \dots
$$

La probabilité de terminaison est :

$$
\mathbb{P}(T < \infty) = \sum_{k=1}^{\infty} \mathbb{P}(T = k) = p_{\text{succ}} \sum_{k=0}^{\infty} (1 - p_{\text{succ}})^k = p_{\text{succ}} \cdot \frac{1}{p_{\text{succ}}} = 1
$$

L'espérance du nombre d'itérations est :

$$
\mathbb{E}[T] = \frac{1}{p_{\text{succ}}} = \frac{A(x)B(x)}{H(x^2)} < \infty \quad \text{car } H(x^2) > 0
$$
Cet algorithme représente une approche théoriquement élégante pour la génération uniforme, initialement proposée par Duchon. Cependant, sa complexité pratique dépend cruciallement du calcul exact des coefficients $a_n b_n$ et de la sommation de la série (dépend inversement que de $\frac{1}{\sum_{n \in \mathbb{N}} a_n b_n}$, ce qui peut s'avérer prohibitif pour de nombreuses classes combinatoires (si $\sum_{n \in \mathbb{N}} a_n b_n$ est petite alors le temps d'exécution peut tendre vers l'infinie). Pour contourner cette limitation, nous nous tournons vers le cadre de Sportiello pour les classes combinatoires décomposables. En exploitant sa méthodologie constructive pour les produits de Hadamard, nous développons une stratégie de la génération efficace qui contourne les mécanismes de rejet grâce à une décomposition structurelle récursive.

## 2 Algorithme optimal pour le produit de Hadamard (version moins naïve)

**Problème** : étant données deux distributions de probabilité $(p_n)_{n \ge 0}$ et $(q_n)_{n \ge 0}$ telles que $\forall n \in \mathbb{N}: p_n \ge 0, q_n \ge 0, \sum_{n \in \mathbb{N}} p_n = \sum_{n \in \mathbb{N}} q_n = 1$, simuler une distribution de probabilité : $\propto p_n q_n$
L'approche naïve pourrait être implémentée comme suit :

**Algorithm 11** Générateur Naïf Hadamard((p_n), (q_n))

**Require:**

Distributions de probabilité $(p_n)_{n \ge 0}$, $(q_n)_{n \ge 0}$ avec $S = \sum_k p_k q_k > 0$

**Ensure:** Génération aléatoire $k$ selon $r_k \propto p_k q_k$

1: repeat

2: $x \sim p$

▷ Générer $x$ selon $p_n$

3: $y \sim q$

▷ Générer $y$ selon $q_n$

4: until $x = y$

▷ Rejeter si $x \neq y$

5: return $x$

▷ Retourner la génération acceptée ($x = y$)

**Théorème.** L'algorithme Générateur Naïf Hadamard :

1. Termine presque sûrement lorsque $S > 0$

2. Retourne des générations distribués selon $r_k = \frac{p_k q_k}{S}$

### Preuve 4 Partie 1 : Terminaison avec probabilité 1

Soit $S := \sum_{k=0}^{\infty} p_k q_k > 0$ la probabilité d'acceptation pour un essai. La probabilité d'acceptation en une itération est :

$$ \mathbb{P}(acceptation) = \mathbb{P}(X = Y) = \sum_{k=0}^{\infty} \mathbb{P}(X = k)\mathbb{P}(Y = k) = \sum_{k=0}^{\infty} p_k q_k = S > 0 $$

Soit $T$ le nombre d'essais jusqu'à la première acceptation. $T$ suit une loi géométrique :

$$ \mathbb{P}(T = t) = (1 - S)^{t-1}S, \quad t = 1, 2, 3, \dots $$

La probabilité que l'algorithme termine au plus tard à l'essai $m$ est :

$$ \mathbb{P}(T \le m) = 1 - (1 - S)^m $$

Lorsque $m \to \infty$ :

$$ \lim_{m \to \infty} \mathbb{P}(T \le m) = \lim_{m \to \infty} [1 - (1 - S)^m] = 1 $$

$car |1 - S| < 1$. Ainsi $\mathbb{P}(T < \infty) = 1$.
## Partie 2 : Correction de la distribution de sortie

Conditionnellement à l'événement que l'algorithme accepte à l'itération t, soit $X_t, Y_t$ les valeurs prises par x, y durant l'itération t. Pour tout $k \in \mathbb{N}$ :

$$ \mathbb{P}(\text{retourner } k) = \mathbb{P}(X_t = k | X_t = Y_t) $$

$$ = \frac{\mathbb{P}(X_t = k, Y_t = k)}{\mathbb{P}(X_t = Y_t)} $$

$$ = \frac{\mathbb{P}(X_t = k)\mathbb{P}(Y_t = k)}{\sum_{j=0}^{\infty} \mathbb{P}(X_t = j)\mathbb{P}(Y_t = j)} $$

$$ = \frac{p_k q_k}{\sum_{j=0}^{\infty} p_j q_j} $$

$$ = \frac{p_k q_k}{S} = r_k $$

La distribution de sortie correspond exactement à $r_k$ pour tout $k \in \mathbb{N}$.

**Analyse de complexité** : Le nombre moyen d'essais est $\mathbb{E}[T] = \frac{1}{S}$. Chaque essai nécessite deux générations indépendants de $p_n$ et $q_n$. La complexité dans le pire cas est non bornée lorsque $S \to 0^+$, mais finie pour des distributions fixes avec $S > 0$.

Cet algorithme ne diffère pas fondamentalement du premier algorithme proposé pour les distributions de Boltzmann ; tous deux souffrent de complexité et sont "très" probabilistes.

## Technique avancée basée sur Poisson (Sportiello) :

Nous proposons maintenant une version mise à jour de l'algorithme de Sportiello qui est contrôlée en complexité par deux paramètres de Poisson. Cet algorithme proposé suit exactement ce qui est attendu théoriquement : $\mathbb{P} \propto_{\lambda, \mu} p_n q_n$.
**Algorithm 12** Procédure à essai unique

**Require:**

$\lambda, \mu > 0$ (paramètres de Poisson)

Distributions de probabilité $p(n), q(n)$ sur $n \in \mathbb{N}$

**Ensure:** Entier $x$ généré aléatoirement ou NULL (rejet)

1. **function ESSAIUNIQUE($\lambda, \mu, p, q$)**

2. $k_x \leftarrow POISSON(\lambda)$

3. $k_y \leftarrow POISSON(\mu)$

4. $X \leftarrow SAMPLE(p, k_x)$

▷ $k_x$ tirages selon $p$

5. $Y \leftarrow SAMPLE(q, k_y)$

▷ $k_y$ tirages selon $q$

6. $A \leftarrow CONSTRUIREDICTIONNAIREFREQ(X)$

▷ $i \in X : \#\{x_i \in X | x_i = i\}$

7. $B \leftarrow CONSTRUIREDICTIONNAIREFREQ(Y)$

▷ $i \in Y : \#\{y_i \in Y | y_i = i\}$

8. $S \leftarrow CLÉS(A) \cup CLÉS(B)$

9. Candidats $\leftarrow$ []

10. **for** $i \in S$ **do**

11. $a \leftarrow A[i], b \leftarrow B[i]$

▷ 0 par défaut si absent

12. **if** $(a, b) \in \{(1, 1), (1, 2), (2, 1), (3, 1), (1, 3)\}$ **then**

13. Candidats.ajouter($i$)

14. **end if**

15. **end for**

16. **if** $|Candidats| \neq 1$ **then**

17. **return** NULL

18. **end if**

19. $x_0 \leftarrow Candidats[0]$

20. $S \leftarrow S \setminus \{x_0\}$

21. **for** $i \in S$ **do**

22. $a \leftarrow A[i], b \leftarrow B[i]$

23. **if** $(a, b) \notin \{(0, 0), (0, 1), (1, 0), (2, 0), (0, 2)\}$ **then**

24. **return** NULL

25. **end if**

26. **end for**

27. $a_0 \leftarrow A[x_0], b_0 \leftarrow B[x_0]$

28. **if** $(a_0, b_0) = (1, 1) \land \text{UNIFORME}(0, 1) \geq 1/3$ **then**

29. **return** NULL

30. **else if** $(a_0, b_0) \in \{(1, 2), (2, 1)\} \land \text{UNIFORME}(0, 1) \geq 2/3$ **then**

31. **return** NULL

32. **else**

33. **return** $x_0$

34. **end if**

35. **end function**

**Approche initiale (Sportiello)** : La première méthode proposée par Sportiello génère deux multi-ensembles de taille fixe :

$$1. \mathcal{A}_k = \{a_1, \dots, a_k\} \text{ où } a_i \stackrel{\text{i.i.d.}}{\sim} (p_n)_{n \ge 0}$$

$$2. \mathcal{B}_k = \{b_1, \dots, b_k\} \text{ où } b_i \stackrel{\text{i.i.d.}}{\sim} (q_n)_{n \ge 0}$$

L'algorithme identifie ensuite les éléments communs dans $\mathcal{A}_k \cap \mathcal{B}_k$. Si exactement un élément commun $c^*$ existe, il est retourné comme élément générer. Cependant, cette méthode présente une erreur dans la loi du résultat (la distribution est différente de la cible $r_n \propto p_n q_n$). Particulièrement lorsque $k \max_n(p_n q_n) \gg 1$.
La solution proposé par sportiello consiste à eviter d'utiliser les tailles fixes pour les liste générer par $(p_n)_{n \in \mathbb{N}}$, $(q_n)_{n \in \mathbb{N}}$

$$ \models \text{POISSONISATION : Générer des multi-ensembles de taille aléatoire via des distributions de Poisson :} $$

$$ \mathcal{A}_{\lambda} = \{a_1, \dots, a_{N_{\lambda}}\}, \qquad N_{\lambda} \sim \text{Poisson}(\lambda) $$

$$ \mathcal{B}_{\mu} = \{b_1, \dots, b_{N_{\mu}}\}, \qquad N_{\mu} \sim \text{Poisson}(\mu) $$

$$ \models \text{COMPTAGE DES VALEURS DE CHAQUE LISTES : Les comptes de chaque valeur } n \text{ suivent :} $$

$$ C_n^A \sim \text{Poisson}(\lambda p_n), \quad C_n^B \sim \text{Poisson}(\mu q_n) $$

$$ \models \text{SÉLECTION OPTIMALE : (COMPLEXITÉ, TEMPS D'ÉXECUTION) Les paramètres } \lambda, \mu \text{ sont ajustés pour maximiser la probabilité d'avoir des éléments communs uniques (c'est à dire diminuer la valeur de l'esperance moyenne de la terminaison de l'algo) tout en assurant que la distribution conjointe satisfait :} $$

$$ \mathbb{P}(\text{sélectionner } n) \propto \theta p_n q_n $$

où $\theta = \theta(\lambda, \mu)$ contrôle la concentration de la distribution et la complexité moyenne.

Cette technique réduit l'erreur de la distribution généré en exploitant les propriétés de découplage des distributions de Poisson avec d'autres distributions et permet une correction de biais précise par optimisation des paramètres.

**Preuve 5 Technique de Sportiello basée sur Poisson : soit $k \in \mathbb{N}$**

$$ \begin{aligned} \mathbb{P}(C_n^A = k) &= \sum_{m \ge k} \mathbb{P}(C_n^A = k \mid N_\lambda = m) \times \mathbb{P}(N_\lambda = m) \\ &= \sum_{m \ge k} \exp(-\lambda) \frac{\lambda^m}{m!} \binom{m}{k} p_n^k (1-p_n)^{m-k} \\ &= \exp(-\lambda) \frac{p_n^k \lambda^k}{k!} \sum_{m \ge k} \frac{\lambda^{m-k} (1-p_n)^{m-k}}{(m-k)!} \\ &= \exp(-\lambda p_n) \frac{(\lambda p_n)^k}{k!} \end{aligned} $$

ce qui prouve la technique. Q.E.D.

Soient $\lambda, \mu \in \mathbb{R}^2$ Définissons le raccourci : $\phi_x(a, b) = \pi_{\lambda p_x}(a)\pi_{\mu q_x}(b)$ où $\pi_{\theta}(n) = \mathbb{P}(X = n)$ avec $X \sim \mathbb{P}(\theta)$ (loi de Poisson de paramètre $\theta$)

La distribution de probabilité proposée par Sportiello est donnée par :

$$ \forall x \in \mathbb{N} : p(x) = \left( \frac{1}{3}\phi_x(1,1) + \frac{2}{3}(\phi_x(2,1) + \phi_x(1,2) + \phi_x(3,1) + \phi_x(1,3)) \right) \times \prod_{y \ne x} (\phi_y(0,0) + \phi_y(0,1) + \phi_y(1,0) + \phi_y(0,2) + \phi_y(2,0)) $$

Nous développons le calcul de $p(x)$.
$$
\begin{align*}
p(x) &= \left[ \frac{1}{3} \exp(-\lambda p_x - \mu q_x) \lambda p_x \mu q_x \right. \\
&\quad \left. + \frac{2}{3} \exp(-\lambda p_x - \mu q_x) \left( \frac{\lambda^2 p_x^2 \mu q_x}{2} + \frac{\lambda p_x \mu^2 q_x^2}{2} \right) \right. \\
&\quad \left. + \exp(-\lambda p_x - \mu q_x) \left( \frac{\lambda^3 p_x^3 \mu q_x}{6} + \frac{\lambda p_x \mu^3 q_x^3}{6} \right) \right] \\
&\quad \times \prod_{y \neq x} \left[ \exp(-(\lambda p_y + \mu q_y)) \left( 1 + (\lambda p_y + \mu q_y) + \frac{\lambda^2 p_y^2 + \mu^2 q_y^2}{2} \right) \right] \\
&= p_x q_x \lambda \mu \exp(-(\lambda p_x + \mu q_x)) \left[ \frac{1}{3} + \frac{2}{3} \cdot \frac{\lambda p_x + \mu q_x}{2} + \frac{\lambda^2 p_x^2 + \mu^2 q_x^2}{6} \right] \\
&\quad \times \prod_{y \neq x} \left[ \exp(-(\lambda p_y + \mu q_y)) \left( 1 + \lambda p_y + \mu q_y + \frac{\lambda^2 p_y^2 + \mu^2 q_y^2}{2} \right) \right] \\
&= p_x q_x \frac{\lambda \mu}{3} \exp(-(\lambda p_x + \mu q_x)) \left( 1 + \lambda p_x + \mu q_x + \frac{\lambda^2 p_x^2 + \mu^2 q_x^2}{2} \right) \\
&\quad \times \prod_{y \neq x} \left[ \exp(-(\lambda p_y + \mu q_y)) \left( 1 + \lambda p_y + \mu q_y + \frac{\lambda^2 p_y^2 + \mu^2 q_y^2}{2} \right) \right] \\
&= p_x q_x \frac{\lambda \mu}{3} \exp(-(\lambda + \mu)) \prod_{n \in \mathbb{N}} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right)
\end{align*}
$$

Propriétés de l’algorithme de Sportiello

1. Distribution exacte du produit de Hadamard : D’après l’expression finale :

$$
p(x) = \frac{\lambda\mu}{3} p_x q_x \exp(-\lambda - \mu) \prod_{n \in \mathbb{N}} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right)
$$

on observe que les termes $\frac{\lambda\mu}{3}\exp(-\lambda - \mu)\prod_{n\in\mathbb{N}}\left(1+\lambda p_n+\mu q_n+\frac{\lambda^2 p_n^2+\mu^2 q_n^2}{2}\right)$ sont in-
dépendants de $x$. Ainsi :

$p(x) \propto p_x q_x$

La distribution de sortie est exactement le produit de Hadamard $r_x = \frac{p_x q_x}{S}$ où $S = \sum_x p_x q_x$.

2. **Probabilité de succès** : La probabilité totale de succès est :

$$
\begin{align*}
P_{\text{succès}} &= \sum_x p(x) \\
&= \frac{\lambda\mu}{3} \exp(-\lambda - \mu) \left[ \prod_{n \in \mathbb{N}} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right) \right] \sum_x p_x q_x \\
&= \frac{\lambda\mu}{3} \exp(-\lambda - \mu) S \prod_{n \in \mathbb{N}} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right)
\end{align*}
$$

3. Complexité attendue : Le nombre moyen d'essais jusqu'au succès est :

$$
\mathbb{E}[\text{essais}] = \frac{1}{P_{\text{succès}}}
$$
**Preuve 6** Soit $X_t$ la variable aléatoire représentant la valeur de retour de l'algorithme (sans rejet).

Ainsi : $X_t \sim \mathcal{G}(P_{succ\text{è}s})$ (loi géométrique)

$$ \therefore \mathbb{E}[X_t] = \frac{1}{P_{succ\text{è}s}} = \frac{3 \exp(\lambda + \mu)}{\lambda \mu S \times \theta(\lambda, \mu)} $$

où :

$$ \theta(\lambda, \mu) = \prod_{n \in \mathbb{N}} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right) $$

**Algorithm 13** Générateur de Hadamard par rejet de Sportiello

**Require:**

$\lambda, \mu > 0$ (paramètres de Poisson)

Distributions de probabilité $p(n), q(n)$ sur $n \in \mathbb{N}$

**Ensure:** Entier $x$ générer aléatoirement selon $r_x \propto p_x q_x$

1: **procedure** GÉNÉRATEURPRINCIPAL($\lambda, \mu, p, q$)

2: $x \leftarrow \text{NULL}$

3: **repeat**

4: $x \leftarrow \text{ESSAIUNIQUE}(\lambda, \mu, p, q)$

5: **until** $x \neq \text{NULL}$

6: **return** $x$

7: **end procedure**

1: **function** ESSAIUNIQUE($\lambda, \mu, p, q$)

2:

▷ Même implémentation que l'Algorithmme 12

3: **return** $\text{NULL}$ ou génération aléatoire valide $x$

4: **end function**

## 2.1 Simulation des algorithmes

Dans cette section, nous nous concentrons sur la simulation de l'algorithme proposé en utilisant PYTHON. Nous proposerons des modèles probabilistes (distributions) $p_n, q_n$ et le but est de calculer la distribution théorique de $(\frac{p_n q_n}{\sum_{k \in \mathbb{N}} p_k q_k})_n$ et de la comparer avec l'algorithme de Sportiello.

Pour cela, nous pouvons emprunter la voie la plus simple pour le calcul de la distribution théorique, en commençant par donner un résultat élémentaire :

**Résultat (élémentaire) :** soit $X, G, Y$ deux variable aléatoires, sachant que : $X \rightsquigarrow \mathbb{P}(1), G \rightsquigarrow \mathcal{G}(p), Y = G - 1$.

alors : $\forall n \in \mathbb{N}: \mathbb{P}(Y = n) = (1 - p)^n p$.

Soit $p_n = \mathbb{P}(Y = n) = (1 - p)^n p$ (géométrique décaler), $q_n = \exp(-\lambda) \frac{\lambda^n}{n!}$ (Poisson).

$$ p_n q_n = \exp(-\lambda) p \frac{((1 - p)\lambda)^n}{n!} $$

$$ \sum_{n \in \mathbb{N}} p_n q_n = \exp(-\lambda) p \exp((1 - p)\lambda) $$
Ainsi le produit de Hadamard de $p_n$ et $q_n$ est exactement $\mathcal{P}((1-p)\lambda)$ (Poisson de paramètre $(1-p)\lambda$).

$$ \Rightarrow \frac{p_n q_n}{\sum_{n \in \mathbb{N}} p_n q_n} = \exp((1-p)\lambda) \frac{((1-p)\lambda)^n}{n!} = \mathcal{P}((1-p)\lambda) \quad (3) $$

On simule maintenant le produit de Hadamard des lois de X et Y des paramètres respective 10, 0.9 afin de le comparer avec un loi de poisson de paramètres 1 donc la distribution de produit de Hadamard correspond $P_n = \frac{1}{en!}$.

<figure><img src="image_4.png" /><figcaption>Figure 2: Simulation du produit de Hadamard</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3: Simulation de $\mathcal{P}(1)$.</figcaption></figure>
## 2.2 Produit de Hadamard sous loi de Boltzmann

Dans cette partie, nous nous intéressons à la génération de paires d'objets combinatoires $(a, b) \in \mathcal{A} \times \mathcal{B}$ de même taille sous loi de Boltzmann. Pour cela, nous appliquons l'algorithme 9 combiné avec la méthodologie de Sportiello (Algorithme 12). Comme démontré dans la section 1.6, nous pouvons simuler efficacement la génération aléatoire d'objets combinatoires définis récursivement ou par grammaires.

### 2.2.1 Générateurs de Boltzmann spécifiques

**Algorithm 14** $\Gamma\mathcal{B}(x)$: Générateur de Boltzmann pour les arbres binaires
___
**Require:** $x \in [0, \rho_{\mathcal{B}}) = [0, 1/4)$
**Ensure:** Arbre binaire $T$ selon $\mathbb{P}_x$
___
1: $p_{\text{feuille}} \leftarrow \frac{1}{B(x)}$ \quad ▷ Probabilité de l'arbre vide
2: $p_{\text{noeud}} \leftarrow \frac{x \cdot B(x)^2}{B(x)} = xB(x)$ \quad ▷ Probabilité d'un nœud interne
3: Générer $U \sim \mathcal{U}([0, 1])$
4: **if** $U < p_{\text{feuille}}$ **then**
5: **return** $\epsilon$ \quad ▷ Arbre vide
6: **else**
7: $T_{\text{gauche}} \leftarrow \Gamma\mathcal{B}(x)$
8: $T_{\text{droite}} \leftarrow \Gamma\mathcal{B}(x)$
9: **return** $(\bullet, T_{\text{gauche}}, T_{\text{droite}})$
10: **end if**
___

**Algorithm 15** $\Gamma\mathcal{F}(x)$: Générateur de Boltzmann pour les mots de Fibonacci
___
**Require:** $x \in [0, \rho_{\mathcal{F}}) = [0, \frac{\sqrt{5}-1}{2})$
**Ensure:** Mot $m \in \mathcal{F}$ selon $\mathbb{P}_x$
___
1: $p_{\epsilon} \leftarrow \frac{1}{F(x)}$ \quad ▷ Prob. mot vide
2: $p_a \leftarrow \frac{x}{F(x)}$ \quad ▷ Prob. mot "a"
3: $p_b \leftarrow \frac{x \cdot F(x)}{F(x)} = x$ \quad ▷ Prob. commencer par 'b'
4: $p_{ab} \leftarrow \frac{x^2 F(x)}{F(x)} = x^2$ \quad ▷ Prob. commencer par 'ab'
5: Générer $U \sim \mathcal{U}([0, 1])$
6: **if** $U < p_{\epsilon}$ **then**
7: **return** $\epsilon$
8: **else if** $U < p_{\epsilon} + p_a$ **then**
9: **return** "a"
10: **else if** $U < p_{\epsilon} + p_a + p_b$ **then**
11: $m' \leftarrow \Gamma\mathcal{F}(x)$
12: **return** "b" + $m'$
13: **else**
14: $m' \leftarrow \Gamma\mathcal{F}(x)$
15: **return** "ab" + $m'$
16: **end if**
___
**Algorithm 16** ΓW(x): Générateur de Boltzmann pour marches aléatoires Z²

**Require:** $x \in [0, \rho_W) = [0, 1/4)$

**Ensure:** Marche w (séquence de pas) selon $\mathbb{P}_x$

1: $p_{\text{stop}} \leftarrow 1 - 4x$ ▷ Probabilité d'arrêt

2: Générer $U \sim U([0, 1])$

3: **if** $U < p_{\text{stop}}$ **then**
4:     **return** $\epsilon$ ▷ Marche vide

5: **else**
6:     Choisir $d \in \{\uparrow, \downarrow, \leftarrow, \rightarrow\}$ uniformément
7:     $w' \leftarrow \Gamma W(x)$
8:     **return** $d + w'$ ▷ Concaténation

9: **end if**

### 2.2.2 Étude asymptotique des espérances

L'espérance de la taille sous loi de Boltzmann est donnée par :

$$ \mathbb{E}_x[N] = \frac{xC'(x)}{C(x)} $$

Pour les trois classes :

* **Arbres binaires** :

$$ \mathbb{E}_x[N_{\mathcal{B}}] = \frac{1}{1 - 4x} - 1, \quad x \in [0, 1/4) $$

* **Mots de Fibonacci** :

$$ \mathbb{E}_x[N_{\mathcal{F}}] = \frac{x(2 + 2x + x^2)}{(1 - x - x^2)(1 + x)} $$

* **Marches aléatoires** :

$$ \mathbb{E}_x[N_W] = \frac{4x}{1 - 4x} $$

Pour égaliser les espérances entre arbres ($\mathcal{B}$) et marches ($\mathcal{W}$) :

$$ \frac{1}{1 - 4x} - 1 = \frac{4x}{1 - 4x} \implies x = \frac{1}{8} $$

À cette valeur, $\mathbb{E}_{1/8}[N_{\mathcal{B}}] = \mathbb{E}_{1/8}[N_{\mathcal{W}}] = 1$.

### 2.2.3 Optimisation par poissonisation (Sportiello)

Pour générer des paires $(a, b)$ avec $|a| = |b|$, nous utilisons la paramétrisation de Poisson :

$$ \lambda^*, \mu^* = \arg \max_{\lambda, \mu} P_{\text{succès}}(\lambda, \mu) $$

où la probabilité de succès est donnée par :

$$ P_{\text{succès}} = \frac{\lambda \mu}{3} e^{-\lambda - \mu} S \prod_{n=0}^{\infty} \left( 1 + \lambda p_n + \mu q_n + \frac{\lambda^2 p_n^2 + \mu^2 q_n^2}{2} \right) $$

avec $S = \sum_n p_n q_n$.
<figure><img src="image_6.png" /><figcaption>Figure 4: Simulation du produit de Hadamard sous loi de Boltzmann des objets (arbre, marche aléatoire sur $\mathbb{Z}^2$)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: Simulation du produit de Hadamard sous loi de Boltzmann des objets (arbre, mot de Fibonacci $(b | ab)^(a | \epsilon)$)</figcaption></figure>
Conclusion

Ce stage au Laboratoire Bordelais de Recherche en Informatique (LaBRI) restera une expéri-
ence scientifique et humaine marquante. Je tiens à réitérer ma profonde gratitude envers
Monsieur Philippe Duchon pour sa bienveillance exceptionnelle. Lors de notre première
rencontre, il a transformé une simple demande de stage en une véritable initiation à la
combinatoire analytique : pendant deux heures dans son bureau, il a patiemment défini
les concepts fondateurs (séries génératrices, lois de Boltzmann), évoqué avec passion ses
travaux fondateurs avec Philippe Flajolet - jusqu'à l'anecdote éclairante du nom Boltzmann
- et exposé le défi ouvert du produit de Hadamard avec cette phrase décisive :

« *C'est ça, vraiment, ce que j'aimerais que tu explores.* »

Bien qu’initialement orienté vers l’algèbre, j’ai découvert une fascination pour les probabil-
ités combinatoires grâce à son mentorat. Travailler sur l’algorithme de Sportiello, analyser
les distributions de taille sous poissonisation, et implémenter des générateurs pour les ar-
bres binaires ou les mots de Fibonacci ont consolidé ma maîtrise des objets discrets. Cette
immersion m’a révélé l’élégance des méthodes analytiques en informatique théorique.

Plus qu’un stage, ce fut une rencontre fondatrice : celle d’un chercheur inspirant qui voit
dans un étudiant inconnu un collaborateur potentiel. Merci, Monsieur Duchon, pour cette
confiance et pour l’exigence joyeuse qui ont fait de ces semaines au LaBRI un chapitre
indispensable de mon parcours.
# Key Research on Hadamard Product Sampling

(a) Improved Boltzmann Sampling [Spo16]

* Contribution: First polynomial-time algorithm for exact sampling from $C = A \odot B$

* Technique: Poissonized rejection with pattern matching

* Complexity: $O(n^{2\alpha}) \rightarrow O(n^{\alpha} \log n)$

(b) Exact Generation with Approximate Oracles [BRL14]

* Contribution: Error-corrected sampling using approximate size oracles

* Technique: Adaptive parameter tuning via Newton iteration

* Accuracy: $\mathbb{E}[\text{error}] < \varepsilon$ in $O(\log \frac{1}{\varepsilon})$ iterations

(c) Unlabeled Boltzmann Framework [Piv08]

* Contribution: Complete theory for unlabeled combinatorial classes

* Key Lemma: $\mathbb{P}(|\gamma| = n) = \frac{[z^n]C(z)}{C(\rho)}\rho^n$

* Extension: Multivariate Boltzmann for tuples

n

# Algorithmic Breakthrough: Sportiello's Sampler

For $C = A \odot B$ with generating functions $A(z), B(z)$:

SAMPLER<sub>C</sub>(z):

1. $\lambda \leftarrow \text{root of } \lambda A'(\lambda) B'(\lambda) = n$

2. repeat

3. $\gamma_A \sim \Gamma A(\lambda), \gamma_B \sim \Gamma B(\lambda)$

4. until $|\gamma_A| + |\gamma_B| = n$

5. return $(\gamma_A, \gamma_B)$

Success probability: $\mathbb{P} = \frac{[z^n]A(z)B(z)}{A(\lambda)B(\lambda)} \lambda^n$
Specialized References on Boltzmann Sampling

[BRL14] Olivier Bodini, Nicolas Rolin, and Jérémie Lumbroso. "Génération aléatoire ex-
acte de Boltzmann avec un oracle approximatif". In: *Journées Combinatoires de Bordeaux*. 2014.

[Duc+04] P. Duchon et al. "Boltzmann Samplers for the Random Generation of Combinatorial Structures". In: *Combinatorics, Probability and Computing* (2004).

[Piv08] Carine Pivoteau. "Génération aléatoire sous modèle de Boltzmann: le cas non-étiqueté". Supervised by Michèle Soria, with P. Flajolet and É. Fusy. PhD thesis. Université Pierre et Marie Curie, 2008.

[PSS12] C. Pivoteau, B. Salvy, and M. Soria. "Algorithms for Combinatorial Structures: Well-Founded Systems and Newton Iterations". In: *Journal of Discrete Algorithms* (2012).

[Spo16] Andrea Sportiello. "Improved Boltzmann sampling for the Hadamard product of distributions". In: *Proceedings of the 10th International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom 2016)*. Ed. by Jean-Marc Fédou and Luca Ferrari. La Marana, France, June 2016. URL: https://hal.science/hal-03214414.