Research Article Open Access

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

Kwabena Doku-Amponsah1
  • 1 University of Ghana, Ghana


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.

Journal of Mathematics and Statistics
Volume 13 No. 4, 2017, 347-352


Submitted On: 8 July 2017 Published On: 29 November 2017

How to Cite: Doku-Amponsah, K. (2017). Local Large Deviations: A McMillian Theorem for Typed Random Graph Processes. Journal of Mathematics and Statistics, 13(4), 347-352.

  • 3 Citations



  • Local Large Deviation Principle
  • Variational Principle
  • Empirical Link Measure
  • Spectral Potential Theory
  • Relative Entropy
  • Typed Random Process