### A discrete theory of search. I

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

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

A general formalization is given for asynchronous multiple access channels which admits different assumptions on delays. This general framework allows the analysis of so far unexplored models leading to new interesting capacity regions. The main result is the single letter characterization of the capacity region in case of 3 senders, 2 synchronous with each other and the third not synchronous with them.