# Asymptotic equipartition properties for simple hierarchical and networked structures

ESAIM: Probability and Statistics (2012)

- Volume: 16, page 114-138
- ISSN: 1292-8100

## Access Full Article

top## Abstract

top## How to cite

topDoku-Amponsah, Kwabena. "Asymptotic equipartition properties for simple hierarchical and networked structures." ESAIM: Probability and Statistics 16 (2012): 114-138. <http://eudml.org/doc/276390>.

@article{Doku2012,

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. },

author = {Doku-Amponsah, Kwabena},

journal = {ESAIM: Probability and Statistics},

keywords = {Asymptotic equipartition property; large deviation principle; relative entropy; random graph; multitype Galton-Watson tree; randomly coloured random graph; typed graph; typed tree.; asymptotic equipartition property; typed tree},

language = {eng},

month = {7},

pages = {114-138},

publisher = {EDP Sciences},

title = {Asymptotic equipartition properties for simple hierarchical and networked structures},

url = {http://eudml.org/doc/276390},

volume = {16},

year = {2012},

}

TY - JOUR

AU - Doku-Amponsah, Kwabena

TI - Asymptotic equipartition properties for simple hierarchical and networked structures

JO - ESAIM: Probability and Statistics

DA - 2012/7//

PB - EDP Sciences

VL - 16

SP - 114

EP - 138

AB - 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.

LA - eng

KW - Asymptotic equipartition property; large deviation principle; relative entropy; random graph; multitype Galton-Watson tree; randomly coloured random graph; typed graph; typed tree.; asymptotic equipartition property; typed tree

UR - http://eudml.org/doc/276390

ER -

## References

top- R. Arking, Biology of Aging, 2nd edition. Sinauer, Sunderland, MA (1998).
- J.D. Biggins, Large deviations for mixtures. Electron. Commun. Probab.9 (2004) 60–71. Zbl1060.60026
- J.D. Biggins and D.B. Penman, Large deviations in randomly coloured random graphs. Electron. Commun. Probab.14 (2009) 290–301. Zbl1185.05125
- 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.
- T.M. Cover and J.A. Thomas, Elements of Information Theory, in Wiley Series in Telecommunications (1991). Zbl0762.94001
- A. Dembo and I. Kontoyiannis, Source Coding, Large deviations and Approximate Pattern. IEEE Trans. Inf. Theory48 (2002) 1590–1615. Zbl1061.94016
- A. Dembo and O. Zeitouni, Large deviations techniques and applications. Springer, New York (1998). Zbl0896.60013
- 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. Zbl1078.60020
- K. Doku-Amponsah, Large deviations and basic information theory for hierarchical and networked data structures. Ph.D. thesis, Bath (2006). Zbl1318.60086
- K. Doku-Amponsah and P. Mörters, Large deviation principle for empirical measures of coloured random graphs. Ann. Appl. Prob.20 (2010) 1989–2021. Zbl1213.60054
- M.Kimmel and D.E.Axelrod, Branching Processes with Biology. Springer, New York (2002). Zbl0994.92001
- C.J. Mode, Multitype Branching Processes Theory and Applications. American Elsevier, New York (1971). Zbl0219.60061
- M.E. Newman, Random graphs as models of networks. URIhttp://arxiv.org/abs/cond-mat/0202208
- P. Olofsson and C.A. Shaw, Exact sampling formulas for multitype Galton-Watson processes. J. Math. Biol.45 (2002) 279–293. Zbl1013.92019
- D.B. Penman, Random graphs with correlation structure. Ph.D. thesis, Sheffield (1998).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.