Résumé :
Les techniques de concentrations ont pour objet de prouver que la probabilité qu'une certaine variable aléatoire soit de valeur voisine de sa moyenne (espérance) est élevée. Ces techniques sont à la base des méthodes de preuve probabilistes (où l'on prouve l'existence de certains objets en prouvant que ce sont des évènements aléatoires de probabilité positive) et de l'analyse des algorithmes aléatoires (on cherche alors à prouver que presque sûrement l'algorithme aura un comportement satisfaisant).
Les techniques de concentration sont nées de la loi des grand nombres et du théorème central limite qui remontent au dix-huitième siècle. Ce cours abordera les bornes de concentration classiques.
Ainsi, commençant par les bornes de Markov et Chebycheff (valables pour toute variable aléatoire), nous introduirons la borne de Chernoff qui permet de traiter les sommes de variables de Bernouilli indépendantes. Puis nous étudierons des outils plus généraux, comme la méthode des différences finies (celle-ci repose sur l'usage de martingales) qui permet de prouver que le résultat d'un processus est souvent voisin de la moyenne que l'on peut espérer au départ ; et enfin les inégalités de Talagrand qui permettent de traiter le cas de variables non indépendantes.
Chaque borne de concentration sera
illustrée par des application en optimisation combinatoire.
Abstract:
Concentration technics aim to prove that the probability that some random variable will have a value close to its mean is large. Those technics are the main fondation of the probabilistic method (where one proves the existence of some object by showing that it is a random event with positive probability) or studying randomized algorithms (where one wants to show that almost surely the algorithm behaves nicely).
Concentration technics originate from the law of large numbers, and from the central limit theorem which were proved in the eighteen century. This talk will cover the most usual ones.
Hence starting from the old Markov and Chebychev bounds, we will introduce the Chernoff bound (which allows to treat sums of independant Bernouilli variables). Then we will focus on more general tools which allow to treat non independant variables: the bounded difference one (which relies on the use of martingales) and allows to prove that the outcome of a process is likely to be close to its expectation value at the beginning of the process ; and the more recent Talagrand inequalities which allow to treat non independant variables.
We will illustrate each technic use by some examples in combinatorial optimisation.