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 language | English |
---|---|
Pages (from-to) | 114-138 |
Number of pages | 25 |
Journal | ESAIM - Probability and Statistics |
Volume | 16 |
DOIs | |
Publication status | Published - 2012 |
Keywords
- Asymptotic equipartition property
- Large deviation principle
- Multitype Galton-Watson tree
- Random graph
- Randomly coloured random graph
- Relative entropy
- Typed graph
- Typed tree.