Exponential approximation,method of types for empirical neighbourhood distributions for random graphs by random allocation
No Thumbnail Available
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
International journal of Statistics and Probability
Abstract
In this article we find exponential good approximation of the empirical neigbourhood distribution ofsymbolled random graphs conditioned to a given empirical symbol distribution and empirical pair distribution.Using this approximation we shorten or simplify the proof of (Doku-Amponsah and Morters 2010, Theorem 2.5);the large deviation principle (LDP) for empirical neigbourhood distribution of symbolled random graphs. We alsoshow that the LDP for the empirical degree measure of the classical Erd˝os-R´enyi graph is a special case of (Doku-Amponsah and Moerters, 2010, Theorem 2.5). From the LDP for the empirical degree measure, we derive an LDP for the the proportion of isolated vertices in the classical Erd˝os-R´enyi graph.
Description
Keywords
concentration inequalities, coupling, empirical occupancy measure, empirical degree measure, sparse random graphs, bins and balls