Skip to main content

The importance sampling technique for understanding rare events in Erdős-Rényi random graphs

Publication ,  Journal Article
Bhamidi, S; Hannig, J; Lee, CY; Nolen, J
Published in: Electronic Journal of Probability
October 19, 2015

In dense Erdős-Rényi random graphs, we are interested in the events where large numbers of a given subgraph occur. The mean behavior of subgraph counts is known, and only recently were the related large deviations results discovered. Consequently, it is natural to ask, can one develop efficient numerical schemes to estimate the probability of an Erdős-Rényi graph containing an excessively large number of a fixed given subgraph? Using the large deviation principle we study an importance sampling scheme as a method to numerically compute the small probabilities of large triangle counts occurring within Erdős-Rényi graphs. We show that the exponential tilt suggested directly by the large deviation principle does not always yield an optimal scheme. The exponential tilt used in the importance sampling scheme comes from a generalized class of exponential random graphs. Asymptotic optimality, a measure of the efficiency of the importance sampling scheme, is achieved by a special choice of the parameters in the exponential random graph that makes it indistinguishable from an Erdős-Rényi graph conditioned to have many triangles in the large network limit. We show how this choice can be made for the conditioned Erdős-Rényi graphs both in the replica symmetric phase as well as in parts of the replica breaking phase to yield asymptotically optimal numerical schemes to estimate this rare event probability.

Duke Scholars

Published In

Electronic Journal of Probability

DOI

EISSN

1083-6489

Publication Date

October 19, 2015

Volume

20

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 0105 Mathematical Physics
  • 0104 Statistics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Bhamidi, S., Hannig, J., Lee, C. Y., & Nolen, J. (2015). The importance sampling technique for understanding rare events in Erdős-Rényi random graphs. Electronic Journal of Probability, 20. https://doi.org/10.1214/EJP.v20-2696
Bhamidi, S., J. Hannig, C. Y. Lee, and J. Nolen. “The importance sampling technique for understanding rare events in Erdős-Rényi random graphs.” Electronic Journal of Probability 20 (October 19, 2015). https://doi.org/10.1214/EJP.v20-2696.
Bhamidi S, Hannig J, Lee CY, Nolen J. The importance sampling technique for understanding rare events in Erdős-Rényi random graphs. Electronic Journal of Probability. 2015 Oct 19;20.
Bhamidi, S., et al. “The importance sampling technique for understanding rare events in Erdős-Rényi random graphs.” Electronic Journal of Probability, vol. 20, Oct. 2015. Scopus, doi:10.1214/EJP.v20-2696.
Bhamidi S, Hannig J, Lee CY, Nolen J. The importance sampling technique for understanding rare events in Erdős-Rényi random graphs. Electronic Journal of Probability. 2015 Oct 19;20.

Published In

Electronic Journal of Probability

DOI

EISSN

1083-6489

Publication Date

October 19, 2015

Volume

20

Related Subject Headings

  • Statistics & Probability
  • 4905 Statistics
  • 0105 Mathematical Physics
  • 0104 Statistics