Distributed Source Simulation With No Communication

06/17/2019
by   Tomer Berg, et al.
0

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences U^n and V^n respectively, drawn from a joint distribution p_UV^⊗ n, and wish to locally generate sequences X^n and Y^n respectively with a joint distribution that is close (in KL divergence) to p_XY^⊗ n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains X-U-V-Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both p_UV and p_XY are doubly symmetric binary sources with parameters p,q≤ 1/2 respectively. While it is trivial that in this case p≤ q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset