Asymptotic equipartition properties for simple hierarchical and networked structures

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)114-138
Number of pages25
JournalESAIM - Probability and Statistics
Volume16
DOIs
Publication statusPublished - 2012

Keywords

  • Asymptotic equipartition property
  • Large deviation principle
  • Multitype Galton-Watson tree
  • Random graph
  • Randomly coloured random graph
  • Relative entropy
  • Typed graph
  • Typed tree.

Fingerprint

Dive into the research topics of 'Asymptotic equipartition properties for simple hierarchical and networked structures'. Together they form a unique fingerprint.

Cite this