Bruno GAUJAL - Researcher, INRIA Data Science
Date: - Location: Eurecom
Location : Eurecom, room 102 Speaker : Bruno GAUJAL Title : "Computing Absorbing Times via Fluid Approximation and Applications to the Coupon Collector and to Perfect Sampling" Abstract: The execution time of a large distributed algorithm can often be modeled by the hitting time of an absorbing state in a stochastic dynamic system. I will consider several cases of this general problem by computing the absorbing time of a discrete time Markov chain made of n objects, each with an absorbing state and evolving in mutual exclusion. By using a “Poissonization technique” that makes all the objects composing the chain asymptotically independent, I will show that the random absorbing time T(n) is well approximated by a deterministic time t(n) that corresponds to the first time when a fluid limit of the chain approaches the absorbing state at a distance less than 1/n. I will apply this result in three unrelated cases. The most direct one is the coupon collector with n coupons, for which we retrieve directly the well-known result that it takes on average n log n +( k-1) n log log n+O(n) steps to collect k samples of each coupon. Several generalizations of the coupon collector (invalid coupons, rare coupons) can also solved either in closed forms or through fast numerical computations. I will also show how to use this general approach to compute asymptotic equivalents (not merely bounds) of coupling times of random walks that correspond to the average execution time of perfect sampling algorithms. Part of the talk is based on a joined work with Nicolas Gast. Speaker's bio: Bruno Gaujal is an Inria researcher. Up to Dec. 2015, he has been the head of the large-scale computing group, MESCAL, in the research center of Inria Grenoble-Rhônes-Alpes. He has held several positions in AT&T Bell Labs, INRIA Sophia-Antipolis, Loria and École Normale Supérieure of Lyon. He is a former student at École Normale Supérieure of Lyon and obtained his PhD from University of Nice in 1994, under the supervision of François Baccelli. He got his “Habilitation à diriger des recherches” in 2001 from the university of Nancy. He is the author of more than 100 scientific publications in journals and international conferences. He is a founding partner and a scientific advisor of a start-up company, RTaW, since 2007. His main interests are in performance evaluation, optimization and control of large discrete event dynamic systems with applications to telecommunications networks and large computing infrastructures.
