Asymptotic equipartition properties for simple hierarchical and networked structures
ESAIM: Probability and Statistics, Tome 16 (2012), pp. 114-138.

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.

DOI : https://doi.org/10.1051/ps/2010016
Classification : 4A15,  94A24,  60F10,  05C80
Mots clés : 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
DA  - 2012///
SP  - 114
EP  - 138
VL  - 16
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ps/2010016/
UR  - https://www.ams.org/mathscinet-getitem?mr=2946123
UR  - https://doi.org/10.1051/ps/2010016
DO  - 10.1051/ps/2010016
LA  - en
ID  - PS_2012__16__114_0
ER  - 
Doku-Amponsah, Kwabena. Asymptotic equipartition properties for simple hierarchical and networked structures. ESAIM: Probability and Statistics, Tome 16 (2012), pp. 114-138. doi : 10.1051/ps/2010016. http://archive.numdam.org/articles/10.1051/ps/2010016/

[1] R. Arking, Biology of Aging, 2nd edition. Sinauer, Sunderland, MA (1998).

[2] J.D. Biggins, Large deviations for mixtures. Electron. Commun. Probab. 9 (2004) 60-71. | MR 2081460 | Zbl 1060.60026

[3] J.D. Biggins and D.B. Penman, Large deviations in randomly coloured random graphs. Electron. Commun. Probab. 14 (2009) 290-301. | MR 2524980 | Zbl 1185.05125

[4] C. Cannings and D.B. Penman, 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 1973541 | Zbl 1025.05055

[5] T.M. Cover and J.A. Thomas, Elements of Information Theory, in Wiley Series in Telecommunications (1991). | MR 1122806 | Zbl 1140.94001

[6] A. Dembo and I. Kontoyiannis, Source Coding, Large deviations and Approximate Pattern. IEEE Trans. Inf. Theory 48 (2002) 1590-1615. | MR 1909475 | Zbl 1061.94016

[7] A. Dembo and O. Zeitouni, Large deviations techniques and applications. Springer, New York (1998). | MR 1619036 | Zbl 0896.60013

[8] A. Dembo, P. Mörters and S. Sheffield, Large deviations of Markov chains indexed by random trees. Ann. Inst. Henri Poincaré : Probab. Stat. 41 (2005) 971-996. | Numdam | MR 2172206 | Zbl 1078.60020

[9] K. Doku-Amponsah, Large deviations and basic information theory for hierarchical and networked data structures. Ph.D. thesis, Bath (2006).

[10] K. Doku-Amponsah and P. Mörters, Large deviation principle for empirical measures of coloured random graphs. Ann. Appl. Prob. 20 (2010) 1989-2021. | MR 2759726 | Zbl 1213.60054

[11] M. Kimmel and D.E. Axelrod, Branching Processes with Biology. Springer, New York (2002). | MR 1903571 | Zbl 0994.92001

[12] C.J. Mode, Multitype Branching Processes Theory and Applications. American Elsevier, New York (1971). | MR 279901 | Zbl 0219.60061

[13] M.E. Newman, Random graphs as models of networks. http://arxiv.org/abs/cond-mat/0202208

[14] P. Olofsson and C.A. Shaw, Exact sampling formulas for multitype Galton-Watson processes. J. Math. Biol. 45 (2002) 279-293. | MR 1934415 | Zbl 1013.92019

[15] D.B. Penman, Random graphs with correlation structure. Ph.D. thesis, Sheffield (1998).

Cité par Sources :