Auswahl der wissenschaftlichen Literatur zum Thema „Analyse probabiliste d'algorithmes“

L'intelligence artificielle (IA) bouleverse le monde de la prévision météorologique avec l'utilisation d'algorithmes d'apprentissage profond nourris par des champs de réanalyses. Dans ce contexte, le Centre européen pour les prévisions météorologiques à moyen terme (CEPMMT) a décidé de développer un système de prévisions reposant sur l'IA. Ces prévisions, aujourd'hui de type déterministe, montrent des résultats prometteurs. Toutefois, le réalisme de ce type de prévision reposant sur l'IA est souvent questionné. Ici, nous identifions différents types de réalisme et interrogeons notamment le rapport entre réalisme structurel et prévisibilité des événements météorologiques. Une analyse statistique de prévisions déterministes reposant sur l'IA laisse apparaître un dilemme réalisme/performance qu'une approche probabiliste devrait aider à résoudre. Artificial intelligence (AI), based on deep-learning algorithm using high-quality reanalysis datasets, is showing enormous potential for weather forecasting. In this context, the European Centre for Medium-Range Weather Forecasts (ECMWF) is developing a new forecasting system based on AI. Verification results of deterministic forecast for now are promising. However, the realism of weather forecasts based on AI is often questioned. Here, different types of realism are identified and we discuss, in particular, the relationship between structural realism and predictability of weather events. Furthermore, a statistical analysis of deterministic forecasts based on AI points to a realism/performance dilemma that a probabilistic approach should help to solve.

L’intérêt porté aux algorithmes probabilistes est, entre autres,dû à leur simplicité. Cependant, leur analyse peut devenir très complexeet ce particulièrement dans le domaine du distribué. Nous mettons en évidencedes algorithmes, optimaux en terme de complexité en bits résolvantles problèmes du MIS et du couplage maximal dans les anneaux, qui suiventle même schéma. Nous élaborons une méthode qui unifie les résultatsde bornes inférieures pour la complexité en bits pour les problèmes duMIS, du couplage maximal et de la coloration. La complexité de ces analysespouvant facilement mener à l’erreur et l’existence de nombreux modèlesdépendant d’hypothèses implicites nous ont motivés à modéliserde façon formelle les algorithmes distribués probabilistes correspondant ànotre modèle (par passage de messages, anonyme et synchrone), en vuede prouver formellement des propriétés relatives à leur analyse. Pour cela,nous développons une bibliothèque, RDA, basée sur l’assistant de preuveCoq
Probabilistic algorithms are simple to formulate. However, theiranalysis can become very complex, especially in the field of distributedcomputing. We present algorithms - optimal in terms of bit complexityand solving the problems of MIS and maximal matching in rings - that followthe same scheme.We develop a method that unifies the bit complexitylower bound results to solve MIS, maximal matching and coloration problems.The complexity of these analyses, which can easily lead to errors,together with the existence of many models depending on implicit assumptionsmotivated us to formally model the probabilistic distributed algorithmscorresponding to our model (message passing, anonymous andsynchronous). Our aim is to formally prove the properties related to theiranalysis. For this purpose, we develop a library, called RDA, based on theCoq proof assistant

Dans la première partie de cette thèse, la vérification de propriétés booléennes monotones de variables booléennes dans un environnement avec erreurs est étudiée. La deuxième partie concerne surtout le calcul de la taille maximale moyenne de structures de données dynamiques

Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.

Dans cette thèse, nous nous intéressons au comportement asymptotique des distributions de coûts associés à des algorithmes d'Euclide de la classe rapide. Nous commençons dans un premier chapitre par des rappels sur les propriétés dynamiques des systèmes euclidiens et introduisons la propriété de moments forts pour les coûts additifs non-réseau. Nous établissons ensuite la condition de coût fortement diophantien et montrons sa généricité. Dans le deuxième chapitre, nous analysons, en adaptant des techniques de Dolgopyat-Melbourne, des perturbations d'opérateurs de transfert associés à des applications de la bonne classe. Ces résultats sont utilisés dans le troisième chapitre pour obtenir des estimations sur la fonction génératrice des moments où nous montrons sa quasi-décroissance exponentielle.

Le dernier chapitre est consacré aux démonstrations de téorèmes de la limite locale. Le premier théorème est sans vitesse de convergence et concerne tous les coùts non-réseau ayant des moments forts à l'ordre trois. La condition diphantienne nous permet ensuite d'établir un théorème de la limite locale avec contrôle de la vitesse de convergence. Pour des observables suffisament régulières, nous obtenons une vitesse de convergence optimale.

Cette thèse porte sur l'analyse d'algorithmes stochastiques et leur application en Finance notamment et est composée de deux parties. Dans la première partie, nous présentons un résultat de convergence pour des algorithmes stochastiques où les innovations vérifient une hypothèse de moyennisation avec une certaine vitesse. Nous l'appliquons ensuite à différents types d'innovations (suites i.i.d., suites à discrépance faible, chaînes de Markov homogènes, fonctionnelles de processus \alpha-mélangeant) et nous l'illustrons à l'aide d'exemples motivés principalement par la Finance. Nous établissons ensuite un résultat de vitesse ''universelle'' de convergence dans le cadre d'innovations équiréparties dans [0,1]^q et nous confrontons nos résultats à ceux obtenus dans le cadre i.i.d.. La seconde partie est consacrée aux applications. Nous présentons d'abord un problème d'allocation optimale appliqué au cas d'un nouveau type de place de trading: les {\em dark pools}. Ces places proposent un prix d'achat (ou de vente) certain, mais n'assurent pas le volume délivré. Le but est alors d'exécuter le maximum de la quantité souhaitée sur ces places. Ceci mène à la construction d'un algorithme stochastique sous contraintes à l'aide du Lagrangien que nous étudions dans les cadres d'innovations i.i.d. et moyennisantes. Le chapitre suivant présente un algorithme d'optimisation pour trouver la meilleure distance de placement d'ordres limites: il s'agit de minimiser le coût d'exécution d'une quantité donnée. Ceci mène à la construction d'un algorithme stochastique sous contraintes avec projection. Pour assurer l'existence et l'unicité de l'équilibre, des critères suffisants sur certains paramètres du modèle sont obtenus à l'aide d'un principe de monotonie opposée pour les diffusions unidimensionnelles. Le chapitre suivant porte sur l'implicitation et la calibration de paramètres dans des modèles financiers. La première technique mène à un algorithme de recherche de zéro et la seconde à une méthode de gradient stochastique. Nous illustrons ces deux techniques par des exemples d'applications sur 3 modèles: le modèle de Black-Scholes, le modèle de Merton et le modèle pseudo-CEV. Enfin le dernier chapitre porte sur l'application des algorithmes stochastiques dans le cadre de modèles d'urnes aléatoires utilisés en essais cliniques. A l'aide des méthodes de l'EDO et de l'EDS, nous retrouvons les résultats de consistance (convergence p.s.) et de normalité asymptotique (TCL) de Bai et Hu mais sous des hypothèses plus faibles sur les matrices génératrices. Nous étudions aussi un modèle ''multi-bras'' pour lequel nous retrouvons le résultat de convergence p.s. et nous montrons un nouveau résultat de normalité asymptotique par simple application du TCL pour les algorithmes stochastiques.

Le cadre générale de cette thèse est l'analyse quantitative des objets issus de la théorie des langages rationnels. On adapte des techniques d'analyse d'algorithmes (complexité en moyenne, complexité générique, génération aléatoire, ...) à des objets et à des algorithmes qui font intervenir des classes particulières d'automates. Dans une première partie nous étudions la complexité de l'algorithme de minimisation de Brzozowski. Bien qu'ayant une mauvaise complexité dans le pire des cas, cet algorithme a la réputation d'être efficace en pratique. En utilisant les propriétés typiques des applications et des permutations aléatoires, nous montrons que la complexité générique de l'algorithme de Brzozowski appliqué à un automate déterministe croît plus vite que tout polynôme en n, où n est le nombre d'états de l'automate. Dans une seconde partie nous nous intéressons à la génération aléatoire d'automates acycliques. Ces automates sont ceux qui reconnaissent les ensembles finis de mots et sont de ce fait utilisés dans de nombreuses applications, notamment en traitement automatique des langues. Nous proposons deux générateurs aléatoires. Le premier utilise le modèle des chaînes de Markov, et le second utilise la "méthode récursive", qui tire partie des décompositions combinatoires des objets pour faire de la génération. La première méthode est souple mais difficile à calibrer, la seconde s'avère plutôt efficace. Une fois implantée, cette dernière nous a notamment permis d'observer les propriétés typiques des grands automates acycliques aléatoires
The general context of this thesis is the quantitative analysis of objects coming from rational language theory. We adapt techniques from the field of analysis of algorithms (average-case complexity, generic complexity, random generation...) to objects and algorithms that involve particular classes of automata. In a first part we study the complexity of Brzozowski's minimisation algorithm. Although the worst-case complexity of this algorithm is bad, it is known to be efficient in practice. Using typical properties of random mappings and random permutations, we show that the generic complexityof Brzozowski's algorithm grows faster than any polynomial in n, where n is the number of states of the automaton. In a second part, we study the random generation of acyclic automata. These automata recognize the finite sets of words, and for this reason they are widely use in applications, especially in natural language processing. We present two random generators, one using a model of Markov chain, the other a ``recursive method", based on a cominatorics decomposition of structures. The first method can be applied in many situations cases but is very difficult to calibrate, the second method is more efficient. Once implemented, this second method allows to observe typical properties of acyclic automata of large size

Dans un grand éventail d'applications allant des sciences du climat à la finance, des événements extrêmes avec une probabilité loin d'être négligeable peuvent se produire, entraînant des conséquences désastreuses. Les extrêmes d'évènements climatiques tels que le vent, la température et les précipitations peuvent profondément affecter les êtres humains et les écosystèmes, entraînant des événements tels que des inondations, des glissements de terrain ou des vagues de chaleur. Lorsque l'emphase est mise sur l'étude de variables mesurées dans le temps sur un grand nombre de stations ayant une localisation spécifique, comme les variables mentionnées précédemment, le partitionnement de variables devient essentiel pour résumer et visualiser des tendances spatiales, ce qui est crucial dans l'étude des événements extrêmes. Cette thèse explore plusieurs modèles et méthodes pour partitionner les variables d'un processus stationnaire multivarié, en se concentrant sur les dépendances extrémales.Le chapitre 1 présente les concepts de modélisation de la dépendance via les copules, fondamentales pour la dépendance extrême. La notion de variation régulière est introduite, essentielle pour l'étude des extrêmes, et les processus faiblement dépendants sont abordés. Le partitionnement est discuté à travers les paradigmes de séparation-proximité et de partitionnement basé sur un modèle. Nous abordons aussi l'analyse non-asymptotique pour évaluer nos méthodes dans des dimensions fixes.Le chapitre 2 est à propos de la dépendance entre valeurs maximales est cruciale pour l'analyse des risques. Utilisant la fonction de copule de valeur extrême et le madogramme, ce chapitre se concentre sur l'estimation non paramétrique avec des données manquantes. Un théorème central limite fonctionnel est établi, démontrant la convergence du madogramme vers un processus Gaussien tendu. Des formules pour la variance asymptotique sont présentées, illustrées par une étude numérique.Le chapitre 3 propose les modèles asymptotiquement indépendants par blocs (AI-blocs) pour le partitionnement de variables, définissant des clusters basés sur l'indépendance des maxima. Un algorithme est introduit pour récupérer les clusters sans spécifier leur nombre à l'avance. L'efficacité théorique de l'algorithme est démontrée, et une méthode de sélection de paramètre basée sur les données est proposée. La méthode est appliquée à des données de neurosciences et environnementales, démontrant son potentiel.Le chapitre 4 adapte des techniques de partitionnement pour analyser des événements extrêmes composites sur des données climatiques européennes. Les sous-régions présentant une dépendance des extrêmes de précipitations et de vitesse du vent sont identifiées en utilisant des données ERA5 de 1979 à 2022. Les clusters obtenus sont spatialement concentrés, offrant une compréhension approfondie de la distribution régionale des extrêmes. Les méthodes proposées réduisent efficacement la taille des données tout en extrayant des informations cruciales sur les événements extrêmes.Le chapitre 5 propose une nouvelle méthode d'estimation pour les matrices dans un modèle linéaire à facteurs latents, où chaque composante d'un vecteur aléatoire est exprimée par une équation linéaire avec des facteurs et du bruit. Contrairement aux approches classiques basées sur la normalité conjointe, nous supposons que les facteurs sont distribués selon des distributions de Fréchet standards, ce qui permet une meilleure description de la dépendance extrémale. Une méthode d'estimation est proposée garantissant une solution unique sous certaines conditions. Une borne supérieure adaptative pour l'estimateur est fournie, adaptable à la dimension et au nombre de facteurs
In a wide range of applications, from climate science to finance, extreme events with a non-negligible probability can occur, leading to disastrous consequences. Extremes in climatic events such as wind, temperature, and precipitation can profoundly impact humans and ecosystems, resulting in events like floods, landslides, or heatwaves. When the focus is on studying variables measured over time at numerous specific locations, such as the previously mentioned variables, partitioning these variables becomes essential to summarize and visualize spatial trends, which is crucial in the study of extreme events. This thesis explores several models and methods for partitioning the variables of a multivariate stationary process, focusing on extreme dependencies.Chapter 1 introduces the concepts of modeling dependence through copulas, which are fundamental for extreme dependence. The notion of regular variation, essential for studying extremes, is introduced, and weakly dependent processes are discussed. Partitioning is examined through the paradigms of separation-proximity and model-based clustering. Non-asymptotic analysis is also addressed to evaluate our methods in fixed dimensions.Chapter 2 study the dependence between maximum values is crucial for risk analysis. Using the extreme value copula function and the madogram, this chapter focuses on non-parametric estimation with missing data. A functional central limit theorem is established, demonstrating the convergence of the madogram to a tight Gaussian process. Formulas for asymptotic variance are presented, illustrated by a numerical study.Chapter 3 proposes asymptotically independent block (AI-block) models for partitioning variables, defining clusters based on the independence of maxima. An algorithm is introduced to recover clusters without specifying their number in advance. Theoretical efficiency of the algorithm is demonstrated, and a data-driven parameter selection method is proposed. The method is applied to neuroscience and environmental data, showcasing its potential.Chapter 4 adapts partitioning techniques to analyze composite extreme events in European climate data. Sub-regions with dependencies in extreme precipitation and wind speed are identified using ERA5 data from 1979 to 2022. The obtained clusters are spatially concentrated, offering a deep understanding of the regional distribution of extremes. The proposed methods efficiently reduce data size while extracting critical information on extreme events.Chapter 5 proposes a new estimation method for matrices in a latent factor linear model, where each component of a random vector is expressed by a linear equation with factors and noise. Unlike classical approaches based on joint normality, we assume factors are distributed according to standard Fréchet distributions, allowing a better description of extreme dependence. An estimation method is proposed, ensuring a unique solution under certain conditions. An adaptive upper bound for the estimator is provided, adaptable to dimension and the number of factors

Pour optimiser la gestion des réseaux de télécommunication, nous considérons le système de file d'attente M^X / G / 1 avec rappels et clients impatients. En utilisant la méthode des variables supplémentaires, nous obtenons les fonctions génératrices partielles de l'état stationnaire conjointe de l'état du serveur et du nombre de clients dans le groupe de rappels. Pour compléter l'analyse du modèle considéré, nous calculons la distribution stationnaire de la chaîne de Markov induite, grâce à laquelle nous présentons la propriété de la décomposition stochastique. Cependant, la fonction génératrice de la distribution stationnaire du nombre de clients dans le groupe de rappels, est obtenue sous une forme explicite, très complexe et ne révèle pas la nature de la distribution en question. Alors, nous étudions le comportement asymptotique de la variable aléatoire représentant le nombre de clients en orbite et dans le système pour des valeurs limites des différents paramètres. Nous complétons notre travail par des exemples numériques.