Upload
others
View
3
Download
0
Embed Size (px)
Citation preview
Combinatoire analytique et modèles d’urnes
Basile Morcrette,encadré par Philippe Flajolet
Projet Algorithms, INRIA Rocquencourt.
6 septembre 2010
1/22
Des situations diverses et variées
I épidémies
I génétique des populations
I physique statistique : particules de gaz dans uncompartiment
I structures informatiques : arbres, graphes
2/22
Plan
1. Modèles d’urnes2. Urnes et branches d’arbres aléatoires3. Urnes de croissance préférentielle4. Urnes des k-arbres
3/22
Le modèle d’urne
I une urne et des boules de couleurs différentes
4/22
Le modèle d’urne
I une urne et des boules de couleurs différentes
4/22
Le modèle d’urne
I une urne et des boules de couleurs différentesI des règles fixées pour l’évolution de l’urne
(1 00 1
)4/22
Urne de Pólya (α βγ δ
)α, δ ∈ Z, β, γ ∈ Z>0 .
Urne équilibrée : α + β = γ + δ (nombre total de boules déterministe).
Configuration initiale fixée (a0, b0) : a0 boules • (comptées par x)
b0 boules ◦ (comptées par y)
DéfinitionHistoire de longueur n : une suite de n évolutions (n tirages).Hn,a,b : nombre d’histoires de longueur n, débutant en (a0, b0), et ter-minant en (a, b).Fonction génératrice des Hn,a,b :
H(x , y , z) =∑n,a,b
Hn,a,b xayb zn
n!.
5/22
Urne de Pólya (α βγ δ
)α, δ ∈ Z, β, γ ∈ Z>0 .
Urne équilibrée : α + β = γ + δ (nombre total de boules déterministe).
Configuration initiale fixée (a0, b0) : a0 boules • (comptées par x)
b0 boules ◦ (comptées par y)
DéfinitionHistoire de longueur n : une suite de n évolutions (n tirages).Hn,a,b : nombre d’histoires de longueur n, débutant en (a0, b0), et ter-minant en (a, b).Fonction génératrice des Hn,a,b :
H(x , y , z) =∑n,a,b
Hn,a,b xayb zn
n!.
5/22
Urne de Pólya (α βγ δ
)α, δ ∈ Z, β, γ ∈ Z>0 .
Urne équilibrée : α + β = γ + δ (nombre total de boules déterministe).
Configuration initiale fixée (a0, b0) : a0 boules • (comptées par x)
b0 boules ◦ (comptées par y)
DéfinitionHistoire de longueur n : une suite de n évolutions (n tirages).Hn,a,b : nombre d’histoires de longueur n, débutant en (a0, b0), et ter-minant en (a, b).Fonction génératrice des Hn,a,b :
H(x , y , z) =∑n,a,b
Hn,a,b xayb zn
n!.
5/22
Urne de Pólya (α βγ δ
)α, δ ∈ Z, β, γ ∈ Z>0 .
Urne équilibrée : α + β = γ + δ (nombre total de boules déterministe).
Configuration initiale fixée (a0, b0) : a0 boules • (comptées par x)
b0 boules ◦ (comptées par y)
DéfinitionHistoire de longueur n : une suite de n évolutions (n tirages).Hn,a,b : nombre d’histoires de longueur n, débutant en (a0, b0), et ter-minant en (a, b).Fonction génératrice des Hn,a,b :
H(x , y , z) =∑n,a,b
Hn,a,b xayb zn
n!.
5/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
+ (2xy3 + 2x2y2 + 2x3y) z3
6
6/22
Compter les histoiresPrenons l’urne
(1 00 1
)et (a0, b0) = (1, 1).
H(x , y , z) =
xyz
+ (xy2 + x2y) z2
2
+ (2xy3 + 2x2y2 + 2x3y) z3
6
+ . . .
6/22
Des comportements très divers
Problème Comprendre la composition de l’urne après n étapes, lorsque ntend vers ∞.
( 1 00 1 )
(0 1 00 −1 20 0 1
)
( 3 12 2 ) ( 2 1
1 2 )
7/22
Des comportements très divers
Problème Comprendre la composition de l’urne après n étapes, lorsque ntend vers ∞.
( 1 00 1 )
(0 1 00 −1 20 0 1
)
( 3 12 2 ) ( 2 1
1 2 )7/22
Urnes équilibrées et système différentiel
Approche analytique Théorème [Flajolet–Dumas–Puyhaubert 2005]
Urne(α βγ δ
)et{
(a0, b0)α + β = γ + δ
=⇒H = X a0 Y b0
où{
X = Xα+1 Y β
Y = X γ Y δ+1
Travaux réalisés :I étude d’urnes en grande dimensionI étude d’urnes à coefficients positifs (= additives)
8/22
Urnes équilibrées et système différentiel
Approche analytique Théorème [Flajolet–Dumas–Puyhaubert 2005]
Urne(α βγ δ
)et{
(a0, b0)α + β = γ + δ
=⇒H = X a0 Y b0
où{
X = Xα+1 Y β
Y = X γ Y δ+1
Travaux réalisés :I étude d’urnes en grande dimensionI étude d’urnes à coefficients positifs (= additives)
8/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)
I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)
I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformément
I la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
2. Urnes et branches d’arbre aléatoire
I Motivation : quantifier la proportion de tautologies parmi lesformules logiques ayant comme seul connecteur l’implication.
I Modèle probabiliste : croissance uniforme aux feuilles (modèle ABR)I tirer une feuille au hasard uniformémentI la remplacer par un noeud binaire et deux feuilles
9/22
Modélisation par une urne 3× 3
3 couleurs,avec les règles :
∇ → •∇• → ××× → ××
Urnecorrespondante :0 1 0
0 −1 20 0 1
Fonction génératrice des histoires
H(y , z) = exp(ln(
11− z
)+ (y − 1)z
)z compte la longueur de l’histoire,y compte le nombre de boules •.
10/22
Modélisation par une urne 3× 3
3 couleurs,avec les règles :
∇ → •∇• → ××× → ××
Urnecorrespondante :0 1 0
0 −1 20 0 1
Fonction génératrice des histoires
H(y , z) = exp(ln(
11− z
)+ (y − 1)z
)z compte la longueur de l’histoire,y compte le nombre de boules •.
10/22
Modélisation par une urne 3× 3
3 couleurs,avec les règles :
∇ → •∇• → ××× → ××
Urnecorrespondante :0 1 0
0 −1 20 0 1
Fonction génératrice des histoires
H(y , z) = exp(ln(
11− z
)+ (y − 1)z
)z compte la longueur de l’histoire,y compte le nombre de boules •.
10/22
Loi de Poisson dans les sous-arbresSoit Uk,n le nombre de sous-arbres gauches de taille k directementaccrochés à la branche droite d’un arbre aléatoire de taille n.
Théorème
I U1,n converge en loi, U1,n −→n→∞
U1,
I U1 ∼ Poisson (1), avec vitesse de convergence en O(
2n
n!
).
Généralisation Utilisation d’une urne (k + 2)× (k + 2)
Théorème
I Uk,n converge en loi, Uk,n −→n→∞
Uk ,
I Uk ∼ Poisson( 1
k
), avec vitesse de convergence en O
((2k)n
n!
).
11/22
Loi de Poisson dans les sous-arbresSoit Uk,n le nombre de sous-arbres gauches de taille k directementaccrochés à la branche droite d’un arbre aléatoire de taille n.
Théorème
I U1,n converge en loi, U1,n −→n→∞
U1,
I U1 ∼ Poisson (1), avec vitesse de convergence en O(
2n
n!
).
Généralisation Utilisation d’une urne (k + 2)× (k + 2)
Théorème
I Uk,n converge en loi, Uk,n −→n→∞
Uk ,
I Uk ∼ Poisson( 1
k
), avec vitesse de convergence en O
((2k)n
n!
).
11/22
3. Urnes de croissance préférentielle
Motivation : Caractériser les urnes 2× 2 additives (coefficients positifs).Approche : Avoir une classe d’urnes avec des fonctions génératrices“exploitables”.
Théorème
La classe d’urnes équilibrées(2α βα α + β
), avec α > 0, β > 0, a une
fonction génératrice bivariée algébrique.
La fonction génératrice des histoires H(x , z) est racine du polynôme en Y
(z − a− b(x)) Y 2α+β + b(x) Y α + a
12/22
3. Urnes de croissance préférentielle
Motivation : Caractériser les urnes 2× 2 additives (coefficients positifs).Approche : Avoir une classe d’urnes avec des fonctions génératrices“exploitables”.
Théorème
La classe d’urnes équilibrées(2α βα α + β
), avec α > 0, β > 0, a une
fonction génératrice bivariée algébrique.
La fonction génératrice des histoires H(x , z) est racine du polynôme en Y
(z − a− b(x)) Y 2α+β + b(x) Y α + a
12/22
Simulations – Moyenne – Variance
PropositionSoit Xn la variable aléatoire comptant le nombre de boules de couleur xdans l’urne au temps n. Alors
E(Xn) =α(2α + β)
α + βn +
α
α + β
Γ( 12α+β )
Γ( α+12α+β )
nα
2α+β +α
α + β+O
(n
α2α+β−1
),
V(Xn) =α3(2α + β)
(α + β)2 n + O(n
α+β2α+β
)où Γ(x) :=
∫ ∞0
tx−1e−tdt .
13/22
Simulations – Moyenne – Variance
PropositionSoit Xn la variable aléatoire comptant le nombre de boules de couleur xdans l’urne au temps n. Alors
E(Xn) =α(2α + β)
α + βn +
α
α + β
Γ( 12α+β )
Γ( α+12α+β )
nα
2α+β +α
α + β+O
(n
α2α+β−1
),
V(Xn) =α3(2α + β)
(α + β)2 n + O(n
α+β2α+β
)où Γ(x) :=
∫ ∞0
tx−1e−tdt .
13/22
Exploitation analytique
1. L’équation de la fonction génératrice présente deux singularités,lorsque x varie autour de 1.
2. Il y a confluence lorsque x tend vers 1. Cela donne desdéveloppements asymptotiques différents selon le voisinage que l’onconsidère.
Démarche :I utilisation d’un contour normalisé (grâce à la moyenne et la
variance), autour des singularités. Addition des deux contributions.I changement de variable à la Lagrange, et méthode de col.
But : obtenir une convergence vers une loi normale.
14/22
Exploitation analytique
1. L’équation de la fonction génératrice présente deux singularités,lorsque x varie autour de 1.
2. Il y a confluence lorsque x tend vers 1. Cela donne desdéveloppements asymptotiques différents selon le voisinage que l’onconsidère.
Démarche :I utilisation d’un contour normalisé (grâce à la moyenne et la
variance), autour des singularités. Addition des deux contributions.I changement de variable à la Lagrange, et méthode de col.
But : obtenir une convergence vers une loi normale.
14/22
Exploitation analytique
1. L’équation de la fonction génératrice présente deux singularités,lorsque x varie autour de 1.
2. Il y a confluence lorsque x tend vers 1. Cela donne desdéveloppements asymptotiques différents selon le voisinage que l’onconsidère.
Démarche :I utilisation d’un contour normalisé (grâce à la moyenne et la
variance), autour des singularités. Addition des deux contributions.I changement de variable à la Lagrange, et méthode de col.
But : obtenir une convergence vers une loi normale.
14/22
4. Urnes des k-arbres
Motivation : modélisation de réseaux sociaux [Panholzer–Seitz 2010]
DéfinitionUn k-arbre T est
I soit une k-cliqueI soit il existe un sommet f ayant une k-clique comme voisin et T\f
est un k-arbreOrdonné : fils distinguables.Croissant : sommets numérotés dans l’ordre d’apparition.
15/22
4. Urnes des k-arbres
Motivation : modélisation de réseaux sociaux [Panholzer–Seitz 2010]
DéfinitionUn k-arbre T est
I soit une k-cliqueI soit il existe un sommet f ayant une k-clique comme voisin et T\f
est un k-arbreOrdonné : fils distinguables.Croissant : sommets numérotés dans l’ordre d’apparition.
1-arbres ordonnés croissants (dits PORT)
15/22
4. Urnes des k-arbres
Motivation : modélisation de réseaux sociaux [Panholzer–Seitz 2010]
DéfinitionUn k-arbre T est
I soit une k-cliqueI soit il existe un sommet f ayant une k-clique comme voisin et T\f
est un k-arbreOrdonné : fils distinguables.Croissant : sommets numérotés dans l’ordre d’apparition.
2-arbres ordonnés croissants
15/22
Modélisation
Pour les 1-arbres(0 21 1
)
Pour les k-arbres(k − 1 2
k 1
)
ddz H(x , z)
H(x , z)k (H(x , z)− x + 1)2 = 1
16/22
Modélisation
Pour les 1-arbres(0 21 1
)
Pour les k-arbres(k − 1 2
k 1
)
ddz H(x , z)
H(x , z)k (H(x , z)− x + 1)2 = 1
16/22
Modélisation
Pour les 1-arbres(0 21 1
)
Pour les k-arbres(k − 1 2
k 1
)
ddz H(x , z)
H(x , z)k (H(x , z)− x + 1)2 = 1
16/22
Modélisation
Pour les 1-arbres(0 21 1
)
Pour les k-arbres(k − 1 2
k 1
)
ddz H(x , z)
H(x , z)k (H(x , z)− x + 1)2 = 1
16/22
Loi normale limiteSoit Xn la variable aléatoire comptant le nombre de boules � dans l’urneU1 après n étapes.Cas k = 1 : nombre de feuilles dans un PORT de taille n.
Théorème
I Xn a une moyenne µn et une variance σ2n
I Xn−(2/3)n√n/3 converge en loi vers N (0, 1),
avec vitesse de convergence O(
1√n
).
µn = E(Xn) =23
(n+1/2)+O(1n
), σ2
n = V(Xn) =19
(n+1/2)+O(1n
),
P
{Xn − 2
3n√ n9
6 t
}= Φ(t) + O
(1√n
), où Φ(t) =
1√2π
∫ t
−∞e−
v22 dv .
17/22
Loi normale limite –Convergence de la fonction de répartition
P
{Xn − 2
3n√n9
6 t
}−→n→∞
18/22
Loi Locale Limite
ThéorèmeNotons pn,k = P {Xn = k}. La distribution des Xn satisfait une loi locale
limite de type gaussienne avec vitesse de convergence O(
1√n
), i.e.
supt∈R
∣∣∣∣√n3
pn,b2n/3+t√
n/3c −1√2π
e−t2/2∣∣∣∣ 6 1√
n.
19/22
Loi Locale Limite –Convergence vers la fonction de densité
√n3
P{
Xn =
⌊2n3
+ t√
n3
⌋}−→n→∞
20/22
Grandes déviationsI borne exponentiellement petite sur la grande déviation par rapport à
la valeur moyenne : quantification sur les événements rares
Théorème
I si 0.42 < t < 2/3, P(Xn 6 tn) ≈ e−nW (t) (queue gauche)I si 2/3 < t < 0.73, P(Xn > tn) ≈ e−nW (t) (queue droite)
21/22
Conclusion et Perspectives
Divers problèmes modélisés par les urnes et traités par la combinatoireanalytique :
I Urnes en grande dimensionI premiers pas avec la combinatoire analytique
I variété de problèmes modélisés
I Urnes bicolores additivesI classe algébrique à deux paramètres : générale
I urne des k-arbres : premiers résultats sur les urnes additives avecLoi centrale limite, Loi locale limite et principe de grandes déviations,avec vitesse de convergence.
22/22