2009/09/28 by Ofer Shayevitz, Meir Feder, Shayevitz, Ofer +1 · 4 citations
Computer Science · Mathematics · #Cellular Automata and Applications #FOS: Computer and information sciences #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.0909.4828
openalex publication_date 2009/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems.