Journal of Mathematics and Statistics

Local Large Deviations: A McMillian Theorem for Typed Random Graph Processes

Kwabena Doku-Amponsah

DOI : 10.3844/jmssp.2017.347.352

Journal of Mathematics and Statistics

Volume 13, Issue 4

Pages 347-352


For a finite typed graph on n nodes and with type law µ on finite alphabet Γ, we define the spectral potential ρλ(., µ), of the graph. From the ρλ(., µ) we define the Kullback action or the divergence function, Hλ(π || v), with respect to an empirical link measure, π, as the Legendre dual. For the finite typed random graph conditioned to have an empirical link measure π and empirical type measure µ, we prove a Local large Deviation Principle (LLDP), with rate function Hλ(π || v) and speed n. From this LLDP, we obtain a full conditional large deviation principle and a weak variant of the classical McMillian Theorem for the typed random graph models. Given the typical empirical link measure, λµ⊗µ, we show that, the number of typed random graphs is equal to en||λµ⊗µ||H(λµ⊗µ⁄||λµ⊗µ||) approximately. Note that we do not require any topological restrictions on the space of finite graphs for these LLDPs.


© 2017 Kwabena Doku-Amponsah. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.