Asymptotic equipartition properties for simple hierarchical and networked structures
Statistics Department, University of Ghana, Box LG 115, Legon, Ghana
Received: 19 June 2009
Revised: 31 March 2010
Revised: 9 June 2010
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.
Mathematics Subject Classification: 4A15 / 94A24 / 60F10 / 05C80
Key words: Asymptotic equipartition property / large deviation principle / relative entropy / random graph / multitype Galton-Watson tree / randomly coloured random graph / typed graph / typed tree.
© EDP Sciences, SMAI, 2012