Source Coding for Synthesizing Correlated Randomness

摘要

We consider a scenario wherein two parties Alice and Bob are provided $X_{1}^{n}$ and $X_{2}^{n}$ – samples that are IID from a PMF $P_{X_{1} X_{2}}$ . Alice and Bob can communicate to Charlie over (noiseless) communication links of rates $R_{1}$ and $R_{2}$ , respectively. Their goal is to enable Charlie generate samples $Y^{n}$ such that the triple $(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to $prod P_{X_{1} X_{2} Y}$ , enabling the three parties achieve strong coordination. In addition, the three parties may posses pairwise shared common randomness at rates $C_{1}$ and $C_{2}$ . We address the problem of characterizing the set of rate quadruples $(R_{1},R_{2},C_{1},C_{2})$ for which the above goal can be accomplished. We propose a new coding scheme based on random algebraic codes–coset codes in particular–of asymptotically large block-length. We analyze its performance and derive a single-letter information-theoretic inner bound. This bound subsumes the largest known inner bound and improves upon it strictly for identified examples. Our findings build on a variant of soft-covering which generalizes its applicability to the algebraic code ensembles. In addition, we provide an outer bound to the rate region for this three party distributed setup.