Modèles d'urnes et allocations aléatoires

Les modèles d'urnes sont parmi les modèles les plus courants d'allocations aléatoires, et peuvent être utilisés pour représenter nombre de phénomènes informatiques (l'exemple le plus connu est sans doute le hachage), en reliant le coût que l'on souhaite étudier à un paramètre tel que le nombre d'urnes ayant une certaine propriété. Leur comportement « statique », à un instant donné, peut souvent se décrire par des séries génératrices du type « grande puissance de fonction », et est alors analysable par les techniques classiques en analyse d'algorithmes ; il conduit fréquemment à des distributions limites suivant des lois de Poisson ou Gaussiennes. Par contraste, l'évolution « dynamique », au fil du temps et des mises à jour, est plus difficile à analyser.

Les travaux récents dans ce domaine sont centrés autour de phénomènes du type Anniversaires ou Collectionneur de coupons. Ils ont été motivés par l'analyse de deux algorithmes de génération aléatoire.

  • Le premier concerne la génération aléatoire boltzmannienne d'un produit de Hadamard, et conduit à un problème d'anniversaires généralisé: on ne considère que les anniversaires garçon/fille. Ce travail a été fait en collaboration avec O. Bodini et O. Roussel (Paris 6).
  • Le second est issu de la bio-informatique, plus précisément de la génération aléatoire de structures d'ARN. Il a été mené avec Y. Ponty (LIX).

Des travaux plus anciens concernent, à partir de l'étude de modèles particuliers (bases de données et apprentissage), des classes de modèles susceptibles d'un traitement uniforme. Nous avons commencé par étudier des modèles « semi-dynamiques », où seules les requêtes sans modification des données et les insertions sont autorisées : pour cette classe, et pour certaines valeurs des paramètres de départ (« domaine central »), le coût étudié peut être décrit asymptotiquement par un processus limite Gaussien.  Ces résultats peuvent être étendus à des modèles autorisant la suppression de données, ainsi qu'au cas multi-dimensionnel.

Quelques publications

J. du Boisberranger, D. Gardy et Y. Ponty: The weighted word collector. Colloque international AofA’12 (Montréal, Juin 2012).

O. Bodini, D. Gardy et O. Roussel: Boys and Girls Birthdays and Hadamard products. Fundamenta Informaticae, Vol. 117, pp. 85-101, 2012.

D. Gardy et Y. Ponty: Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models. 7th conference GASCOM (Génération Aléatoire de Structures COMbinatoires), Montréal (Canada), Septembre 2010.

M. Drmota, D. Gardy and B. Gittenberger. General urn models with several types of balls and Gaussian limiting fields. Random Structures and Algorithms, Vol.24 No.1, 2004.

D. Gardy. Occupancy urn models in analysis of algorithms. J. of Statistical Planning and Inference, special issue on the Fourth International Conference on Lattice Paths Combinatorics and Applications, Vol. 101 (1-2), pp. 95-105, Feb. 2002.

M. Drmota, D. Gardy et B. Gittenberger. A unified presentation of some urn models. Algorithmica, Special issue on the average-case analysis of algorithms, Vol. 29 No 1/2,  pp 120-147, 2001.

DMC Firewall is a Joomla Security extension!