article · IEEE Transactions on Information Theory · 2020
Distributed Source Simulation With No Communication
Tomer Berg, Ofer Shayevitz, Young-Han Kim, Lele Wang
Cited by 2Abstract and details only
Abstract
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$U^{n}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$V^{n}$ </tex-math></inline-formula> respectively, drawn from a joint distribution <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p_{UV}^ {\otimes n}$ </tex-math></inline-formula> , and wish to locally generate sequences <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X^{n}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y^{n}$ </tex-math></inline-formula> respectively with a joint distribution that is close (in KL divergence) to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p_{XY}^ {\otimes n}$ </tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$U$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$V$ </tex-math></inline-formula> is nonzero, and we conjecture that only scalar Markov chains <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X-U-V-Y$ </tex-math></inline-formula> can be simulated otherwise. Motivated by this conjecture, we further examine the case where both <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p_{UV}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p_{XY}$ </tex-math></inline-formula> are doubly symmetric binary sources with parameters <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p,q\leq 1/2$ </tex-math></inline-formula> respectively. While it is trivial that in this case <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p\leq q$ </tex-math></inline-formula> is both necessary and sufficient, we use Fourier analytic tools to show that when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> is close to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> then any successful simulation is close to being scalar in the total variation sense.
Cite this paper
Berg, T., Shayevitz, O., Kim, Y.-H., & Wang, L. (2020). Distributed Source Simulation With No Communication. IEEE Transactions on Information Theory, 67(2), 886–901. https://doi.org/10.1109/tit.2020.3034469
Berg, Tomer, et al. “Distributed Source Simulation With No Communication.” IEEE Transactions on Information Theory, vol. 67, no. 2, 2020, pp. 886–901, https://doi.org/10.1109/tit.2020.3034469.
Berg, Tomer, Ofer Shayevitz, Young-Han Kim, and Lele Wang. 2020. “Distributed Source Simulation With No Communication.” IEEE Transactions on Information Theory 67 (2): 886–901. https://doi.org/10.1109/tit.2020.3034469.
Berg, T. et al. (2020) ‘Distributed Source Simulation With No Communication’, IEEE Transactions on Information Theory, 67(2), pp. 886–901. Available at: https://doi.org/10.1109/tit.2020.3034469.
@article{berg2020distributed,
title = {{Distributed Source Simulation With No Communication}},
author = {Berg, Tomer and Shayevitz, Ofer and Kim, Young-Han and Wang, Lele},
journal = {IEEE Transactions on Information Theory},
volume = {67},
number = {2},
pages = {886--901},
year = {2020},
doi = {10.1109/tit.2020.3034469}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.