PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Channel Synthesis

Paul Cuff

arXiv:1208.4415v3cs.IT

TL;DR

The paper studies how to synthesize a discrete memoryless channel from a compressed description of its input when communication and independent common randomness are limited. It characterizes their optimal rate trade-off using a soft-covering-based achievability proof. The trade-off connects Wyner’s common information at one extreme with Shannon’s mutual information at the other, while supporting extensions to secrecy, game theory, and related randomness settings.

  • Problem

    The central problem is determining the communication and common-randomness resources needed for an encoder and distant decoder to reproduce the nearly i.i.d. behavior of a prescribed memoryless channel.

  • Method

    The paper constructs a feasible joint distribution through the soft covering lemma and infers encoder and decoder behavior without explicit joint typicality or binning.

  • Results

    The optimal trade-off has Wyner’s common information as the communication requirement without common randomness and Shannon’s mutual information with enough common randomness.

  • Takeaways & Limitations

    Distributed channel synthesis provides a resource-based view of correlation and connects channel simulation to secrecy systems and correlated strategies in game theory.

Abstract

from arXiv · show

Two familiar notions of correlation are rediscovered as the extreme operating points for distributed synthesis of a discrete memoryless channel, in which a stochastic channel output is generated based on a compressed description of the channel input. Wyner's common information is the minimum description rate needed. However, when common randomness independent of the input is available, the necessary description rate reduces to Shannon's mutual information. This work characterizes the optimal trade-off between the amount of common randomness used and the required rate of description. We also include a number of related derivations, including the effect of limited local randomness, rate requirements for secrecy, applications to game theory, and new insights into common information duality. Our proof makes use of a soft covering lemma, known in the literature for its role in quantifying the resolvability of a channel. The direct proof (achievability) constructs a feasible joint distribution over all parts of the system using a soft covering, from which the behavior of the encoder and decoder is inferred, with no explicit reference to joint typicality or binning. Of auxiliary interest, this work also generalizes and strengthens this soft covering tool.

I. INTRODUCTION

Distributed channel synthesis asks how an encoder and distant decoder can reproduce the nearly i.i.d. behavior of a prescribed memoryless channel under limited communication and common randomness. The paper characterizes this resource trade-off and develops a soft-covering-based proof technique for strong coordination.

  • Problem: An encoder observes an i.i.d. input sequence, sends a description to a distant decoder, and the decoder generates the channel output sequence.Success is judged by statistical indistinguishability from the distribution induced by the target memoryless channel.
  • Problem: The task requires input-output pairs to be nearly i.i.d. according to the prescribed memoryless channel, not merely empirically correlated.This stronger requirement distinguishes the paper’s strong coordination problem from typical source-coding objectives.
  • Applications: Distributed channel synthesis has applications to secrecy systems and game theory, where correlated strategies can benefit cooperating participants.The paper discusses channel synthesis as a means of communication in many repeated-game settings.
  • Resource trade-off: Without common randomness, communication requires Wyner’s common information, whereas sufficient common randomness reduces communication to Shannon’s mutual information.These quantities are the two extreme operating points of the paper’s communication–common-randomness trade-off.
  • Proof technique: The achievability proof constructs a joint distribution using the soft covering lemma and infers encoder and decoder behavior without explicit joint typicality or binning.The paper also generalizes soft covering, including an extension to superposition codebooks.
  • Resource trade-off: The system uses a transmitted message and common randomness independent of the channel input, and the paper characterizes the required rates of both resources.Block operation produces n outputs from n inputs while preserving conditional independence within the synthesized memoryless channel.

E. Main Result

Theorem II.1 characterizes the communication and common-randomness rates for synthesizing a discrete memoryless channel, with Wyner’s common information and mutual information as extreme operating points. Examples derive rate regions for erasure, reverse erasure, and scatter channels.

  • Theorem II.1: The achievable region consists of rate pairs satisfying R ≥ I(X; U) and R0 + R ≥ I(X, Y; U) for a Markov auxiliary U.The auxiliary distribution must induce QXQY|X, satisfy X−U−Y, and obey |U| ≤ |X||Y| + 1.
  • Extreme operating points: With no common randomness, the minimum communication rate is Wyner’s common information C(X; Y ).Wyner’s quantity is defined as min I(X, Y; U) over auxiliaries satisfying X−U−Y.
  • Extreme operating points: With unlimited common randomness, the communication requirement reduces to mutual information R ≥ I(X; Y ).Choosing U = Y attains equality, with sufficient common-randomness rate H(Y |X).
  • Erasure channel: For the symmetric erasure channel, the achievable region is parameterized by r ∈ [1 −p, r∗], with R ≥ r and R0 + R ≥ h(p) + r.Here r∗ = min{2(1 −p), 1}, and choices of r > r∗ are suboptimal.
  • Reverse erasure channel: For the reverse erasure channel, optimal parameters satisfy r ∈ [r∗, 1], where r∗ = min{2(1 −p), 1}, and choices of r < r∗ are suboptimal.The corresponding first rate inequality is R ≥ h(p) − rh.

I. Total Variation Distance

Total variation measures how closely the induced input-output distribution matches the desired channel distribution, with statistical indistinguishability as its operational motivation. The section also identifies a limitation: the main rate region may fail under Wyner-directed Kullback-Leibler divergence.

  • Definition: Total variation quantifies the distance between the induced and desired input-output distributions.It is defined for distributions Π and Γ on a common set.
  • Operational meaning: Small total variation prevents reliable detection of a synthesized channel by binary hypothesis tests.This supports the channel-synthesis objective of making synthetic and genuine channels statistically indistinguishable.
  • Operational meaning: Total variation also makes expectations of bounded functions continuous across nearby distributions.The resulting bound allows payoff analysis under the desired distribution when total variation is small.
  • Comparison with divergence: Kullback-Leibler divergence is generally stricter than total variation, while normalized divergence does not preserve the same relationship.For suitable i.i.d. distributions, a reverse asymptotic relationship can hold when absolute continuity is satisfied.
  • Limitation: The main rate region no longer holds when fidelity is measured by Wyner-directed Kullback-Leibler divergence.For the identity channel, rates below log |X| can yield infinite divergence, although positive channels can achieve exponential decay.
  • Broadcast extension: The broadcast extension synthesizes separate output sequences using a common encoder transmission and common randomness.Its achievable region is characterized by R ≥ I(X; U) and R0 + R ≥ I(X, Y1, ..., Ym; U), subject to the broadcast auxiliary-variable constraints.

B. Game Theory

The paper applies distributed synthesis to coordinated actions in repeated games, where communication limits constrain cooperative strategies. It also gives secrecy and limited-memory variants with distinct communication–common-randomness trade-offs.

  • Game setup: Team A’s players coordinate repeated-game actions through a secure channel limited to R bits per iteration.Player 1 selects Xt and communicates with Player 2, who selects Yt.
  • Game-theoretic synthesis: Optimal cooperative strategies can be represented by i.i.d. actions drawn from a designed joint distribution.The achievable rate-payoff region is characterized by R ≥ C(X; Y) and Π ≤ minz∈Z E π(X, Y, z).
  • Game-theoretic synthesis: Convexification can make time-sharing between low- and high-communication strategies optimal under an average-rate constraint.The paper notes that splitting time between efficient strategies may preserve competitive performance.
  • Secrecy: With public communication, common randomness can serve as a one-time pad, producing optimal secrecy rate pairs.The resulting region requires R ≥ I(X; U) and R0 ≥ I(X, Y; U).
  • Secrecy: In the public-communication setting, the required common-randomness rate exceeds the communication rate, and the two separate extrema cannot generally be attained together.The common-randomness and communication rates can individually reduce to common information and mutual information, respectively.
  • Limited-memory fidelity: For tests with memory B = bn, an achievable region includes R ≥ I(X; U) and R0 + R ≥ bI(X, Y; U).If B is finite and does not grow with n, no common randomness is required and communication need only exceed I(X; Y).

E. Local Randomness

The paper extends distributed channel synthesis to limited decoder-local randomness and relates the resulting trade-offs to common-information duality and secrecy settings. It also develops a soft covering tool used in the achievability proof.

  • Local Randomness: The decoder can be modeled as deterministic while using rate-limited local randomness.The local-randomness extension assigns the decoder a rate R_L of private random bits.
  • Local Randomness: The achievable rate triples satisfy R ≥ I(X; U), R0 + R ≥ I(X, Y; U), and R_L ≥ H(Y|U) for some auxiliary U.These inequalities characterize the closure of the synthesis region for communication, common randomness, and decoder-local randomness.
  • Local Randomness: When all local-randomness inequalities are tight, the total randomness entering the synthetic channel is R0 + R_L = H(Y|X).This total excludes the minimally random encoder and is described as efficient compared with local synthesis.
  • Common Information Duality: Common-information duality pairs extracting shared randomness from correlated observations with generating correlated sequences from shared randomness.The two settings have rates C_G-K(X;Y) and C_W(X;Y), respectively.
  • Communication and Duality: Allowing communication independent of the receiver output relaxes the required randomness rate to I(X;Y) in both complementary settings.A communication rate H(Y|X) is sufficient in the synthesis setting and necessary for most distributions.
  • Soft Covering: The achievability argument relies on soft covering, where averaging conditional output distributions over a sufficiently large random codebook approximates an i.i.d. distribution.For memoryless channels, the sufficient codebook rate is R > I(U;V), and the paper strengthens the tool with exponential bounds.

B. Soft Covering Lemma Statement

The soft covering lemma shows that a random codebook passed through a memoryless channel can synthesize the desired i.i.d. output distribution when its rate exceeds the relevant mutual information. This lemma supplies the distributional foundation for the channel-synthesis construction.

  • Lemma Statement: A random codebook of 2^{nR} input sequences is selected uniformly and passed through a memoryless channel to induce an output distribution.The induced output distribution is random because the codebook itself is random.
  • Lemma Statement: R > I_Φ(U;V) guarantees that the expected total variation between the induced and desired output distributions vanishes as n increases.The convergence criterion is lim n→∞ E ||P_V^n − Q_V^n||_TV = 0.
  • Lemma Statement: The expected total variation converges exponentially fast under the strengthened soft covering result.The exponent is specified through γ in the paper’s later analysis.
  • Application: The synthesis proof constructs a joint distribution satisfying structural constraints by construction, then uses soft covering to establish the remaining approximation properties.The construction starts from an auxiliary distribution and a random codebook indexed by communication and common-randomness indices.
  • Application: The resulting likelihood encoder and decoder preserve the required Markov structure and exact resource cardinalities after the construction is adjusted.The encoder is defined from the conditional codeword distribution, while the decoder uses the induced conditional output channel.

C. Synthesis Analysis

The synthesis analysis uses two soft-covering applications and total-variation properties to show that the constructed distribution meets the achievability requirements. It then summarizes the corresponding stochastic encoder and decoder and develops supporting converse tools.

  • Synthesis Analysis: Soft covering is applied first at rate R0 + R to approximate the joint input-output distribution generated through the auxiliary codebook.A second application uses each fixed common-randomness subcodebook at rate R to control the input distribution.
  • Synthesis Analysis: Total variation terms vanish as n grows, so the constructed distribution satisfies the synthesis requirement and nearly satisfies the independence and i.i.d. conditions.The final bound uses marginal contraction and invariance under a common channel.
  • Encoder and Decoder: The likelihood encoder restricts attention to the subcodebook selected by common randomness and samples a codeword according to its likelihood under Q_X|U.Most selection probability is concentrated on codewords jointly typical with the observed source sequence.
  • Encoder and Decoder: The decoder identifies the codeword from the common randomness and message, then locally synthesizes Y^n through the memoryless channel Q_Y|U.Decoder randomization of H(Y|U) per channel use is fundamental and unavoidable.
  • Supporting Tools: A cardinality argument reduces the auxiliary-variable search to a finite bound while preserving the relevant Markov-chain and information properties.The connected-set version of Carathéodory’s theorem yields at most |X||Y|+1 auxiliary values.
  • Supporting Tools: The analysis uses random-time-index and entropy-continuity lemmas to relate nearly i.i.d. sequence distributions to single-letter information quantities.These tools bound total variation at a random time and control entropy differences for finite alphabets.

C. Epsilon Rate Region

The converse introduces an epsilon rate region for nearly synthesized distributions and uses a random time index to construct a single-letter auxiliary variable. This establishes that every achievable rate pair lies in the stated region up to vanishing continuity terms.

  • Epsilon Rate Region: The epsilon rate region requires R ≥ I(X;U) and R0 + R ≥ I(X,Y;U) − 2g(ε) for an auxiliary distribution in D_ε.The distribution must satisfy total-variation proximity, the Markov chain X−U−Y, and |U| ≤ |X||Y|+1.
  • Epsilon Rate Region: Any achievable rate pair belongs to the epsilon rate region.The converse begins with an arbitrary achievable synthesis code and derives the required single-letter constraints.
  • Single-Letterization: A uniformly random time index T converts the block distribution into single-letter variables X_T and Y_T, with X_T independent of T because the source is i.i.d.The output variable Y_T need not be independent of T.
  • Single-Letterization: The Markov chain X_T−(J,K,T)−Y_T follows from conditional independence of the full input and output sequences given J and K.The cardinality lemma then supplies an auxiliary U with the required single-letter structure.
  • Single-Letterization: The induced variables satisfy I_Γ(X;U) = I_P(X_T;J,K,T) and I_Γ(X,Y;U) = I_P(X_T,Y_T;J,K,T).These identities connect the auxiliary-variable information terms to the communication and common-randomness indices.

D. Continuity of Sǫ at Zero

The rate region S is established as closed, and the epsilon-relaxed regions Sε decrease to S as ε approaches zero. The surrounding soft-covering results extend this framework to general sources and channels and imply vanishing total variation under stated conditions.

  • D. Continuity of Sε at Zero: The epsilon rate regions Sε decrease to the closed set S as ε decreases to zero.This is stated as Lemma VI.5 and underpins continuity at zero.
  • D. Continuity of Sε at Zero: The proof handles the nontrivial reverse inclusion by contradiction, excluding intermediate rate pairs from a suitably chosen relaxed region S′ε.The construction chooses ε so that the relaxation cannot reach the hypothesized boundary point.
  • D. Continuity of Sε at Zero: Closedness of S relies on a bounded auxiliary alphabet, compactness of the feasible distribution set, and continuity of the rate-mapping function.The cardinality bound makes the relevant simplex compact, while continuity transfers compactness to the rate region.
  • Soft covering: The generalized soft-covering theorem bounds expected total variation between the desired output distribution and that induced by a randomly constructed deterministic encoder.The encoder codebook is sampled independently according to ΦU|W, while the desired output uses the corresponding stochastic encoder.
  • Soft covering: For sequences of sources and channels, soft covering succeeds when the information-density condition tends to negative infinity, yielding vanishing expected total variation.The result specializes to sequence-of-channels soft covering and gives lim n→∞ E∥PV(n)−QV(n)∥TV = 0.

B. Implications of Soft Covering

Soft covering yields several channel-synthesis constructions, including local synthesis, source-assisted synthesis, and superposition coding. These constructions provide sufficient rate conditions, often with uniform or exponential convergence, and many rates are tight up to a null space.

  • Rate tightness: Most corollary rate requirements are tight up to a null space in the channel transition matrix.This tightness is obtained through entropy arguments.
  • Source-assisted synthesis: Source entropy can replace required random-index rate: Corollary VII.7 uses R + rH(W) > I(U; V) to produce an i.i.d. output.The construction combines an i.i.d. source with a uniformly distributed random index at rate R.
  • Local Channel Synthesis: Local channel synthesis requires R > I(U; V |W) + γn for accurate conditional synthesis uniformly over source sequences with the appropriate empirical distribution.Here γn must be in ω(1/√n), and the expected total variation tends uniformly to zero.
  • Local Channel Synthesis: With constant γ > 0, the local-synthesis error can be chosen to vanish exponentially fast.The stronger conditional guarantee holds for every qualifying sequence rather than only on average over an i.i.d. source.
  • Superposition Encoding: Superposition synthesis is sufficient when R1 > I(W; V), R2 > I(W, U; V) − H(W), and R1 + R2 > I(W, U; V).Two independently generated codebooks are cascaded through a memoryless channel, with convergence occurring exponentially quickly.

C. Proof of Theorem VII.1

The proof of Theorem VII.1 separates typical and atypical contributions using a tailored information-density set, then controls the typical contribution through Jensen’s inequality and variance analysis.

  • Typical-set decomposition: The proof defines a typical set Aτ and separates the induced output distribution into typical and atypical parts.The typical set is intended to contain most of the probability mass.
  • Typical-set decomposition: Jensen’s inequality converts the absolute-value analysis into a second-moment bound that enables variance control for the typical contribution.This is the key step used to analyze the total variation term associated with typical triples.
  • Specialization: The general proof specializes to channel resolvability by taking W independent of U and using a channel that depends only on U.Under these substitutions, the theorem directly yields the relevant form of Corollary VII.2.
  • General distributions: The argument is stated for discrete variables but extends to general random variables through Radon–Nikodym derivatives.The extension requires care when defining and comparing information-density quantities involving infinite values.

2) Proof:

The proof establishes soft-covering bounds by comparing the induced and desired output distributions and then derives exponential decay rates for memoryless extensions. Under HΦ(W) > IΦ(W, U; V), the expected total variation error decays exponentially.

  • Proof: Random codebook construction makes the deterministic encoder’s induced output distribution unbiased relative to the desired output distribution.Linearity of expectation and insertion of the codebook distribution establish this property.
  • Proof: The total variation error is split into typical and atypical contributions, with the typical term controlled by variance and the atypical term by probability bounds.The decomposition uses the triangle inequality before applying separate estimates.
  • Exponents of Total Variation: For memoryless sources and channels, HΦ(W) > IΦ(W, U; V) guarantees exponentially fast decay of expected total variation error.The memoryless specialization supplies the condition under which the derived exponent is positive.
  • Exponents of Total Variation: The basic digital-rate soft-covering lemma is recovered by substituting ΦW = 2−R, ΦU|W = ΦU, and ΦV|W,U = ΦV|U.This substitution yields a new achievable exponent for channel resolvability.
  • Exponents of Total Variation: The relaxed exponent associated with β′ = 1 removes the second term of the bound but is suboptimal.When R − IΦ(U; V) is small, the alternative exponents are approximately equal; for larger gaps, optimizing parameters can become extreme.

VIII. SUMMARY

The paper characterizes distributed channel synthesis through an achievable rate region and extends its proof techniques to broader input sequences, secrecy, applications, and soft covering.

  • Theorem II.1 gives a complete information-theoretic description of the achievable communication and common-randomness rate region.Common randomness independent of the channel input can replace part of the communication required for synthesis.
  • Distributed channel synthesis requires unconventional codecs, including a stochastic decoder, to reproduce nearly i.i.d. channel input-output pairs.The synthesis objective is stronger than merely producing empirically correlated sequences.
  • Distributed channel synthesis is as efficient as local channel synthesis in the number of random bits required by the system.
  • The main result extends to arbitrary channel input sequences that need not be i.i.d. or known when the codec is designed.A stronger soft covering lemma makes the probability of exceeding a vanishing total-variation threshold decay doubly exponentially, enabling a union bound over input sequences.
  • The work develops applications to secrecy, game theory, and quantum measurements, while also deriving the likelihood encoder from a feasible joint distribution.It additionally generalizes soft covering and obtains improved channel-resolvability exponents.

APPENDIX

The appendix analyzes the symmetric binary erasure channel by reducing admissible conditional product distributions to three categories and develops related achievability and converse arguments.

  • A. Derivation for Erasure Channel Example of §II-F: For each U=u, the Markov property forces PX,Y|U=u to be a product distribution, and erasure-channel sparsity restricts it to three categories.The zero-probability events (X,Y)=(0,1) and (1,0) create this restriction.
  • A. Derivation for Erasure Channel Example of §II-F: Category A requires X=0 whenever Y=0 has positive probability, whereas Category B is the reverse condition for positive probability on Y=1.Category C is the remaining case, assigning zero probability to Y∈{0,1}.
  • A. Derivation for Erasure Channel Example of §II-F: At most one U value per category suffices, yielding |U|≤3 instead of the nominal bound |X||Y|+1=7.Symmetry then implies an optimal construction formed by concatenating two symmetric binary erasure channels.
  • III-B. Game Theory: In the game-theoretic converse, time sharing and the Markov chain X−(U,W)−Y show that achievable payoffs equal the convexification of G0.The achievability direction first synthesizes an i.i.d. channel output and then uses time sharing.
  • III-D. Limited Memory: Limited-memory statistical tests are satisfied simultaneously for all t because the relevant limits converge exponentially quickly in n.This establishes existence of a channel-synthesis code passing those tests for every time index.
  • III-E. Limited Local Randomness: With limited local randomness, achievability requires decoder-local randomness at rate RL>H(Y|U).The converse incorporates the decoder’s local randomness into the auxiliary variable used in the rate-region argument.

C. Comparison of Soft Covering Lemma to bound in [17]

This section compares soft covering bounds and proves a converse for channel resolvability and mean-resolvability of discrete memoryless channels.

  • C. Comparison of Soft Covering Lemma to bound in [17]: The alternative bound from [17] yields exponential total-variation decay for memoryless sources and channels, but with a smaller exponent than Lemma IV.1.The second and fourth terms dominate the bound in the relevant decomposition.
  • C. Comparison of Soft Covering Lemma to bound in [17]: A threshold-based split of the fourth term produces a simpler bound that is dominated by (106) in Corollary VII.2.
  • D. Mean-resolvability Converse for DMCs: Soft covering lemmas provide tight asymptotic rate requirements for producing accurate channel output distributions, defining channel resolvability.The same entropy-based method also gives a converse for mean-resolvability.
  • D. Mean-resolvability Converse for DMCs: The converse allows a nonuniform codebook index J provided its entropy satisfies H(J)≤nR.The output entropy is bounded using the index entropy and the conditional channel entropy.
  • D. Mean-resolvability Converse for DMCs: Continuity and total-variation closeness transfer output-distribution proximity to the corresponding input distributions and conditional entropy bounds.These steps lead to the rate lower bound R≥IΦ(U;V).
Loading 1208.4415v3…