The Posterior Matching Feedback Scheme: Capacity Achieving and Error Analysis

Recently, we have introduced a sequential communication scheme for general memoryless channels with feedback based on the idea of posterior matching, providing a unified framework in which the known Horstein and Schalkwijk-Kaflath schemes are special cases. In this paper, we show that the posterior matching scheme achieves the mutual information for a large family of channels and input distributions, and provide closed-form expressions for the attainable error probability over a range of rates. Moreover, we derive the achievable rates in a mismatched setting, where the scheme is designed according to the wrong channel model. In particular, our results hold for discrete memoryless channels, thereby confirming a longstanding conjecture that the Horstein scheme achieves capacity. The proof techniques employed utilize novel relations between information rates and convergence properties of iterated function systems.