Liste des résumés Aléa 2007

La liste des résumés est disponible également au format pdf. pdf

Résumés

1. Aguech, Rafik (Univ. Monastir)

Poids d'un parcours dans un Arbre binaire de recherche

Étant donné un Arbre binaire de recherche construit à partir de (x1,...,xn): un n échantillon de uniforme [0, 1], et un noeud xkn choisit au hasard parmi (x1,...,xn), on étudie le comportement du poids du parcours joignant les noeuds x1 et xkn. ( le poids d'un parcours ou d'un arc joignant les noeuds x et y est par définition la somme de tous les noeuds qui appartiennent à cet arc.)

2. Akhavi, Ali (Univ. Denis Diderot)

Autour de la LLL-réduction d'une base aléatoire

Pour g < n, soient b1, ..., bn−g, n − g vecteurs alétoires indépendants de Rn choisis selon une même distribution, invariante par rotation et sans masse en 0. Ces vecteurs sont presque sûrement indépendants et forment donc une base du réseau euclidien qu'ils engendrent. Dans cet exposé nous montrons l'existence d'une probabilité-limite (avec n) qu'une telle base soit réduite au sens de Lenstra, Lenstra et Lovász. La preuve est basée sur l'étude du processus (rg+1(n), rg+2(n), ..., rn−1(n)) où rj(n) est le ratio des carrés des normes de deux vecteurs consécutifs b*n−j+1 et b*n−j construits à partir des vecteurs de départ (b1,...,bn−g) par le procédé d'orthogonalisation de Gram-Schmidt. Nous montrons que lorsque n→+∞ le processus (rj(n)−1)j tend en distribution vers un processus (Rj −1)j et fournissons quelques indications sur cette distribution limite.

3. Avram, Florin (Univ. de Pau)

Premier passage des marches aléatoires au delà des frontières linéaires par morceaux

Nous améliorons les résultats asymptotiques présentés l'année dernière concernant le premier passage des processus de Levy et des marches aléatoires au delà des frontières linéaires par morceaux.

4. Banderier, Cyril (Univ. Paris-Nord)

Noyau d'un arbre aléatoire : c'est normal !

Lors d'un précédent aléa, j'avais fait un exposé sur les noyaux de graphes dirigés, et un traitement possible par série génératrice : un calcul d'espérance donnait déjà des résultats nouveaux pour les graphes très peu denses (= peu de cycles), seuls les cas des graphes denses ayant été préalablement étudiés par des probabilistes. Je me propose dans cet exposé de pousser l'étude jusqu'aux lois limites, et ce sur diverses familles simples d'arbres (travail en commun avec Alois Panholzer et Markus Kuba).

5. Broutin, Nicolas (McGill University)

Faire la lumière sur les tries et les arbres aléatoires

Les tries sont des structures de données arborées très couramment utilisées dans les algorithmes sur les mots. Un des paramètres chers en analyse d'algorithme est la hauteur moyenne, qui quantifie le pire comportement en moyenne. Jusqu'à présent, les hauteurs des tries ont été étudiées séparément de celles des autres structures d'arbres, ce qui est surprenant compte tenu des similarités apparentes entre les modèles. Nous proposons de regarder les tries sous un nouvel angle basé sur un mélange de grandes déviations, de profil, et d'interprétations géométriques. En particulier, nous distinguons deux phases: l'une est quasi-déterministe, l'aléatoire intervient seulement dans la seconde. La hauteur peut être expliquée par les contributions de chacune des phases. Cette approche permet de réconcilier les tries avec les autres type d'arbres, en particulier les arbres digitaux de recherche pour lesquels seule la phase déterministe a une influence. En outre, ce point de vue conduit à de nouvelles applications. Il permet d'obtenir la hauteur de tries construits sur des alphabets codés optimalement, ainsi que celle des arbres introduits par de la Briandais (1959) et des arbres ternaires de recherche dus à Bentley et Sedgewick (1997). Nous essaierons de présenter l'aspect unificateur pour l'étude des arbres aléatoires. Nous resterons aussi le plus proche possible des exemples et de l'intuition qui nous a conduit à développer cette approche. (Travail avec L. Devroye.)

6. Coupier, David (Univ. Lille 1)

Étude des configurations locales dans le modèle d'Ising

Sur un graphe d-dimensionnel, on considère le modèle d'Ising associé au champ magnétique a et au potentiel de paire b. La taille du graphe n est destinée à tendre vers l'infini et les potentiels a=a(n) et b=b(n) pourront dépendre de n.
Une configuration locale est un motif déterministe formé de spins + et −. Des conditions portant sur les potentiels a(n) et b(n) seront établies afin de décrire la probabilité d'apparition et le nombre d'occurrences dans le graphe d'une configuration locale donnée (fonctions seuils, approximations poissonniennes, inégalités exponentielles), ainsi que les distances séparant de tels objets.

7. Darrasse, Alexis (Univ. Pierre et Marie-Curie)

Réseaux apolloniens aléatoires et génération boltzmannienne d'arbres

Les Réseaux Apolloniens Aléatoires sont une structure récemment apparue pour modéliser les graphes du réel. Cette structure montre un comportement plus proche des graphes réels que les modèles dominants, pour ce qui est des propriétés les plus étudiées (degré, modularité, distance moyenne). Nous proposons l'étude d'un modèle voisin, fondé sur une bijection avec des arbres ternaires, dont nous montrons qu'il préserve les propriétés de base. Ce modèle offre aussi l'avantage d'une grande souplesse de génération grâce à l'utilisation de processus de Boltzmann, ce qui permet d'affiner l'adéquation avec les graphes réels.

8. Draief, Moez (Imperial College London)

Seuils épidémiques et applications à différentes familles de graphes

Nous nous intéressons aux conditions sous lesquelles on observe des transitions de phase pour deux modèles classiques d'épidémies (SIS et SIR). Nous appliquons ensuite les résultats généraux obtenus à certaines familles de graphes (graphe complet, hypercube, graphe régulier, graphe d'Erdös-Rényi et graphe power-law).

9. Duchon, Philippe (Université Bordeaux 1)

Génération aléatoire et propriétés statistiques de ``configurations de boucles compactes'' avec symétries

Les ``configurations de boucles compactes'' (fully-packed loop configurations, ou FPL) sont des configurations de chemins sans intersections, ``remplissant'' une grille carrée; elles sont le sujet, entre autres, de conjectures dues initialement aux physiciens Razumov et Stroganov. Les configurations présentant différentes formes de symétries ont été énumérées par Kuperberg. Je présenterai des algorithmes de génération aléatoire exactement uniforme, de type ``couplage depuis le passé'', pour différentes classes de symétrie, ainsi que des remarques expérimentales sur la ``forme'' asymptotique de ces objets.

10. Fekete, Eric (Univ. Versailles-Saint Quentin)

Marches branchantes sur l'ABR: convergence de la mesure d'occupation

Une marche aléatoire branchante est un objet à deux niveaux d'aléa : un arbre et des incréments. Nous nous intéressons ici aux marches dont l'arbre sous-jacent est l'Arbre Binaire de Recherche, et plus particulièrement à se mesure d'occupation. Selon certaines conditions sur les incréments, la mesure d'occupation correctement renormalisée converge faiblement vers une mesure déterministe. Cette convergence nous permet alors d'obtenir un résultat sur le profil des arbres récursifs et un autre sur la taille des fragments de certaines fragmentations homogènes.

11. Flajolet, Philippe (INRIA-Rocquencourt)

Comptage probabiliste

À venir.

12. Gardy, Danièle (Univ. Versailles-Saint Quentin)

Tautologies simples et implication

Parmi les différents types de formules booléennes, nous nous intéressons à celles qui sont construites à partir du connecteur d'implication ⇒ et des variables booléennes, et à la loi de probabilité P⇒ induite sur les fonctions booléennes.
Une conjecture de M. Zaionc (Cracovie) est que, dans un tel système, les tautologies ont, avec une probabilité tendant vers 1 lorsque le nombre de variables booléennes tend vers l'infini, une forme simple. Nous donnons une preuve de cette propriété, puis nous présentons les conséquences logiques qui en découlent, et qui permettent de comparer les pouvoirs d'expression de la logique intuitionniste et du calcul des propositions classiques.
Nous étudions également les liens entre la probabilité P⇒(f) d'une fonction booléenne f, et sa complexité.
Travail par en collaboration avec Hervé Fournier et Antoine Genitrini (PRiSM, Univ. Versailles St Quentin).

13. Gérin, Lucas (Université Henri-Poincaré)

Limites continues de certains Automates Cellulaires Probabilistes

L'objectif de cet exposé est de présenter un travail en cours avec P.Chassaing sur l'étude de limites éventuelles en tant que processus de certains Automates Cellulaires Probabilistes (ces objets ont déjà été présentés à ALEA par Schabanel et al. ces deux dernières années). Il s'agira de montrer comment certains de ces systèmes dynamiques très simples montrent des comportements asymptotiques très différents, certains liés au mouvement brownien.

14. Hafidi, Bezza (Université de Bourgogne)

Estimation de l'arbre de Contexte via les Critères BIC et MDL

Les critères BIC et MDL ont connu ces dernières années un intérêt important pour résoudre les problèmes de sélection de modèles. Récemment, Csizar et Talata (2005) ont traité le cas des chaînes de Markov à longueur variable. Ils ont proposé un algorithme pour calculer les estimateurs BIC et MDL de l'arbre de contexte. Dans ce travail, nous étudions la vitesse de convergence et la consistence de cet algorithme en tant qu'un critère d'estimer l'arbre de contexte. En collaboration avec Véronique Maume.

15. Herrbach, Claire (Univ. Paris-Sud)

Analyse de la complexité moyenne d'un algorithme d'alignement d'arbres

Le problème de l'alignement d'arbres consiste à construire un sur-arbre commun à deux arbres, grâce à un jeu d'opérations d'édition. L'algorithme d'alignement que nous étudions a pour but d'aligner des structures secondaires d'ARN, que l'on peut modéliser par des arbres. Il utilise un jeu d'opérations prenant en compte une certaine réalité biologique. Nous présenterons une analyse de la complexité moyenne de cet algorithme.

16. Koudou, Efoévi Angelo (Université Henri-Poincaré)

A Link between the Matsumoto-Yor Property and an Independence Property on Trees

Let X and Y be two non-dirac, positive and independent random variables. A necessary and sufficient condition for the random variables (X+Y)−1 and X−1−(X+Y)−1 to be independent is that X follows a generalized inverse Gaussian distribution while Y is gamma-distributed with suitable parameters. The sufficient part of this assertion, named in the related recent literature as the Matsumoto-Yor property, is included in a work by Matsumoto and Yor (2001). The general case of the Matsumoto-Yor property was given by Letac and Wesolowski (2000). (Let us note that, in spite of dates of publication, Matsumoto-Yor, 2001, precedes Letac and Wesolowski, 2000). It turns out that the Matsumoto-Yor property is, in the (non-generalized) inverse Gaussian case, a consequence of a work by Barndorff-Nielsen and Koudou (1998) where an exact distributional and independence result was established on a finite tree equipped with inverse Gaussian random resistances. To prove this, one only has to apply the latter result to a trivial tree (with only two edges).

17. Krikun, Maxim (Université Henri-Poincaré)

Attribution connexe à un processus de Poisson dans $R^2$

Dans [math.PR/0505668] Hoffman, Holroyd et Peres ont demandé, s'il existe un moyen d'attribuer à chaque site du processus de Poisson de l'intensité 1 dans le plan un territoire connexe de mesure de Lebesgue 1, de manière déterministe et invariante par des translations (c.-à-d. indépendamment du choix de système des coordonnées dans le plan). Nous proposons une solution qui utilise l'application de Riemann du plan moins un arbre infini vers le demi-plan.

18. Le Bars, Jean-Marie (Univ. Caen)

Énumération de fonctions booléennes 1-résilientes

Les fonctions interviennent depuis longtemps en cryptographie comme primitives cryptographiques, par exemple comme fonctions de combinaison et de filtrage dans les schémas de chiffrement à flots. Elles doivent satisfaire différents critères (degré algébrique, non-linéarité, k-résilience), mais il faut souvent trouver un compromis entre ces propriétés car elles induisent des incompatibilités partielles. Nous nous intéressons ici au critère d'immunité aux corrélations. Notre objectif est de classifier les fonctions booléennes et de mesurer la représentativité d'une fonction selon ce critère. Nous verrons une méthode pour coder les fonctions booléennes qui permet de classifier les fonctions selon leur distance aux fonctions sans corrélation d'ordre 1. Ce codage a de bonnes propriétés algorithmiques, nous disposons ainsi des premiers algorithmes efficaces pour énumérer et générer des fonctions 1-résilientes. Il permet aussi d'obtenir les premières bornes inférieures significatives du nombre de fonctions 1-résilientes.

19. Lelarge, Marc (ENS-Paris)

Arbre couvrant quasi minimal: un exposant critique pour des modèles probabilistes

Nous étudions la relation entre l'arbre couvrant minimal (ACM) sur des points aléatoires et l'arbre «quasi» optimal sous la contrainte qu'une proportion δ de ses arêtes sont différentes de celles de l'ACM. Un raisonnement heuristique suggère que quelque soit le modèle probabiliste sous-jacent, le ratio des longueurs des deux arbres doit varier en 1 + Θ(δ2). Nous montrons ce résultat d'échelle pour le modèle de la grille avec des longueurs d'arêtes aléatoires. Dans le modèle Euclidien de dimension 2, grâce à la connection bien connue entre ACM et percolation continue, nous réduisons la preuve du résultat d'échelle à un Ansatz qui étend un résultat technique connu dans le cas de la percolation sur la grille au cas de la percolation continue. Si le temps le permet, je présenterai un problème d'optimisation par programmation dynamique pour lequel le même exposant critique de 2 apparaît.
En collaboration avec David Aldous et Charles Bordenave (UC Berkeley).

20. Lhote, Loïck (Univ. Caen)

Traverses minimales dans un hypergraphe: applications et analyse en moyenne

Un hypergraphe est défini par un ensemble de sommets et un ensemble d'hyperarêtes, chaque hyperarête étant elle-même un ensemble de sommets. Une traverse minimale d'un hypergraphe est un ensemble de sommets, minimal au sens de l'inclusion, qui s'intersecte avec toutes les hyperarêtes. Générer les traverses minimales d'un hypergraphe est un problème théoriquement difficile mais qui a de nombreuses applications en intelligence artificielle, en fouille de données, en logique, pour les calculs arithmétiques, etc. Nous en présenterons certaines. Des algorithmes existent mais les complexités données font toutes intervenir des grandeurs inconnues comme le nombre de traverses minimales ou la taille de la plus grande traverse. Dans une deuxième partie de l'exposé, nous présenterons une analyse en moyenne de ces grandeurs avec un modèle simple (de type Bernoulli) d'hypergraphes aléatoires. En un sens, cette analyse permet de comparer les algorithmes entre eux.

21. Louchard, Guy (Univ. Libre de Bruxelles)

The Franklin Leader Election Algorithm

We start with a set of n players. We assign a classical permutation of {1,…,n} to the set, all players corresponding to a peak stay alive, the other ones are killed. If there are no peaks, we choose a player at random (this is assumed to have 0 cost), indeed in the original game, one deals with circular permutations, so there always exists at least one peak, here we first approach the problem with a classical permutation.
What is the distribution of the number Xn of phases before getting only one player? This is the essence of a Leader Election Algorithm proposed by W.R. Franklin. We present a first probabilistic analysis of this algorithm.

22. Marckert, Jean-François (Univ. Bordeaux 1)

Animaux dirigés et modèles de gaz

Un animal dirigé (AD) est un sous ensemble connexe d'un graphe orienté. Plus précisément, un animal dirigé A de source S, est un sous ensemble d'un graphe orienté G, tel que A contient S, et tel que tout élément de A peut-être atteint depuis un élément de S par un chemin orienté entièrement inclus dans A. Un gaz (à particules dures) sur G, est un sous ensemble indépendant de G : les sommets "occupés" ne sont pas voisins.
Afin d'énumérer les AD (de source un unique point) sur un réseau, Dhar (un physicien), a dans les années 80 exhibé une relation formelle entre la série génératrice des AD et la probabilité qu'un sommet du graphe soit occupé par un certain modèle de gaz aléatoire. Ce lien formel a ensuite été rendu rigoureux par M. Bousquet-Mélou.
Dans cet exposé, je propose de montrer que le lien formel établi par Dhar-Bousquet-Mélou peut s'expliquer au niveau des objets eux mêmes, et cela non seulement sur les réseaux, mais aussi sur tout graphe orienté.
Tout cela sera précédé par quelques rappels des résultats et des méthodes non probabilistes concernant l'énumération des animaux dirigés sur un réseau. (Travail commun avec Yvan Le Borgne).

23. Nicodème, Pierre (École Polytechnique)

Comptage d'occurrences d'un nombre fini de mots: une approche par inclusion-exclusion

Nous considérons le cas général de comptage de mots, où un mot peut être facteur d'autres mots. Noonan et Zeilberger ont résolu ce problème, sans toutefois ne donner de preuves ni de formules explicites; ils étendent pour ce faire la méthode d'inclusion-exclusion de Goulden et Jackson. Nous comparons, dans le cas d'un mot, la méthode formelle sur les langages de Régnier et Szpankowski, et la méthode d'inclusion-exclusion. Nous traitons ensuite le cas général de comptage de mots, en donnant preuves et exemples.
Travail en commun avec: Frédérique Bassino, Julien Clément et Julien Fayolle.

24. Pivoteau, Carine (Univ. Pierre et Marie-Curie)

Random sampling of plane partitions

This talk introduces random generators of plane partitions. Combining a bijection of Pak with the framework of Boltzmann samplers, we obtain an approximate-size and an exact-size sampler for plane partitions that have expected complexity respectively O(n ln(n)3 and O(n4/3) (under a real-arithmetic computation model). To our knowledge, these are the first polynomial-time samplers for plane partitions according to the size. The same principles yield efficient samplers for (p×q)-boxed plane partitions (plane partitions with two dimensions bounded).

25. Simatos, Florian (INRIA-Rocquencourt)

Résultats asymptotiques sur la première urne vide dans un modèle avec une infinité d'urnes

Motivé par le problème de la diffusion de l'information dans un réseau pair-à-pair, un modèle stochastique dans lequel N boules sont lancées dans une infinité d'urnes est étudié. Dans ce modèle, la probabilité pi qu'une boule tombe dans l'urne i est un nombre aléatoire, ce qui rend les lancers de boules dépendants. Le comportement asymptotique de l'index νN de la première urne vide est étudié.
Deux cas particuliers sont présentés. Dans le premier, les (pi) sont déterministes et ont une décroissance en loi de puissance. On montre alors que νN / q(N) converge en loi vers une constante, avec q(N) = (N / lnN)1/(ρ+ 1). Dans le deuxième cas, les (pi) s'écrivent à l'aide de variables aléatoires indépendantes, et il est prouvé que νN / q′(N) converge en loi vers une loi de Weibull, avec q′(N) = N1/(ρ+ 2).
L'inégalité de Chen-Stein est l'outil central utilisé pour obtenir ces résultats.

26. Vallée, Brigitte (Univ. de Caen)

Évolution des rationnels au cours de l'algorithme d'Euclide

L'évolution de la densité d'un réel lors de l'algorithme des fractions continues est un problème ancien, posé par Gauss lui-même, et bien étudié depuis. On sait que la densité évolue vers une densité limite, appelée densité de Gauss, égale à (1/ log2) 1/ (1+x), que la vitesse est exponentielle, etc...
Il est très naturel de se poser la même question dans le cadre discret, celui qui correspond donc à l'algorithme d'Euclide. La réponse à cette question a aussi des conséquences importantes quand on veut analyser les versions "rapides" de l'algorithme d'Euclide.
Puisque l'algorithme d'Euclide termine toujours avec un rationnel nul, la mesure limite finale est une mesure de Dirac concentrée en 0. Mais que se passe-t-il au cours de l'algorithme? La densité de Gauss intervient-elle quand même?
La réponse "discrète" est, comme souvent, plus complexe que la réponse "continue" et ... inattendue! Travail commun avec Eda Cesaratto, Julien Clément, Benoît Daireaux, Loïck Lhote, Véronique Maume.