ICTS:34422

A Sanov-type theorem for marked sparse random graphs and its applications

(2026). A Sanov-type theorem for marked sparse random graphs and its applications . SciVideos. https://scivideos.org/icts-tifr/34422

A Sanov-type theorem for marked sparse random graphs and its applications . SciVideos, Apr. 16, 2026, https://scivideos.org/icts-tifr/34422 

          @misc{ scivideos_ICTS:34422,
            doi = {},
            url = {https://scivideos.org/icts-tifr/34422},
            author = {},
            keywords = {},
            language = {en},
            title = {A Sanov-type theorem for marked sparse random graphs and its applications },
            publisher = {},
            year = {2026},
            month = {apr},
            note = {ICTS:34422 see, \url{https://scivideos.org/icts-tifr/34422}}
          }
Sarath Yasodharan
Talk numberICTS:34422
Source RepositoryICTS-TIFR
Collection

Abstract

We prove a Sanov-type large deviation principle for the component empirical measure of certain families of sparse random 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.

Joint work with I-Hsun Chen and Kavita Ramanan.