Universal divergence estimation for finite-alphabet sources

Haixia Cai, Sanjeev R. Kulkarni, Sergio Verdú

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


This paper studies universal estimation of divergence from the realizations of two unknown finite-alphabet sources. Two algorithms that borrow techniques from data compression are presented. The first divergence estimator applies the Burrows-Wheeler block sorting transform to the concatenation of the two realizations; consistency of this estimator is shown for all finite-memory sources. The second divergence estimator is based on the Context Tree Weighting method; consistency is shown for all sources whose memory length does not exceed a known bound. Experimental results show that both algorithms perform similarly and outperform string-matching and plug-in methods.

Original languageEnglish (US)
Pages (from-to)3456-3475
Number of pages20
JournalIEEE Transactions on Information Theory
Issue number8
StatePublished - Aug 2006

All Science Journal Classification (ASJC) codes

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


  • Block sorting
  • Burrows-Wheeler transform
  • Context tree weighting method
  • Divergence estimation
  • Information divergence
  • Markov sources
  • Universal methods


Dive into the research topics of 'Universal divergence estimation for finite-alphabet sources'. Together they form a unique fingerprint.

Cite this