ESAIM: Probability and Statistics

Table of Contents - 2012 - Volume 16  

Research Article

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah

Statistics Department, University of Ghana, Box LG 115, Legon, Ghana. kdoku@ug.edu.gh

Abstract

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

(Received June 19 2009)

(Revised March 31 2010)

(Revised June 9 2010)

(Online publication July 3 2012)

Key Words:

  • Asymptotic equipartition property;
  • large deviation principle;
  • relative entropy;
  • random graph;
  • multitype Galton-Watson tree;
  • randomly coloured random graph;
  • typed graph;
  • typed tree.

Mathematics Subject Classification:

  • 4A15;
  • 94A24;
  • 60F10;
  • 05C80