You have already added 0 works in your ORCID record related to the merged Research product.
You have already added 0 works in your ORCID record related to the merged Research product.
Distributed Source Simulation With No Communication
Distributed Source Simulation With No Communication
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}^ {\otimes 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}^ {\otimes 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 Gacs-Korner (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\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we use Fourier analytic tools to show that when $p$ is close to $q$ then any successful simulation is close to being scalar in the total variation sense.
- Tel Aviv University Israel
- University of British Columbia Canada
- University of California, San Diego United States
Microsoft Academic Graph classification: Physics Entropy (classical thermodynamics) Fourier transform symbols.namesake symbols Kullback–Leibler divergence Binary number Probability distribution Combinatorics Conjecture Joint probability distribution Scalar (mathematics)
Computer Science - Information Theory, Information Theory (cs.IT), FOS: Computer and information sciences, Library and Information Sciences, Computer Science Applications, Information Systems
Computer Science - Information Theory, Information Theory (cs.IT), FOS: Computer and information sciences, Library and Information Sciences, Computer Science Applications, Information Systems
Microsoft Academic Graph classification: Physics Entropy (classical thermodynamics) Fourier transform symbols.namesake symbols Kullback–Leibler divergence Binary number Probability distribution Combinatorics Conjecture Joint probability distribution Scalar (mathematics)
3514
[1] A. Wyner, “The common information of two dependent random variables,” IEEE Transactions on Information Theory, vol. 21, no. 2, pp. 163-179, 1975.
[2] P. G´acs and J. K¨orner, “Common information is far less than mutual information,” Problems of Control and Information Theory, vol. 2, no. 2, pp. 149-162, 1973.
[3] H. S. Witsenhausen, “On sequences of pairs of dependent random variables,” SIAM Journal on Applied Mathematics, vol. 28, no. 1, pp. 100-113, 1975.
[4] R. Frucht, “On the groups of repeated graphs,” Bulletin of the American Mathematical Society, vol. 55, no. 4, pp. 418-420, 1949. [OpenAIRE]
[5] R. Ahlswede and I. Csisza´r, “Common randomness in information theory and cryptography. i. secret sharing,” IEEE Transactions on Information Theory, vol. 39, no. 4, pp. 1121-1132, 1993. [OpenAIRE]
[6] P. W. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” IEEE Transactions on Information Theory, vol. 56, no. 9, pp. 4181-4206, 2010.
[7] T. M. Cover and H. H. Permuter, “Capacity of coordinated actions,” in Information Theory, 2007. ISIT 2007. IEEE International Symposium on. IEEE, 2007, pp. 2701-2705.
[8] M. Abroshan, A. Gohari, and S. Jaggi, “Zero error coordination,” in Information Theory Workshop-Fall (ITW), 2015 IEEE. IEEE, 2015, pp. 202-206.
[9] E. Soljanin, “Compressing quantum mixed-state sources by sending classical information,” IEEE Transactions on Information Theory, vol. 48, no. 8, pp. 2263-2275, 2002. [OpenAIRE]
[10] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse shannon theorem,” IEEE Transactions on Information Theory, vol. 48, no. 10, pp. 2637-2655, 2002.
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Popularity provided by BIP!
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Tel Aviv University Israel
- University of British Columbia Canada
- University of California, San Diego United States
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}^ {\otimes 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}^ {\otimes 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 Gacs-Korner (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\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we use Fourier analytic tools to show that when $p$ is close to $q$ then any successful simulation is close to being scalar in the total variation sense.