Asymptotic equipartition properties for simple hierarchical and networked structures

DOI10.1051/PS/2010016MaRDI QIDQ4921829zbMATH OpenOpenAlexFDO

Authors Kwabena Doku-Amponsah

Publication date 14 May 2013

Published in ESAIM: Probability and Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.2523

zbMATH Keywords

random graphlarge deviation principlerelative entropyasymptotic equipartition propertymultitype Galton-Watson treetyped graphtyped treerandomly coloured random graph

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

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/logn$ can be coded by about $nH$ bits, where $H$ is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

Recommendations

• Lossy asymptotic equipartition property for hierarchical data structures
• scientific article; zbMATH DE number 1522491
• Strong laws of large numbers and the asymptotic equipartition property for the asymptotic \(N\)-branch Markov chains indexed by a Cayley tree
• Asymptotic equipartition property for second-order circular Markov chains indexed by a two-rooted Cayley tree
• Ergodic behavior of graph entropy

Cited in

(7)

• Joint large deviation principle for some empirical measures of the \(d\)-regular random graphs
• Theoretical aspects of equitable partition of networks into sparse modules
• A catalog of self-affine hierarchical entropy functions
• Large deviation principles for empirical measures of colored random graphs
• Lossy asymptotic equipartition property for hierarchical data structures
• The asymptotic equipartition property for a special Markov random field
• Asymptotic dependency structure of multiple signals

This page was built for publication: Asymptotic equipartition properties for simple hierarchical and networked structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4921829)