Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, October 18, 2017 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


Large deviation and entropic optimality in sparse settings

Seminar: Probability 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.


alanmh@berkeley.edu