Modèles d'urnes et allocations aléatoires-old

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 recherches de l'équipe, parties de l'étude de modèles particuliers (bases de données et apprentissage), ont permis de dégager 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.

Publications

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.

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.

Our website is protected by DMC Firewall!