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-Kailath 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.