PaperlayerView exact revision on arXiv

Source-linked AI summary

Achievability proof via output statistics of random binning

Mohammad Hossein Yassaee, Mohammad Reza Aref, Amin Gohari

arXiv:1203.0730v3cs.IT

TL;DR

The paper seeks a general achievability method for network information theory that can handle reliability together with statistical secrecy and coordination requirements. It develops OSRB from random binning and channel–source coding duality, using pmf approximation instead of typicality. The resulting framework gives channel-coding and secret-key achievability connections and supports strong-secrecy and multi-terminal applications.

  • Problem

    Existing achievability proofs repeatedly combine random coding and random binning, motivating a framework that addresses reliability and statistical constraints through a common construction.

  • Method

    The framework converts channel problems into source-coding problems, represents messages and shared randomness as random bins of i.i.d. variables, and analyzes their joint pmfs.

  • Results

    The framework yields a random-binning-only proof route for point-to-point channel coding through its duality with secret-key agreement, with negligible key-decoding error and complete key–public-message independence.

  • Takeaways & Limitations

    OSRB provides a unified way to express reliability, secrecy, and coordination constraints while avoiding direct manipulation of large channel codebooks.

  • Takeaways & Limitations

    Some coordination total-variation constraints are not covered by the framework’s general results and require additional proof techniques such as resolvability.

Abstract

from arXiv · show

This paper introduces a new and ubiquitous framework for establishing achievability results in \emph{network information theory} (NIT) problems. The framework uses random binning arguments and is based on a duality between channel and source coding problems. {Further,} the framework uses pmf approximation arguments instead of counting and typicality. This allows for proving coordination and \emph{strong} secrecy problems where certain statistical conditions on the distribution of random variables need to be satisfied. These statistical conditions include independence between messages and eavesdropper's observations in secrecy problems and closeness to a certain distribution (usually, i.i.d. distribution) in coordination problems. One important feature of the framework is to enable one {to} add an eavesdropper and obtain a result on the secrecy rates "for free." We make a case for generality of the framework by studying examples in the variety of settings containing channel coding, lossy source coding, joint source-channel coding, coordination, strong secrecy, feedback and relaying. In particular, by investigating the framework for the lossy source coding problem over broadcast channel, it is shown that the new framework provides a simple alternative scheme to \emph{hybrid} coding scheme. Also, new results on secrecy rate region (under strong secrecy criterion) of wiretap broadcast channel and wiretap relay channel are derived. In a set of accompanied papers, we have shown the usefulness of the framework to establish achievability results for coordination problems including interactive channel simulation, coordination via relay and channel simulation via another channel.

1 Introduction

The paper presents OSRB, an achievability framework that replaces traditional random coding with random binning through a channel–source coding duality. It uses pmf approximation rather than typicality and targets reliability, secrecy, and coordination constraints across several network settings.

  • 1 Introduction: The framework converts network information theory problems into source coding problems and uses random binning only.It constructs messages and shared randomness as bins of a single i.i.d. source sequence rather than using a large codebook.
  • 1 Introduction: OSRB is based on a duality between channel coding and source-model secret-key agreement.The key corresponds to the channel message, while the public message corresponds to the binning variable; secrecy and reliability become source-coding constraints.
  • 1 Introduction: The framework approximates joint pmfs in total variation instead of relying on typical-set counting or typicality decoding.This statistical approach is designed for settings requiring independence, secrecy, or closeness to a target distribution.
  • 1 Introduction: The OSRB theorem characterizes low-rate distributed binning through nearly independent, uniform bin indices that are also independent of an unbinned source.The complementary high-rate regime is associated with Slepian–Wolf recovery conditions.
  • 1 Introduction: The method makes adding secrecy immediate in examples such as moving from point-to-point communication to wiretap communication.The paper also describes applications to strong secrecy in multi-terminal settings and to coordination and channel simulation.
  • 1 Introduction: The framework unifies superposition and Marton coding as different specifications of the i.i.d. variables being binned.The paper further connects OSRB with hybrid coding and discusses its relation to prior soft-covering and random-binning approaches.

2 Motivation

The paper motivates OSRB through a duality between channel coding and source-model secret-key agreement. Random binning preserves the relevant statistics, enabling reliability and secrecy analyses through one i.i.d. source.

  • Channel–source duality: OSRB converts a primary network information theory problem into a more tractable dual source-coding problem with nearly identical joint statistics.The primary problem is recovered through an appropriate reverse encoder.
  • Channel–source duality: Shannon’s random-codebook proof can be reversed into a secret-key agreement proof by treating the message as the key and the codebook as public communication.The key and public message remain independent under the preserved joint distribution.
  • Channel–source duality: The channel-coding counterpart of secret-key agreement uses M as the message, F as shared randomness, and a reverse encoder obtained from random binning.The Slepian-Wolf bin F supports recovery, while independence of M and F preserves message uniformity after conditioning.
  • Framework advantages: Random binning constructs only one i.i.d. source copy, whereas direct channel coding requires handling a large codebook of codeword sequences.This source-coding viewpoint is presented as a practical advantage of the framework.
  • Secrecy is free: The framework replaces codebook-counting arguments with pmf approximation and supports strong secrecy through statistical independence conditions.The wiretap construction requires independence between the message and the eavesdropper’s observation, including shared randomness where applicable.
  • Secrecy is free: Adding secrecy requires only minor modifications: reliability needs RF > H(X|Y ), while secrecy needs RF + RM < H(X|Z).Together these constraints yield the achievable wiretap rate RM < I(X;Y) − I(X;Z).

3 Output statistics of random binning

This section develops output-statistics results for distributed random binning. The results characterize when bin indices approximate independent randomness and when Slepian-Wolf decoding reliably reconstructs sources.

  • Random binning model: A distributed random binning assigns each source sequence independent uniform bin indices, producing a random pmf over sources, side information, and bins.The binning maps each source sequence into indices with rates R1,…,RT.
  • Output statistics: Theorem 1 gives rate constraints under which the bin indices become approximately uniform and mutually independent of the side information for almost every binning realization.The theorem formalizes the mean independence property of the random bins.
  • Output statistics: The framework also yields achievable rates for extracting mutually independent random strings from separate channel outputs while keeping them independent of the channel input.This generalizes channel intrinsic randomness to a broadcast-channel setting.
  • Slepian-Wolf reconstruction: A Slepian-Wolf region provides conditions for approximating the target joint pmf when reconstructing X[1:T]^n from the side information and all bin indices.The reconstruction constraints are expressed for every subset S of sources.
  • Slepian-Wolf reconstruction: A specialized lemma gives sufficient conditions for recovering only X1^n from the side information and all distributed bins with error probability tending to zero.This reduced reconstruction result is used when the full source tuple need not be decoded.

4 Achievability proof through probability approximation

The paper turns the OSRB idea into a three-part achievability proof based on total-variation approximation. It constructs a source-coding protocol, transfers its properties to the assisted target problem, and removes shared randomness.

  • Probability approximation: The framework defines pmf approximation through total variation, with asymptotic random-pmf closeness requiring expected distance to vanish.For non-random pmfs, the same notation denotes a direct total-variation constraint.
  • Probability approximation: Several approximation rules transfer marginal and conditional closeness between distributions and identify source realizations with similar conditional laws.These rules support the successive pmf substitutions used in the achievability proofs.
  • Three-part proof structure: OSRB has three stages: define dual and assisted protocols, show their induced pmfs are close, then fix shared randomness without disturbing the desired properties.The desired properties may include reliability, secrecy, and distortion constraints.
  • Channel coding: For point-to-point channel coding, random binning creates message and shared-randomness indices, and a Slepian-Wolf decoder reconstructs the transmitted source sequence.The assisted protocol uses the reverse conditional pmf as a stochastic encoder and the Slepian-Wolf decoder as the channel decoder.
  • Channel coding: The proof first approximates the message–randomness distribution, then uses Slepian-Wolf reliability to obtain a joint distribution concentrated on correct reconstruction.The resulting fixed code has probability of error at most ϵn.
  • Wiretap channel: For the wiretap channel, the same construction additionally enforces the strong-secrecy criterion while proving achievability of I(X;Y) − I(X;Z).The message is uniform, the encoder is stochastic, and secrecy is measured through total variation.

4.4 Lossy source coding

The paper reproves lossy source-coding achievability by converting the problem into a source-coding protocol with random bins, then fixing shared randomness while preserving distortion.

  • The target result is achievability of any rate R > I(X; Y) when Ed(X, Y) < D.
  • Protocol A: Protocol A generates i.i.d. (X^n, Y^n), assigns Y^n independent random bins M and F, and uses Slepian-Wolf decoding to recover Y^n.M is the message, while F represents shared randomness.
  • Protocol B: Protocol B uses shared randomness F to generate Y^n from X^n, transmits its bin index M, and reconstructs it with the Slepian-Wolf decoder.Its induced pmf is explicitly factored through the source, shared randomness, generated sequence, bin index, and decoder.
  • Rate conditions: The induced pmfs approach one another when the shared-randomness rate satisfies ˜R < H(Y|X), while reliable Slepian-Wolf decoding requires R + ˜R > H(Y).The decoder-success condition yields an approximation in which the reconstruction equals the generated sequence.
  • Eliminating shared randomness: A fixed binning and a suitable instance F = f exist such that the resulting encoder-decoder achieves expected distortion below D without shared randomness.The proof first establishes the distortion bound for the induced pmf, then conditions on an instance of F and specifies the encoder and decoder.

4.5 Distributed channel synthesis

For distributed channel synthesis, the paper applies its random-binning duality to approximate the desired i.i.d. joint distribution, eliminate extra shared randomness, and recover the rate region.

  • Problem definition: Channel synthesis seeks encoder-decoders whose induced distribution on (X^n, Y^n) approaches the desired i.i.d. distribution in total variation.The model includes a limited-rate communication link and common randomness independent of the source.
  • Rate region: Theorem 2 characterizes achievability through an auxiliary U satisfying X−U−Y, the desired marginal pXY, and R0 + R1 > I(XY; U).
  • Protocol A: Protocol A generates jointly i.i.d. (X^n, U^n, Y^n) and assigns U^n three bins: message M, common randomness ω, and extra shared randomness F.The construction then uses a Slepian-Wolf decoder to recover U^n.
  • Protocol B: Protocol B generates U^n from (X^n, ω, F), sends its M bin, reconstructs U^n using (M, ω, F), and generates Y^n through p(y^n|u^n).The resulting induced pmf is given explicitly by the protocol factorization.
  • Proof conditions: The proof combines pmf approximation, Slepian-Wolf decoding, and independence conditions to obtain the desired joint distribution after fixing F, then eliminates the auxiliary rate by Fourier-Motzkin elimination.The relevant conditions include ˜R + R0 + R1 > H(U), ˜R < H(U|XY), and the independence condition in (31).
  • Eliminating shared randomness: After conditioning on a suitable F, the induced distribution remains close to p(x^n,y^n), and the resulting encoder-decoder obeys the desired vanishing total variation distance.Fourier-Motzkin elimination produces the stated rate region.

4.6 Wiretap broadcast channels with strong secrecy criterion

The wiretap broadcast-channel construction converts the problem into a random-binning source-coding protocol, then transfers reliability and strong secrecy through approximate pmf equivalence. The resulting achievable region extends Marton’s inner bound, with secrecy incorporated by conditioning on the eavesdropper’s observation.

  • Protocol construction: The protocol sends independent common and private messages through a stochastic encoder, while each receiver uses a Slepian-Wolf decoder to recover its message pair.Shared random bin indices support the source-coding formulation and are later eliminated by conditioning.
  • Reliability and secrecy: The construction achieves vanishing decoding error while making the messages nearly independent of the wiretapper output under the strong secrecy criterion.The secrecy approximation has the form ˆp(zn, m[0:2]|f[0:2]) ≈ pU(m[0:2])p(zn).
  • Achievable region: Theorem 3 states that achievable rate tuples lie in the convex hull of an extension of Marton’s inner bound for the wiretap broadcast channel.The theorem provides an achievable region for secure transmission with one common and two private messages.
  • Achievable region: The common-message constraint includes the two legitimate-receiver terms and subtracts the corresponding wiretapper terms, including an additional dependence penalty.A representative bound is 2R0 + R1 + R2 < I(U0U1;Y1|Q) − I(U0U1;Z|Q) + I(U0U2;Y2|Q).
  • Protocol equivalence: The induced pmf requires message and shared-randomness independence so the source-coding and channel-coding protocols can be made equivalent.The construction imposes bin-rate constraints and uses total-variation approximation to establish equivalence.
  • Strong secrecy: Adding secrecy is obtained by conditioning the entropy expressions on Z, so the framework carries secrecy into the broadcast-channel result without a separate coding construction.The paper explicitly describes this as obtaining secrecy for free.

4.7 Distributed lossy compression

The paper reproves the Berger-Tung inner bound by converting distributed lossy compression into a random-binning source-coding problem. Approximate pmf equivalence, Slepian-Wolf decoding, and elimination of shared randomness yield reconstructions satisfying both distortion constraints.

  • Problem and target: The distributed problem compresses two correlated sources into reconstructions whose expected distortions are at most D1 and D2.Each encoder observes one source and communicates a bin index to a joint decoder.
  • Achievable region: Theorem 4 recovers the Berger-Tung inner bound whenever suitable test channels and decoding functions meet the distortion conditions and R1 + R2 > I(X1X2;U1U2).The full theorem also includes the associated binning and decoding inequalities.
  • Protocol construction: The construction uses auxiliary variables U1 and U2 generated from the separate sources, with decoding functions producing the two reconstructions.The auxiliaries are jointly distributed with the sources, and the reconstructions are functions of both decoded auxiliaries.
  • Random binning: Each encoder assigns message and shared-randomness bins to its auxiliary sequence, and the decoder recovers both auxiliaries using a Slepian-Wolf decoder.The messages are retained for the main problem, while the shared randomness enables the source-coding protocol.
  • Protocol equivalence: The shared-randomness rates must preserve independence between each source and its corresponding shared-randomness index, with ˜Rj < H(Uj|Xj).Under the stated Markov structure, these individual constraints make the additional sum constraint redundant.
  • Distortion guarantee: After total-variation approximation and shared-randomness elimination, the induced reconstructions satisfy both distortion constraints with probability tending to one.The proof uses an i.i.d. marginal distribution and a concentration argument for the two distortion measures.

4.8 Lossy coding over broadcast channels

The OSRB framework gives a random-binning achievability proof for lossy transmission of an i.i.d. source over a broadcast channel. It yields distortion conditions and provides an alternative, straightforward proof related to hybrid coding.

  • Achievability result: A distortion pair (D1, D2) is achievable when suitable auxiliaries, encoding, and decoding functions satisfy the stated distortion and information inequalities.The conditions include the two inequalities in (62), together with Ed_j(S, Ŝ_j) ≤ D_j for j = 1, 2.
  • Proof construction: The proof uses random binning of U0, (U0, U1), and (U0, U2), followed by Slepian-Wolf decoding at the two receivers.Each receiver uses its observation and the relevant bin indices to recover the auxiliary sequences before producing a source estimate.
  • Proof construction: The induced pmfs are shown to approximate one another by combining bin-index independence conditions with reliable Slepian-Wolf decoding.A key condition is R0 + R1 + R2 < H(U[0:2]|S), while decoding requires R0 + Rj > H(U0Uj|Yj).
  • Proof construction: After eliminating shared randomness, the resulting encoder and decoders meet the desired distortions up to a vanishing term.The construction finds a fixed shared-randomness realization with distortion no greater than D_j + ε_n, where ε_n → 0.
  • Connection to hybrid coding: The framework supplies an alternative and straightforward achievability proof for hybrid coding in this broadcast lossy-transmission setting.Conditioning on shared randomness gives a codebook interpretation, while the same codebook supports both source- and channel-coding roles.

4.9 Relay channel with/without secrecy

The paper applies OSRB to relay channels and extends noisy network coding to a wiretap relay channel. The construction uses random binning and Slepian-Wolf decoding to obtain reliable communication, with secrecy added through bin-index independence conditions.

  • Scope: The section studies OSRB in a multi-hop setting through the relay channel and its wiretap extension, focusing on noisy network coding.The paper notes that extensions to multiple relays are possible but considers one relay for simplicity.
  • Problem definition: For the wiretap relay channel, the goal is to transmit a message reliably to the receiver while concealing it from the eavesdropper under strong secrecy.The channel has transmitter and relay inputs X and Xr, with outputs Yr, Y, and Z at the relay, receiver, and eavesdropper.
  • Results: The resulting construction extends the noisy network coding inner bound to a relay channel with an eavesdropper.When the eavesdropper is disabled, the stated constraints imply the noisy network coding inner bound for the ordinary relay channel.
  • Results: Specializations recover an achievable strong-secrecy rate for noise forwarding and a deterministic-relay bound by setting the compression variable appropriately.Setting Ŷr = φ gives noise forwarding; setting Ŷr = Yr yields the deterministic relay-channel specialization.
  • Construction: The protocol uses blockwise relay compression, random bin indices, and a final Slepian-Wolf decoder to reconstruct the transmitted sequence and message.The receiver estimates X^nB from its channel outputs and bin indices, then declares the bin index assigned to the estimate as the message.
  • Secrecy analysis: The condition R + Ṙ < H(X) makes the message bin and auxiliary bin nearly independent, supporting the secrecy analysis.Additional random relay-bin constraints are used to approximate the induced pmfs by the shared-randomness protocol.

5 Covering and Packing: Revisited

The paper revisits covering and packing through the OSRB framework, showing how random binning approximates desired joint statistics and yields a multivariate covering interpretation.

  • Relation to standard lemmas: Theorem 1 implies a form of multivariate covering, while the paper states that its discussion of packing is analogous and omitted.The covering form is related to, but not exactly the same as, the standard multivariate covering lemma.
  • Covering interpretation: Under the stated rate conditions, independently selected bins contain sequences jointly typical with one another and with Z^n with high probability.The construction generalizes the mutual-information rate terms associated with Marton coding.
  • Covering interpretation: Random binning partitions each sequence space into bins whose typical-sequence populations are approximately controlled by the bin rates.For bin rate R_i < H(X_i), each bin contains about 2^{nR′_i} typical sequences.
  • Covering interpretation: The resulting fixed binning has a joint distribution close to p_U(b[1:T])p(z), while retaining the typical-sequence counting interpretation.The approximation follows from the random-binning theorem and the existence of a suitable fixed partition.

A Proof of Theorem 1

The proof of Theorem 1 derives random-binning pmf approximation from expected fidelity bounds. Fidelity is converted into total variation control, and entropy conditions ensure convergence to the desired independent distribution.

  • Proof strategy: The proof establishes a one-shot random-binning result by bounding fidelity between the induced and desired pmfs over a common alphabet.The desired pmf is q(b[1:T], z) = p_U(b[1:T])p(z).
  • Fidelity bounds: Fidelity, also called the Bhattacharyya coefficient, measures similarity between two pmfs and lies between 0 and 1.The paper uses fidelity as the intermediate quantity before converting the result to total variation distance.
  • Fidelity bounds: The expected total variation distance between random pmfs is bounded using their expected fidelity.The bound is obtained from the relation between fidelity and total variation distance and applies to random pmfs P_X and Q_X.
  • Asymptotic conclusion: Applying the one-shot bound to i.i.d. sources shows that bin indices become close to independent of Z^n when every subset rate satisfies R_S < H(X_S|Z) − ε.Under these conditions, the relevant convergence quantity tends to one as n grows.
  • Generalization: The argument extends to general correlated sources by replacing average entropy with spectral inf-entropy.The paper states that the proof remains otherwise similar for the general correlated-source case.

Proof of Corollary 1

The corollary is proved by induction on T, reducing the constrained case to an approximation argument that establishes near-independence among bin indices and source observations.

  • The proof proceeds by induction on T, with the base case identified with Theorem 1.
  • When Theorem 1’s constraints hold, the corollary follows directly from that theorem.
  • If a subset constraint fails, the proof uses the resulting rate inequalities and the induction hypothesis to obtain near-independence.
  • Because B_S is a function of X_S^n, it can be introduced into the approximation without changing the desired conclusion.

C Proof of Lemma 3

The lemma’s remaining parts are established by bounding expectations, selecting a suitable sequence through Markov’s inequality, and applying the triangle inequality.

  • The second part bounds the relevant expectation and uses the first lemma part in intermediate steps.
  • Markov’s inequality establishes the existence of a specified x satisfying the required condition.
  • The third part follows from the triangle inequality together with the first lemma part.

D Proof of Lemma 5

The proof bounds the distance between the target and approximating distributions by combining the source distortion term with a total-variation approximation term.

  • The resulting bound is D + dmax, combining the expected distortion contribution with the distributional approximation error.

E Completing Proof of Theorem 6

The theorem’s final approximation is proved by induction on the number of blocks, connecting the two pmf factorizations through successive block-level approximations.

  • The appendix identifies two sufficient approximations for converting the pmf in (71) into the pmf in (72).
  • An induction on the block index b establishes the approximation for every b from 0 through B.
  • The induction step uses pmf factorization, the induction hypothesis, Lemma 4, the stated approximation, and a Markov-chain relation.
  • The desired approximation at each step follows from the two pmf factorizations, the intermediate approximation, and Lemma 4.
Loading 1203.0730v3…