PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Feedback Communication via Posterior Matching

Ofer Shayevitz, Meir Feder

arXiv:0909.4828v2cs.IT

TL;DR

The paper addresses how to obtain simple, optimal feedback communication schemes for general memoryless channels. It introduces posterior matching, derives a recursive scheme, and proves mutual-information achievability under general conditions, including BSC capacity for the Horstein scheme. It also develops error-probability analyses and identifies scope limitations for the presented framework.

  • Problem

    The paper seeks a general principle connecting existing optimal feedback schemes and extending simple capacity-achieving feedback communication beyond specific channels.

  • Method

    Posterior matching recursively transforms the message-point posterior into channel inputs with a selected input distribution, analyzed using concentration and iterated-function-system contraction.

  • Results

    The scheme achieves the mutual information for broad classes of channel and input-distribution pairs, and the Horstein scheme achieves BSC capacity.

  • Takeaways & Limitations

    Posterior matching provides a unified framework in which the Horstein and Schalkwijk–Kailath schemes are special cases, with recursive implementation for supported memoryless channels.

  • Takeaways & Limitations

    Extending the principle to channels with memory requires modification because transmissions independent of previous observations are not always optimal.

Abstract

from arXiv · show

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.

I Introduction

The paper introduces posterior matching as a unifying principle for simple, capacity-achieving feedback communication over general memoryless channels. It connects the Horstein and Schalkwijk–Kailath schemes and develops analyses of achievability and error probability.

  • Feedback preserves memoryless-channel capacity while potentially simplifying capacity-achieving transmission and improving error probability.
  • The Horstein scheme provides an early elegant feedback construction for the Binary Symmetric Channel.
  • The Schalkwijk–Kailath scheme achieves capacity for the AWGN channel using a message-point parameter-estimation strategy.
  • Posterior matching unifies these schemes through a simple recursive transmission strategy tailored to memoryless channels and desired input distributions.
  • The paper analyzes mutual-information achievability and error probability, including closed-form expressions over a range of rates.

II Preliminaries

The preliminaries establish notation for random variables, distributions, channels, feedback transmission schemes, decoding, rates, and achievability. They also introduce distribution-shaping tools used later in the posterior-matching construction.

  • CDFs and inverse CDFs can shape suitable random variables into uniform variables or recover variables from uniform ones, subject to the paper’s discreteness conventions.
  • The paper models a memoryless channel through a conditional distribution P_Y|X and an input/channel pair inducing joint and inverse-channel distributions.
  • A feedback transmission scheme uses measurable functions of the message point and previous input/output observations.
  • Achievability requires the rate not to fall below the target asymptotically and the error probability to vanish, with analogous constrained and pointwise versions.

C Markov Chains II PRELIMINARIES

This section defines the paper’s posterior-based decoding formalism and explains why it corresponds to standard reliable message decoding. The framework interprets achievability through posterior concentration around the transmitted message point.

  • Fixed-rate decoding selects a length-2^-nR interval with maximal posterior probability.
  • Variable-rate decoding selects the shortest interval whose posterior probability exceeds 1−δ_n, maximizing rate for a target error probability.
  • Both decoding rules use the message-point posterior, which can be calculated online at both terminals.
  • The nonstandard interval-based definitions are adopted because they simplify analysis while remaining compatible with standard coding achievability.
  • Achievability corresponds intuitively to posterior concentration in an interval of approximate size 2^-nR around the message point.

C Markov Chains

The preliminaries develop Markov-chain and iterated-function-system machinery for analyzing posterior matching. IFS and reversed IFS compositions provide the state evolution and contraction framework used in later convergence and error analyses.

  • Markov-chain background: A Markov chain is specified by an initial distribution and a stochastic kernel over a measurable state space.
  • Markov-chain background: Irreducibility together with an invariant distribution implies positive recurrence, uniqueness, and ergodicity under the stated conditions.
  • Markov-chain background: The preliminaries state p.h.r. conditions and convergence and strong-law results for suitable Markov chains.
  • Iterated function systems: An IFS evolves by repeated forward composition of random functions, while an RIFS uses the reversed composition order and supports the paper’s analysis.
  • Iterated function systems: Contraction functions and length functions provide conditions under which IFS or RIFS trajectories converge with specified decay profiles.

III Posterior Matching

Posterior matching converts the receiver’s missing message information into channel inputs with the desired marginal distribution. The resulting sequential schemes unify Horstein and Schalkwijk–Kailath and achieve mutual information under the paper’s stated conditions.

  • A The Basic Principle: Posterior matching selects new information independent of past outputs, while retaining enough information to recover the message point.The next input is a fixed function of this auxiliary random variable and is selected to have distribution P_X.
  • A The Basic Principle: I(Θ0; Y_n+1|Y^n) = I(X; Y), so each channel use conveys one-shot mutual information under the posterior matching principle.This identity follows from channel memorylessness, the input marginal P_X, and independence of the next output from past outputs.
  • B The Posterior Matching Scheme: The baseline scheme is simple to express and analyze, although infinitely many transmission functions satisfy the posterior matching principle.The paper develops a viable scheme and analyzes it rather than treating the information identity alone as an achievability proof.
  • B The Posterior Matching Scheme: The posterior matching construction stretches and redistributes posterior mass so that the message representation matches the desired input distribution.This interpretation motivates the name posterior matching and supports recursive representations in suitable settings.
  • B The Posterior Matching Scheme: For AWGN, the scheme sends a scaled MMSE error and becomes a variable-rate Schalkwijk–Kailath variant; for the BSC, it becomes the Horstein scheme.The Gaussian equivalence relies on independence coinciding with the relevant uncorrelatedness property in the AWGN case, while the BSC construction slices the posterior at its median.
  • B The Posterior Matching Scheme: In a simple example, the posterior matching scheme achieves mutual information with zero error using a variable-rate decoding rule.The posterior is uniform over shrinking intervals, and the interval size yields the mutual-information rate.

C The Normalized Channel

The normalized channel maps arbitrary input/channel pairs to a common unit-interval representation with uniform input. This representation preserves the relevant distributions and mutual information while enabling unified recursive analysis across channel types.

  • C The Normalized Channel: The normalized channel uses (0,1) as common input and output alphabets and represents the original input and output through distributional mappings.The output mapping may randomize uniformly across jump spans of the output c.d.f. when discontinuities occur.
  • C The Normalized Channel: The normalized channel preserves a uniform output distribution and the mutual information of the original input/channel pair.Its joint distribution is proper, and the normalized posterior kernel is continuous in its first argument almost everywhere.
  • C The Normalized Channel: A recursive representation uses the inverse normalized channel and yields a sequence of input/output pairs with an invariant joint distribution.The recursive and original posterior matching schemes are equivalent in distribution under the normalized construction.
  • C The Normalized Channel: When the input inverse c.d.f. is not injective, the original input/output sequence is a hidden Markov process, including for the BSC and Horstein scheme.The BSC normalized kernel provides the corresponding recursive representation of the Horstein scheme.
  • C The Normalized Channel: For the BEC with its capacity-achieving input, posterior matching repeats each bit until correct and achieves capacity 1 − p.The normalized kernel in this case is supported on three functions.
  • C The Normalized Channel: The framework extends to general DMCs and to constrained exponential-noise channels, including a closed-form scheme that achieves capacity under the input mean constraint.For DMCs, the normalized kernel is supported on finitely many continuous quasi-affine functions; the exponential-noise example uses a mixed input distribution.

IV Regularity Conditions for Input/Channel Pairs

The paper introduces regularity and ergodicity conditions needed to prove optimality of posterior matching. It organizes admissible input/channel pairs into families whose conditions imply mutual-information achievability.

  • IV Regularity Conditions for Input/Channel Pairs: Regularity conditions are introduced before proving posterior matching optimality and are designed to cover well-behaved input/channel pairs.The paper describes regularity as limiting excessive sensitivity of the channel law to input perturbations.
  • IV Regularity Conditions for Input/Channel Pairs: The assumptions include convex support, bounded densities, controlled conditional-density ratios, proper joint laws, unimodality, and bounded variance.For discrete memoryless channels, the stated setting requires nonzero transition probabilities.
  • IV Regularity Conditions for Input/Channel Pairs: The paper defines properties (A1)–(A5), including regularity, invariant-distribution conditions, fixed-point freeness, capacity-achieving input, and bounded continuous joint density.These properties provide alternative routes for establishing the behavior required by the achievability proof.
  • IV Regularity Conditions for Input/Channel Pairs: The families ΩA and ΩB collect input/channel pairs satisfying alternative combinations of regularity, ergodicity, fixed-point, and capacity conditions.The paper proves mutual-information achievability for members of ΩA ∪ ΩB.
  • IV Regularity Conditions for Input/Channel Pairs: Property (A3) together with bounded continuous joint density implies a stronger form of the invariant-distribution condition, placing ΩC inside ΩA.The intermediate implication is summarized as ΩC ⊂ ΩA.

V ACHIEVING THE MUTUAL INFORMATION

The posterior matching scheme achieves every rate below mutual information for broad classes of input/channel pairs, including constrained settings and canonical channels. The section also identifies technical conditions, examples, and boundaries concerning ergodicity and input-sequence behavior.

  • Main achievability result: Any rate R < I(X; Y ) is achievable by posterior matching for input/channel pairs in the stated classes, including specified input constraints.The theorem distinguishes fixed-rate and pointwise-achievable decoding and permits measurable constraints with finite expected constraint magnitude.
  • Continuous channels: The AWGN Schalkwijk-Kailath scheme pointwise achieves every rate below capacity I(X; Y ) = 1/2 log(1 + SNR).This result follows by applying Theorem V.1 to the corresponding input/channel pair.
  • Discrete channels: The Horstein scheme achieves BSC capacity I(X; Y ) = 1 − hb(p) for every nontrivial crossover probability, settling a longstanding conjecture.The posterior matching scheme coincides with Horstein’s scheme in this case.
  • Discrete channels: For general DMCs with nonzero transition probabilities and capacity-achieving inputs, posterior matching achieves capacity up to the stated technical conditions.The paper also extends the result to arbitrary input distributions satisfying the relevant fixed-point and regularity conditions, achieving rates up to I(X; Y ) within the encoded constraints.
  • Technical conditions: When the technical property B3 fails, an arbitrarily close input distribution can restore it, yielding rates arbitrarily close to I(X; Y ) while approximately preserving input constraints.The paper describes B3 as practically nonrestrictive and uses total-variation approximation to obtain a suitable distribution.
  • Scope and limitations: For some pairs outside the stronger ergodic class, capacity remains achievable but the empirical input distribution need not converge to the designated input distribution.If the capacity-achieving input is unique, the sample-path behavior nevertheless follows that distribution; otherwise it may depend on the ergodic component.
  • Examples: The exponential-noise channel with an input mean constraint admits pointwise rates below its mean-constrained capacity through a closed-form posterior matching scheme.The example relies on regularity and a fixed-point-free posterior matching kernel.
  • Proof of achievability: Under the proof’s rate argument, posterior mass in a 2^-nR neighborhood concentrates after (1+α)n iterations, supporting any rate below mutual information.The resulting variable-rate decoding error probability tends to zero as α becomes arbitrarily small.

VI Error Probability Analysis

The paper develops two error-probability analyses for posterior matching: a general contraction-based result and a more tractable result under additional regularity assumptions. These analyses connect achievable rates to iterated-function-system convergence, with exact consequences varying by channel and input distribution.

  • General contraction analysis: The decoded interval is obtained by rolling back a receiver interval through a reverse iterated function system, and its convergence determines the error-probability decay needed for rate achievability.The target interval has length 1 − pe(n), while the reverse dynamics recover the corresponding interval for the message point.
  • General contraction analysis: The general analysis uses a weight function and an associated contraction rate R†(ρ), but identifying a function yielding positive R† remains difficult.If no suitable contraction exists, the resulting threshold satisfies R† ≤ 0.
  • Regularity-based analysis: Under the theorem’s regularity conditions, posterior matching achieves any rate R < R*, and finite-range shaping can additionally yield zero-error decoding below R*(ρ).A further structural condition on the shaping function provides another specialized expression for the achievable rate.
  • Regularity-based analysis: For bounded-support input distributions, the identity shaping function can make the target error probability exactly zero for all sufficiently large blocklengths.The analysis states that the relevant tail function vanishes beyond the finite support bound.
  • Examples: For Gaussian inputs, the analysis recovers capacity achievability and the familiar double-exponential error-probability behavior, including under fixed-rate decoding.The fixed-rate conclusion follows because the interval contraction factor is independent of the output sequence.
  • Examples: In one example, the best analyzed shaping function supports rates only below R*(ρ2) ≈ 0.305, even though mutual information remains achievable by the main theorem.Thus the error analysis is narrower than the paper’s general achievability result for that channel and input pair.

VII Extensions

The extensions address fixed points, equivalent input/channel pairs, input reorderings, and channel-model mismatch. Under stated conditions, posterior-matching variants achieve rates below mutual information, while fixed points can prevent any positive rate.

  • Fixed points: A fixed point in the posterior-matching kernel can preserve posterior mass in an invariant interval, preventing any positive rate.The resulting Markov-chain invariant distribution is non-ergodic.
  • µ-variants: Different input orderings or µ-variants can eliminate fixed-point artifacts and expand the input/channel pairs for which mutual information is achievable.This extension is especially relevant for discrete memoryless channels and certain continuous-alphabet examples.
  • Equivalence: Equivalent input/channel pairs preserve mutual information, with equivalence induced by measure-preserving transformations of normalized inputs and outputs.The corresponding transformations define µ-related input/channel pairs.
  • Achievability: For admissible µ-variants, any rate R < I(X; Y) is achievable, including under measurable input constraints with finite expected constraint magnitude.The theorem distinguishes ordinary and pointwise achievability across different classes of input/channel pairs.
  • Channel-model mismatch: Under mismatch conditions, the achievable rate includes a nonnegative relative-entropy penalty that vanishes when the designed and actual models coincide.For Gaussian-noise mismatch, the scheme can preserve the designed SNR and attain rates below the designed Gaussian capacity despite non-Gaussian noise.

VIII Discussion

The discussion presents posterior matching as a simple, general feedback framework unifying established schemes and achieving mutual information under broad conditions. It also identifies unresolved limitations in error analysis, fixed-point optimization, model mismatch, and channels with memory.

  • Core framework: Posterior matching turns the receiver’s posterior c.d.f. at the message point into the next channel input through an explicit recursive rule.The recursion makes the transmission scheme depend only on the previous input/output pair.
  • Unified view: The framework unifies the Horstein and Schalkwijk-Kailath schemes and proves capacity achievability for discrete memoryless channels, including the Horstein scheme.The broader result establishes mutual-information achievability for suitable channel and input-distribution pairs.
  • Error analysis: RIFS contraction analysis yields closed-form exponential error-decay expressions, but finding suitable shaping functions and validating rates up to mutual information remain unresolved.The method can accommodate other contraction lemmas that may improve the error expressions.
  • Open questions: A fixed-point-free kernel is necessary for positive-rate achievement, while the best µ-variant for minimizing error probability remains to be characterized.The discussion suggests that proximity to a fixed point may worsen error performance.
  • Scope: Extending posterior matching to channels with memory requires modifying the principle to account for previous observations.The discussion connects this extension to directed information for channels with feedback.

A Main Proofs

The main proofs establish technical properties of posterior-matching kernels, ergodicity, achievability, and contraction. They also show how fixed points create decoding ambiguity and identify conditions under which kernel behavior supports positive-rate communication.

  • Kernel construction: The posterior-matching kernel maps normalized posterior coordinates through output-conditioned transformations, with recursive compositions governing posterior evolution.The proofs analyze these transformations using distribution functions, invariant sets, and Markov-chain representations.
  • Achievability: Achievability proofs relate posterior concentration around the message point to decoding intervals and construct message-point sets with sufficient separation.The construction converts a fixed-rate guarantee into achievability at lower rates.
  • Contraction: Contraction estimates are iterated recursively, with Markov’s and Jensen’s inequalities controlling the resulting bounds.The proofs use contraction relations to propagate decay across compositions of the kernel.
  • Ergodicity: For discrete memoryless channels, nonzero transition probabilities and kernel properties are used to establish ergodicity through invariant-set arguments.The proof shows that invariant sets must have probability zero or one under the relevant conditions.
  • Fixed points: A fixed point partitions the state space into invariant components, so the receiver cannot distinguish which component contains the message point.This ambiguity prevents positive-rate achievement and can make the invariant distribution non-ergodic.

B Pointwise Achievability Proofs

The proofs establish pointwise achievability by analyzing the posterior-matching process as an expanding, recurrent Markov chain. They extend convergence and rate arguments to fixed message points and mismatch operation.

  • B Pointwise Achievability Proofs: The reachable interval generated from any initial message point expands to (0, 1), establishing irreducibility of the normalized chain.The argument uses nested expanding intervals and continuity to show every positive-measure set is eventually reachable.
  • B Pointwise Achievability Proofs: The chain is positive Harris recurrent because its two-step skeleton admits a proper density, despite the one-step transition being deterministic in part.The two-skeleton retains the same invariant distribution and transfers positive Harris recurrence to the original chain.
  • B Pointwise Achievability Proofs: The expansion property rules out periods greater than one, so the normalized chain is aperiodic and converges to its unique invariant distribution.Aperiodicity follows because the expanding reachable sets cannot remain confined to disjoint cyclic classes.
  • B Pointwise Achievability Proofs: For any fixed message point, total-variation convergence reduces the analysis to the uniform-message case, allowing the pointwise achievability lemmas to apply.The recurrent aperiodic chain converges for every initial condition, including deterministic message points.
  • B Pointwise Achievability Proofs: Asymptotic blocks of k consecutive outputs approach i.i.d. uniform behavior in total variation, supporting the final rate-achievability argument.The k-fold chain approaches the k-fold invariant distribution, and the output sequence becomes asymptotically i.i.d. uniform.
  • B Pointwise Achievability Proofs: The mismatch chain remains analyzable under stated properties, and the scheme achieves every rate R < Rmis in the mismatch setting.The proof uses expansion, an invariant distribution, and contraction arguments to establish the mismatch rate bound.

C Miscellaneous Proofs

These proofs establish tail-regularity and entropy bounds for continuous input and conditional distributions under symmetry, unimodality, variance, and tail assumptions. The arguments extend the bounds from the input density to conditional densities.

  • C Miscellaneous Proofs: Symmetry around the density maximum reduces the tail analysis to one side without loss of generality.The proof then treats the negative and positive tails through symmetric arguments.
  • C Miscellaneous Proofs: Tail regularity is established for the input distribution by applying the derived bounds to both tails and setting γ = 1 − FX(x0).The same derivation applies to FX(x) for x < −x0.
  • C Miscellaneous Proofs: The conditional density fX|Y satisfies analogous estimates under common tail parameters, bounded variance, and the stated regularity assumptions.The proof follows the earlier derivation for the marginal density and applies the auxiliary lemma conditionally.
  • C Miscellaneous Proofs: Regular-tail assumptions, finite variance, and unimodality provide bounds on tail locations and density values used throughout the auxiliary estimates.The proof introduces tail parameters and recursively bounds points in the tail.
  • C Miscellaneous Proofs: The resulting estimates bound relative entropy and related integrals involving the input density and its transformed versions.These bounds rely on monotonicity, symmetry, and the assumed tail decay.
Loading 0909.4828v2…