ICTS

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.

Zoom link: https://us02web.zoom.us/j/88670406480
Meeting ID: 886 7040 6480