Title: A Sanov-type theorem for marked sparse random graphs and its
applications.
Speaker: Dr. Sarath Yasodharan, Postdoctoral Research Associate in the Division of Applied Mathematics at Brown University.
Day, Date, and Time: Tuesday 16th January, 2024, 09:30 am to 10:30 am
Venue: Seminar room IE 211, Second Floor, IEOR Building
Abstract: We prove a Sanov-type large deviation principle for the component empirical measure of certain families of sparse random graphs (including random regular graphs and Erdos-Renyi graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropies. We illustrate two applications of this result: (i) we quantify probabilities of rare events in stochastic networks on sparse random graphs, and (ii) we characterize the annealed free energy density of a broad class of probabilistic graphical models.
Bio: Dr. Sarath Yasodharan received his Ph.D. from the Indian Institute of Science in 2022, and he is currently a postdoctoral research associate in the Division of Applied Mathematics at Brown University. His research interests are in networking, applied probability, stochastic optimization, game theory, and data analytics.