these

Informations

• Publié par: Thewyer
• Nombre de lectures: 61
• Langue: English

Extrait

THESE
presentee devant
L’UNIVERSITE DE VERSAILLES-SAINT-QUENTIN
pour obtenir le titre de :
DOCTEUR DE L’UNIVERSITE DE
Mention : Mathematiques et Applications
PAR
THIERRY KLEIN
TITRE DE LA THESE :
INEGALITES DE CONCENTRATION,
MARTINGALES ET
ARBRES ALEATOIRES
Rapporteurs
M. Svante JANSON
M. LiMing WU
Soutenue publiquement le 19 decembre 2003 devant le jury compose de :
M. Jean BRETAGNOLLE Examinateur
M. Oleksiy KHORUNZHIY
M. Michel LEDOUX
M. Emmanuel RIO Directeur de these
M. LiMing WU RapporteurResume
Inegalites de concentration, martingales et
arbres aleatoires
Cette these comporte trois parties. Dans les deux premieres parties, nous nous interessons a
deux aspects de la concentration de la mesure. Dans la derniere partie, nous nous int
a l’analyse asymptotique des arbres binaires de recherche dans le modele dit des permutations
aleatoires.
Dans la premiere partie, nous donnons des constantes optimales dans les inegalites de
concentration de type Talagrand pour le maxima de processus empiriques associes a des
variables aleatoires independantes. Notre methode est basee sur la methode dite de Herbst
et sur des techniques de calculs entropiques.
Dans la seconde partie, nous prouvons des inegalites de concentration convexe pour des
processus de comptage a temps discret et a temps continu. Nous appliquons ensuite ces
resultats pour prouver que le sup de variables aleatoires independantes binomiales (resp. de
Poisson) veri e une inegalite de concentration convexe.
Dans la troisieme partie, nous etudions le comportement asymptotique des arbres binaires
de recherche. Nous utilisons essentiellement deux methodes : le plongement et le tiltage. Nous
obtenons alors de nouveaux resultats sur l’arbre binaire de recherche ainsi que des nouvelles
preuves de resultats connus.
Abstract
Concentration inequlalities, martingales and
random trees
This Phd thesis is divided into three parts. The two rst parts deal with two di eren t aspects
of the concentration of the measure. In the third part, we are interested in the asymptotic
analysis of the binary search tree under the random permutation model
In the rst part, we give optimal constants in Talagrand’s concentration inequalities
for maxima of empirical processes associated to independent and eventually non identically
distributed random variables. Our method is based on the so-called Herbst method.
In the second part, we prove convex concentration inequalities for discrete and continuous
time counting processes. Then we apply these inequalities to prove that the supremum of
independent binomial random variables and the supremun of independent Poisson random
variables satisfy convex concentration inequalities.
In the third part, we are interested in the asymptotic analysis of the binary search tree
under the random permutation model. Two methods are mainly used : the rst one is the
embedding in continuous time and the second one is the tilting probability method. We get
new results on the binary search tree and also new proofs of known results."Il n’est de problemes qu’un manque
de solutions ne nisse par resoudre"
Henri QueuilleRemerciements
"C’est impossible..." impossible de faire ce calcul..."
Combien de fois ai-je pense cela pendant ma these?
On s’approche certainement de l’in ni !
Je tiens a remercier chaleureusement Emmanuel de m’avoir permis de me rendre compte
de mon erreur, c’etait possible ! !
En c^otoyant Emmanuel, j’ai appris que l’on pouvait mener a bout des calculs di ciles. J’ai
beaucoup apprecie son honn^etete intellectuelle, sa grande rigueur scienti que et la maniere
dont il a dirige ma these. Je tiens a le remercier pour son aide precieuse, sa grande connais-
sance des mathematiques qu’il a su partager avec moi, ainsi que la con ance qu’il m’a
accordee durant ces annees de these. Ce travail lui doit beaucoup.
Un grand merci aux rapporteurs Svante Janson et Liming Wu d’avoir eu la gentillesse et
la patience de lire en details mes travaux.
Merci a Jean Bretagnolle, Oleksiy Khorunzhiy, Michel Ledoux, Emmanuel Rio et Liming
Wu de me faire l’honneur de faire partie de mon jury.
Alain, Brigitte, Emmanuel et Jean-Fran cois (mes coauteurs), j’ai eu beaucoup de plaisir
a travailler a vos c^otes et je suis tres er que nous ayons a maintes reprises \invente l’eau
tiede et le l a couper le beurre".
Jean-Fran cois merite une medaille pour toute son aide. Merci pour ton aide mathematique,
informatique, les pauses cafes, les bieres, les parties de cartes...
Merci a toute l’equipe de Proba-Stats, en particulier a Alain qui, parce qu’il ne sait rien,
a su repondre a toutes mes questions.
Merci a tous les membres du LAMA et du departement de mathematiques pour votre
accueil chaleureux pendant ces annees de these.
Un petit coucou aux thesards, courage, c’est bient^ot ni !!
Un grand coucou a Laurence, merci d’avoir partage le stress des derniers mois, ainsi que les
nombreuses pauses pepitos.Voici maintenant venu le temps de dire merci a toutes les personnes qui comptent beau-
coup pour moi (que celles que je vais oublier me le pardonnent).
A ma famille, que je retrouve toujours avec bonheur qu’elle soit ici ou de l’autre c^ote de
la terre.
A tous mes amis, je ne con cois pas la vie sans vous.
A ceux qui ont connu le chinois a 36, son c^ote de Provence et ses sakes.
A mes compagnons qui ont goute aux joies des folles nuits du Paris medieval, du melo
coton aux courses dans les escaliers (comprenne qui pourra!!).
A tous les lyonnais, amis de longues dates (certains depuis pres de 15 ans), ceux qui se
souviennent du Parc, des parties interminables de coinche (regle numero 1 on ne coinche
pas a 80), des jeudis de beaujolais nouveaux (faire attention aux radiateurs), des troisiemes
mi-temps a la gauloise et de la Panda qui m’a si souvent ramenee chez moi.
A tous ceux de la cite, ceux qui se souviennent des bars et des soirees de la Deutsh et
ceux qui m’ont fait decouvrir tant de cultures di erentes.
A tous ceux, qui ne rentrent dans aucunes de ces categories, que j’ai rencontres sur un
terrain de rugby, ou qui depuis ma rencontre se me en t des cotons tiges (encore une fois
comprenne qui pourra!!).
A tous les idealistes et les r^eveurs...
En n, a Marta et a mon futur ls.
A vous tous,
je vous dedie ce travail, vous en ^etes tous un peu responsable.Table des matieres
I Introduction 11
II Inegalites de Concentration de type Talagrand 31
1 Inegalites de concentration a gauche de type T dans le cas i.i.d 33
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.2 Resultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.1 Lemme preparatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.2 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2 Inegalites de concentration de type Talagrand dans le cas d’independance 43
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2 Tensorization of entropy and related inequalities. . . . . . . . . . . . . . . . 48
2.3 Right-hand side deviations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4 Compensated empirical processes. . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5 Technical tools. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
III Inegalites de concentration convexe 63
3 Cas des variables negativement associees 65
3.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.2 De nitions and statement of results . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.1 Theorem for discrete time processes . . . . . . . . . . . . . . . . . . . 69
3.2.2 for continuous time processes . . . . . . . . . . . . . . . . . 70
3.3 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1 Proof of theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.2 Proof of 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.4 Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4.1 Supremum of binomial random variables . . . . . . . . . . . . . . . . 75
3.4.2um of Poisson v . . . . . . . . . . . . . . . . . 79
3.4.3 3-ary search trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4 Cas des martingales 87
4.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2 Expectation type result. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3 Variance type result. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.4 Brownian Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
IV Martingales et Arbres aleatoires 101
5 et Arbres aleatoires 103
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.1.1 The model of binary search trees . . . . . . . . . . . . . . . . . . . . 105
9TABLE DES MATIERES
5.1.2 Embedding of BST in a continuous time model . . . . . . . . . . . . 108
5.1.3 Yule process and fragmentation process . . . . . . . . . . . . . . . . . 109
5.1.4 Tiltings of the models . .