Worst-case Asymmetric Distributed Source Coding

We consider a worst-case asymmetric distributed source coding problem where an information sink communicates with $N$ correlated information sources to gather their data. A data-vector $\bar{x}=(x_1,\mathrm{.}\mathrm{.}\mathrm{.},x_N)\sim \mathcal{P}$ is derived from a discrete and finite joint probability distribution ${\mathcal P} = p(x_1, …, x_N)$andcomponent$x_i$isrevealedtothe$i^{$\text{th}$}$source,$1 \le i \le N$. We consider an asymmetric communication scenario where only the sink is assumed to know distribution $\mathcal{P}$. We are interested in computing the minimum number of bits that the sources must send, in the worst-case, to enable the sink to losslessly learn any $\bar{x}$ revealed to the sources. We propose a novel information measure called information ambiguity to perform the worst-case information-theoretic analysis and prove its various properties. Then, we provide interactive communication protocols to solve the above problem in two different communication scenarios. We also investigate the role of block-coding in the worst-case analysis of distributed compression problem and prove that it offers almost no compression advantage compared to the scenarios where this problem is addressed, as in this paper, with only a single instance of data-vector.