Distributed Source Simulation With No Communication
share
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