A Simple Proof for the Optimality of Randomized Posterior Matching

DOI10.1109/TIT.2016.2549043MaRDI QIDQ2976789zbMATH OpenOpenAlexFDO

Authors Ofer Shayevitz, Meir Feder

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.08929

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Abstract: Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof showing it achieves capacity for a large class of memoryless channels. Naghshvar et al considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel Shannon-Jensen divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system (RIFS) decoder.

Recommendations

• Some new results on probability matching priors
• Improved bounds in stochastic matching and optimization
• Improved bounds in stochastic matching and optimization
• A Bayesian analysis of the matching problem
• Dempster-Shafer approximations and probabilistic bounds in statistical matching
• Convergence of asymptotic costs for random Euclidean matching problems
• Optimality of belief propagation for random assignment problem
• An optimal approximation algorithm for Bayesian inference
• On probability matching priors

This page was built for publication: A Simple Proof for the Optimality of Randomized Posterior Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976789)