Empirical processes, typical sequences, and coordinated actions in standard borel spaces

Research output: Contribution to journalArticle

Abstract

This paper proposes a new notion of typical sequences on a wide class of abstract alphabets (so-called standard Borel spaces), which is based on approximations of memoryless sources by empirical distributions uniformly over a class of measurable 'test functions.' In the finite-alphabet case, we can take all uniformly bounded functions and recover the usual notion of strong typicality (or typicality under the total variation distance). For a general alphabet, however, this function class turns out to be too large, and must be restricted. With this in mind, we define typicality with respect to any Glivenko-Cantelli function class (i.e., a function class that admits a Uniform Law of Large Numbers) and demonstrate its power by giving simple derivations of the fundamental limits on the achievable rates in several source coding scenarios, in which the relevant operational criteria pertain to reproducing empirical averages of a general-alphabet stationary memoryless source with respect to a suitable function class.

Original languageEnglish (US)
Article number6353589
Pages (from-to)1288-1301
Number of pages14
JournalIEEE Transactions on Information Theory
Volume59
Issue number3
DOIs
StatePublished - 2013

Keywords

  • Coordination via communication
  • Glivenko-Cantelli classes
  • empirical processes
  • rate distortion
  • source coding
  • standard Borel spaces
  • typical sequences
  • uniform law of large numbers (ULLN)

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Empirical processes, typical sequences, and coordinated actions in standard borel spaces'. Together they form a unique fingerprint.

  • Cite this