Local Large Deviations: A McMillian Theorem for Typed Random Graph Processes
DOI : 10.3844/jmssp.2017.347.352
Journal of Mathematics and Statistics
Volume 13, Issue 4
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.