Large deviation and entropic optimality in sparse settings

Seminar | October 18 | 3:10-4 p.m. | 1011 Evans Hall

 Shirshendu Ganguly, UC Berkeley

 Department of Statistics

The so called upper tail problem in the Erdos-Renyi random graph comes up naturally in the study of exponential random graph models and related graph ensembles with prescribed subgraph densities. The problem is broadly twofold:

(1) To estimate the probability that the number of copies of a graph H in a random graph is atypically large.

(2) To describe the structure of the random graph, in particular its clustering properties, in this situation.

This is a canonical example of a non-linear large deviation problem where the statistic of interest is a polynomial of independent bits. In this talk, I will describe some recent progress regarding the upper tail problem in the sparse setting, i.e., when the edge density decays to zero, involving solutions of certain entropic optimization problems.
Results in other related settings and open problems will also be presented.