Keynote Lectures
- Bruno Gaujal, INRIA -LIG
Title: Computing the Execution Time of Randomized Algorithm via Fluid Approximation.
Applications to the Coupon Collector, Perfect Sampling and Best Response algorithms.
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 be 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.
Finally, I will present another technique that also ends up solving a differential equation to compute the average execution time of the best response algorithm over potential games.
Part of the talk is based on a joint work with Nicolas Gast; The part on best response is based on a joint work with Stephane Durand.
- Offer Kella, The Hebrew University of Jerusalem
Title: Some martingales associated with Lévy driven queues.
Abstract:
This talk will summarize some continuous time martingales associated with Lévy driven queues. Namely, those that were reported in K and Whitt (1992), Asmussen and K (2000,2001), K and Boxma (2013) and, most recently, K and Yor (yet unpublished). Various applications will be demonstrated.
- Costis Maglaras, Columbia University
Title: Queueing models of (financial) limit order book markets
Abstract:
Most financial markets are becoming electronic, and typically operated as limit order books (LOB). Over short time scales, seconds to minutes, LOB can be best understood, modeled and analyzed as queueing systems. I will offer a brief overview of algorithmic trading and the electronic limit order book, and then highlight 3 or 4 questions related to order placement, order routing, and optimal execution that can be addressed using tools from stochastic network theory.
|
