Date & Time: Wednesday, August 17, 2016, 16:00-17:00.
Venue: Ramanujan Hall
Speaker: Bruce Hajek,
Prof. of Computer Science and Electrical Engineering
University of Urbana-Champaigne
NR Kamat Chair Prof. EE Dept, Iit Bombay
Title: Bounds Implied by Drift and Applications
Abstract: The drift of a real-valued random sequence at a particular time is equal to the conditional expected change in the sequence over the next time step, given the information known about the sequence up to the given time. If the drift is zero the sequence is known as a martingale. The actual change in the sequence is equal to the drift plus a conditional mean zero deviation. After each time step, a new drift can be calculated, and the random deviations from the drift add up over time. It is thus important to bound the cumulative effect of the deviations, to quantify whether the values of the sequence over a long period of time evolve according to the drift. This talk identifies an incomplete list of bounds implied by drift that have been used in many applications, including to analyze the performance of randomized algorithms for non-convex global optimization problems.