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

摘要

In dense Erd?s–Rényi?random graphs, we are interested in the events where large numbers of a given subgraphs occur. The mean behaviour of subgraph counts is known, and only recently were the related large deviations results discovered. Consequently, it is natural to ask, what is the probability of an Erd?s–Rényi?graph containing an excessively large number of a 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.?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 the special choice of exponential random graph that is indistinguishable from the Erd?s–Rényi?graph conditioned to have many triangles. We show how this choice can be made for the conditioned Erd?s–Rényi?graphs both in the replica symmetric phase and also in parts of the replica breaking phase. Equally interestingly, we also show that the exponential tilt suggested directly by the large deviation principle does not always yield an optimal scheme.