PaperlayerView exact revision on arXiv

Source-linked AI summary

On Non-Interactive Simulation of Joint Distributions

Sudeep Kamath, Venkat Anantharam

arXiv:1505.00769v2cs.ITmath.IT

TL;DR

Whether a target joint distribution can be generated non-interactively from correlated samples remains difficult to characterize for general source and target distributions. This paper applies hypercontractivity to derive impossibility conditions, showing that ribbon inclusion captures all corresponding inequalities and can certify non-simulability when it fails.

  • Problem

    Characterizing non-interactive simulation feasibility for general source and target distributions remains difficult.

    Source: §I · pp. 2, 4

  • Method

    The paper uses hypercontractivity inequalities and source/target hypercontractivity ribbons to derive necessary conditions for non-interactive simulation.

    Source: C. Proving impossibility results for… · p. 9

  • Results

    The inclusion R(X; Y) ⊆ R(U; V) is equivalent to satisfying all corresponding inequalities, subsuming every choice of their function parameters.

    Source: C. Proving impossibility results for… · p. 9

  • Takeaways & Limitations

    Failure of ribbon inclusion certifies non-simulability, and comparing ribbon boundaries can avoid identifying a particular violated inequality.

    Source: C. Proving impossibility results for… · p. 10

Abstract

from arXiv · show

We consider the following non-interactive simulation problem: Alice and Bob observe sequences $X^n$ and $Y^n$ respectively where $\{(X_i, Y_i)\}_{i=1}^n$ are drawn i.i.d. from $P(x,y),$ and they output $U$ and $V$ respectively which is required to have a joint law that is close in total variation to a specified $Q(u,v).$ It is known that the maximal correlation of $U$ and $V$ must necessarily be no bigger than that of $X$ and $Y$ if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if $P(x,y)$ is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the $k$-agent version of this problem.

I. INTRODUCTION

The introduction frames non-interactive simulation as producing a target joint law from agents’ correlated i.i.d. observations, while noting that general feasibility remains hard to characterize. It motivates maximal correlation and hypercontractivity as tools for deriving impossibility bounds, with examples showing where the latter goes further.

I. INTRODUCTION

  • General feasibility is open for arbitrary source and target laws, so the paper focuses on outer bounds for target distributions achievable from i.i.d. correlated observations.The achievable set is the closure of output marginals satisfying U−X^k−Y^k−V for some k.Source: §I · pp. 2, 4

A. Example 1

  • For DSBS(α) sources and DSBS(β) targets with 0 ≤ α, β ≤ 1/2, simulation is possible if and only if α ≤ β.The maximal correlation comparison gives this condition, and a suitable noisy copy achieves simulation when it holds.Source: A. Example 1 · pp. 4–5

B. Example 2

  • For DSBS(α) sources, hypercontractivity yields stronger impossibility results than maximal correlation; more generally, the paper gives necessary and sufficient conditions on P(x,y) for this subsumption.Source: B. Example 2 · p. 5
  • The paper also characterizes a limiting hypercontractivity parameter as a KL strong data processing constant and gives k-agent examples where pairwise simulation is possible but triple simulation is not.The parameter characterization extends to reverse hypercontractivity.Source: B. Example 2 · p. 5

II. MAIN TOOLS: MAXIMAL CORRELATION AND HYPERCONTRACTIVITY

Maximal correlation gives a necessary bound on simulable outputs, while hypercontractivity describes additional constraints through a ribbon of norm-contraction parameters.

A. Maximal Correlation

  • Maximal correlation lies between 0 and 1, equals 0 exactly under independence, and equals 1 exactly when the pair has positive Gács-Körner common information.The latter condition is equivalent to the joint distribution being decomposable.Source: A. Maximal Correlation · p. 6
  • Simulation is possible only if the source maximal correlation is at least the target maximal correlation.Maximal correlation also tensorizes across independent pairs, obeys data processing, and is lower semi-continuous in total variation.Source: A. Maximal Correlation · p. 6

B. Hypercontractivity

  • The hypercontractivity ribbon comprises the (p, q) pairs for which conditional expectation contracts or reverse-contracts the corresponding norms.For 1 ≤ q ≤ p the norm inequality is contractive; for 1 ≥ q ≥ p it is reverse-contractive for nonnegative functions.Source: B. Hypercontractivity · p. 7
  • The ribbon pinches at (1, 1), and its geometric bound connects maximal correlation to a straight-line slope.For a doubly symmetric binary source, the ribbon is a wedge bounded by p = q and the maximal-correlation line.Source: B. Hypercontractivity · p. 7, Figure 4 · p. 7

1) Interpretation of hypercontractivity as Hölder-contractivity:

The paper recasts hypercontractivity as tightened Hölder inequalities and uses its ribbon to derive necessary conditions for non-interactive simulation. The ribbon formulation also organizes tests of these conditions and their computational use.

1) Interpretation of hypercontractivity as Hölder-contractivity:

  • For 1 ≤ q ≤ p, membership in the ribbon is equivalent to a tightened Hölder inequality; for 1 ≥ q ≥ p, it is equivalent to a tightened reverse Hölder inequality.The reverse inequality is for strictly positive-valued functions.Source: 1) Interpretation of… · p. 7

2) Duality between R(X; Y) and R(Y; X):

  • The ribbon boundary parameters are dual under exchanging X and Y: (p, q) belongs to R(X; Y) exactly when (q′, p′) belongs to R(Y; X).The slope parameter s_p characterizes the boundary, and for a doubly symmetric binary source s_p equals (1 − 2α)^2 for p ≠ 1.Source: 2) Duality between R(X; Y ) and R(Y ; X) · pp. 8–9

C. Proving impossibility results for non-interactive simulation using the hypercontractivity ribbon R(X; Y )

  • Simulation requires R(X; Y) ⊆ R(U; V), equivalently requiring all source Hölder-contractive inequalities to hold for the target.The collection of inequalities for arbitrary real and positive-valued weights is equivalent to ribbon inclusion.Source: 2) Duality between R(X; Y ) and R(Y ; X) · p. 8, C. Proving impossibility results for… · p. 9
  • A violation of either contractive or reverse-contracting inequalities for some weights rules out simulation; the ribbon test captures all such choices.The two regimes use arbitrary real weights for 1 ≤ q ≤ p and positive weights for 1 ≥ q ≥ p.Source: C. Proving impossibility results for… · p. 9
  • For a DSBS(α) source, choosing λ0 = μ0 = 1 and λ1 = μ1 = ϵ as ϵ → 0 recovers inequality (2) for binary U and V.The source is (−2α/(1−2α), 2α)-hypercontractive in the cited construction.Source: C. Proving impossibility results for… · p. 9
  • The ribbon-boundary approach reduces a search for impossibility to finding p with s_p(X; Y) < s_p(U; V), without identifying a specific violated inequality.The authors know of no algorithm better than brute-force search after suitable discretization for computing the ribbons.Source: C. Proving impossibility results for… · p. 10

III. MAIN RESULTS

The section states and proves the paper's main results.

III. MAIN RESULTS

  • This section states and proves the paper's main results.Source: §III · p. 10

A. Connection between maximal correlation and the hypercontractivity ribbon

The paper relates maximal correlation geometrically to the hypercontractivity ribbon and derives a condition under which ribbon-based impossibility tests are at least as strong as maximal-correlation tests. The connection is established with a perturbative argument.

A. Connection between maximal correlation and the hypercontractivity ribbon

  • For a DSBS source, the hypercontractivity ribbon is bounded by a straight line whose slope is the square of maximal correlation.The ribbon is the wedge formed by p = q and the line corresponding to the maximal-correlation bound.Source: A. Connection between maximal… · p. 10
  • Theorem 1 is proved by perturbing positive functions around one, using zero-mean, unit-variance functions of the source variables.The argument assumes nonconstant variables and uses sufficiently small perturbations.Source: A. Connection between maximal… · p. 10
  • For sources satisfying the stated condition, including DSBS sources, hypercontractivity-based impossibility tests are at least as strong as maximal-correlation tests.The condition is characterized through the source and target hypercontractivity ribbons.Source: A. Connection between maximal… · p. 11
  • Corollary 1 characterizes when source-ribbon containment in a target ribbon implies that source maximal correlation is at least the target maximal correlation.The passage states this implication as one side of an equivalence for the source distribution.Source: A. Connection between maximal… · p. 11

B. Limiting chordal slope of the hypercontractivity ribbon

The paper relates limiting slopes of the hypercontractivity ribbon to strong data processing constants for relative entropy. It also gives applications of these results to source conditions and simulation examples.

B. Limiting chordal slope of the hypercontractivity ribbon

  • The limit of s_p(X;Y) as p approaches 1 exists and is characterized using a strong data processing constant for relative entropies.The constant is defined through a supremum of relative-entropy ratios over input distributions distinct from, and absolutely continuous with respect to, the source marginal.Source: B. Limiting chordal slope of the… · p. 11
  • The strong data processing constant s* is also described as the tightest constant for data processing inequalities involving mutual information in Markov chains.The passage presents this as a result of a recent work.Source: B. Limiting chordal slope of the… · p. 12
  • As p tends to either positive or negative infinity, s_p(X;Y) converges to s*(X;Y); the negative-infinity limit is identified as new.The positive-infinity limit had been established in.Source: B. Limiting chordal slope of the… · p. 12
  • DSBS sources satisfy the stated sufficient condition, which also holds for source distributions from a uniform input into a binary input symmetric output channel.The paper suggests hypercontractivity may be more useful than maximal correlation for a Boolean-functions conjecture, citing evidence in.Source: B. Limiting chordal slope of the… · p. 12

IV. NON-INTERACTIVE SIMULATION WITH k ≥3 AGENTS

For k agents, the paper extends hypercontractivity-based impossibility tests using Hölder contraction regions. Simulation requires containment of the source regions in the corresponding target regions across collections of nonempty subsets.

IV. NON-INTERACTIVE SIMULATION WITH k ≥3 AGENTS

  • The k-agent setup uses independent private randomness and requires the simulated joint law to approach the target in total variation.The agents apply functions to their own source sequences and independent random seeds.Source: §IV · p. 12
  • The k-variable Hölder contraction region uses forward inequalities for exponents at least one and reverse inequalities for exponents at most one.The reverse inequalities apply to positive-valued functions; the exponent orthants are stated as without loss of generality.Source: §IV · p. 14
  • Simulation among k agents requires H(X_S1; …; X_Sm) to be contained in H(U_S1; …; U_Sm) for every collection of nonempty agent subsets.This is the necessary condition in Observation 3.Source: §IV · p. 14
  • A separate necessary condition requires source maximal correlation to dominate target maximal correlation for every pair of nonempty agent subsets.Observation 4 applies the comparison to all nonempty subsets S1 and S2.Source: §IV · p. 14
  • A DSBS triple is specified by three pairwise crossover parameters satisfying triangle inequalities.The passage states that the triple distribution exists when those inequalities hold.Source: §IV · pp. 14–15

Y Z ✏X

A three-agent construction shows that pairwise simulability need not extend to the joint target. Numerical hypercontractivity tests certify the obstruction beyond what the source’s maximal-correlation comparison captures.

Y Z ✏X

  • Every agent pair can simulate its desired marginal, yet the three agents cannot simulate the target triple.The example also rules out simulation after Alice and Charlie pool their observations and tasks, because the resulting maximal correlation is below the target’s.Source: Y Z ✏X · pp. 15–17
  • The DSBS triple is supported on the four binary sequences satisfying X ⊕ Y ⊕ Z = 0.Here ⊕ denotes addition modulo 2.Source: Y Z ✏X · p. 16
  • For p = 1.95 the ratio is at most 1, while for p = 1.85 it reaches 1.0088 at f = g = −1, placing the source’s hypercontractive threshold between them.The source threshold is reported as κ = 1.93....Source: Y Z ✏X · p. 17

A. Proof of the claimed properties of ρm

The proof establishes three properties of maximal correlation used in the paper: data processing, tensorization over independent pairs, and lower semi-continuity under total-variation convergence.

A. Proof of the claimed properties of ρm

B. Proof of the claimed properties of sp

The proof establishes data processing, tensorization, and lower semi-continuity for the hypercontractivity parameter s_p, while noting that continuity can fail.

B. Proof of the claimed properties of sp

C. Limiting properties of sp: Proofs of Thm. 2 and Corollary 2

The proof identifies the limiting hypercontractivity parameters with a divergence-based supremum. It also establishes a first-order approximation for norms of bounded, normalized random variables.

Lemma 1

Proof of Theorem 2

  • The proof uses this norm estimate to compare conditional and unconditional norms, establishing the limiting threshold from both sides.For m below s, it obtains a strict inequality for sufficiently small τ; for m above s, it establishes a positive neighborhood of admissible τ values.Source: C. Limiting properties of sp: Proofs… · pp. 22–23
  • The forward and reverse hypercontractivity limits as p approaches 1 equal s*(Y; X), defined as the supremum of Ent(E[g(Y)|X])/Ent(g(Y)) over nonconstant nonnegative g.The proof identifies this supremum with s*(Y; X) using a divergence representation.Source: C. Limiting properties of sp: Proofs… · pp. 22–23
Loading 1505.00769v2…