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.
Keywords: asymptotic equipartition property, large deviation principle, relative entropy, random graph, multitype Galton-Watson tree, randomly coloured random graph, typed graph, typed tree
@article{PS_2012__16__114_0, author = {Doku-Amponsah, Kwabena}, title = {Asymptotic equipartition properties for simple hierarchical and networked structures}, journal = {ESAIM: Probability and Statistics}, pages = {114--138}, publisher = {EDP-Sciences}, volume = {16}, year = {2012}, doi = {10.1051/ps/2010016}, mrnumber = {2946123}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ps/2010016/} }
TY - JOUR AU - Doku-Amponsah, Kwabena TI - Asymptotic equipartition properties for simple hierarchical and networked structures JO - ESAIM: Probability and Statistics PY - 2012 SP - 114 EP - 138 VL - 16 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ps/2010016/ DO - 10.1051/ps/2010016 LA - en ID - PS_2012__16__114_0 ER -
%0 Journal Article %A Doku-Amponsah, Kwabena %T Asymptotic equipartition properties for simple hierarchical and networked structures %J ESAIM: Probability and Statistics %D 2012 %P 114-138 %V 16 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ps/2010016/ %R 10.1051/ps/2010016 %G en %F PS_2012__16__114_0
Doku-Amponsah, Kwabena. Asymptotic equipartition properties for simple hierarchical and networked structures. ESAIM: Probability and Statistics, Volume 16 (2012), pp. 114-138. doi : 10.1051/ps/2010016. http://archive.numdam.org/articles/10.1051/ps/2010016/
[1] Biology of Aging, 2nd edition. Sinauer, Sunderland, MA (1998).
,[2] Large deviations for mixtures. Electron. Commun. Probab. 9 (2004) 60-71. | MR | Zbl
,[3] Large deviations in randomly coloured random graphs. Electron. Commun. Probab. 14 (2009) 290-301. | MR | Zbl
and ,[4] Models of random graphs and their applications, Handbook of Statistics. Stochastic Processes : Modeling and Simulation, edited by D.N. Shanbhag and C.R. Rao. Elsevier 21 (2003) 51-91. | MR | Zbl
and ,[5] Elements of Information Theory, in Wiley Series in Telecommunications (1991). | MR | Zbl
and ,[6] Source Coding, Large deviations and Approximate Pattern. IEEE Trans. Inf. Theory 48 (2002) 1590-1615. | MR | Zbl
and ,[7] Large deviations techniques and applications. Springer, New York (1998). | MR | Zbl
and ,[8] Large deviations of Markov chains indexed by random trees. Ann. Inst. Henri Poincaré : Probab. Stat. 41 (2005) 971-996. | Numdam | MR | Zbl
, and ,[9] Large deviations and basic information theory for hierarchical and networked data structures. Ph.D. thesis, Bath (2006).
,[10] Large deviation principle for empirical measures of coloured random graphs. Ann. Appl. Prob. 20 (2010) 1989-2021. | MR | Zbl
and ,[11] Branching Processes with Biology. Springer, New York (2002). | MR | Zbl
and ,[12] Multitype Branching Processes Theory and Applications. American Elsevier, New York (1971). | MR | Zbl
,[13] Random graphs as models of networks. http://arxiv.org/abs/cond-mat/0202208
,[14] Exact sampling formulas for multitype Galton-Watson processes. J. Math. Biol. 45 (2002) 279-293. | MR | Zbl
and ,[15] Random graphs with correlation structure. Ph.D. thesis, Sheffield (1998).
,Cited by Sources: