Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah

ESAIM: Probability and Statistics (2012)

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

Abstract

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

How to cite

top

Doku-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
  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.  
  3. J.D. Biggins and D.B. Penman, Large deviations in randomly coloured random graphs. Electron. Commun. Probab.14 (2009) 290–301.  
  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.  
  5. T.M. Cover and J.A. Thomas, Elements of Information Theory, in Wiley Series in Telecommunications (1991).  
  6. A. Dembo and I. Kontoyiannis, Source Coding, Large deviations and Approximate Pattern. IEEE Trans. Inf. Theory48 (2002) 1590–1615.  
  7. A. Dembo and O. Zeitouni, Large deviations techniques and applications. Springer, New York (1998).  
  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.  
  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.  
  11. M.Kimmel and D.E.Axelrod, Branching Processes with Biology. Springer, New York (2002).  
  12. C.J. Mode, Multitype Branching Processes Theory and Applications. American Elsevier, New York (1971).  
  13. M.E. Newman, Random graphs as models of networks.  URIhttp://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.  
  15. D.B. Penman, Random graphs with correlation structure. Ph.D. thesis, Sheffield (1998).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.