The Price of Uncertain Priors in Source Coding

Mark Braverman, Brendan Juba

Abstract

In classical source coding, the sender and receiver are assumed to share a common distribution $P$ over the message space. This paper investigates the "price of uncertainty" when the receiver instead possesses a prior $Q$ that is only known to be $\alpha$-close to $P$. We analyze two primary settings: one requiring error-free recovery and another allowing a failure probability $\epsilon$. We establish that the redundancy required for error-free communication is approximately $2 \log \alpha$ bits, while the introduction of a small error tolerance $\epsilon$ reduces this overhead to approximately $\log \alpha + \log(1/\epsilon)$ bits. Our bounds are tight up to $O(\log \log \alpha)$ terms, settling the first-order costs of communication under uncertain priors.

Introduction

Information theory typically operates under the assumption of a perfectly shared context. When a sender (Alice) transmits a message to a receiver (Bob), both are assumed to know the underlying probability distribution $P$ of the source. This shared knowledge allows for optimal compression, where the average message length approaches the entropy $H(P)$.

However, in many real-world scenarios, Alice and Bob may have slightly different models of the world. This paper addresses the scenario where Bob’s prior $Q$ is an approximation of Alice’s source distribution $P$. We quantify the additional communication cost—the redundancy—necessitated by this discrepancy. We adopt the model of $\alpha$-closeness, defined by the condition: $$\frac{1}{\alpha} Q(m) \le P(m) \le \alpha Q(m)$$ for all messages $m$. The objective is to determine the minimum number of extra bits required beyond $H(P)$ to ensure Bob can decode Alice's message correctly.

Communication Settings

The research distinguishes between two fundamental communication requirements:

1. Error-Free Communication

In the original setting proposed by Juba et al., the receiver must be able to recover the message with probability 1. This is a stringent requirement, as the coding scheme must be robust against any distribution $P$ that satisfies the $\alpha$-closeness condition relative to $Q$.

2. Error-Tolerant Communication ($\epsilon$-error)

Introduced by Haramaty and Sudan, this setting allows for a small probability of failure $\epsilon$. If the message cannot be uniquely decoded within the allocated bit budget, the receiver is permitted to fail.

Methodology

The authors employ a combination of information theory and communication complexity. To establish lower bounds, they frame the problem as a one-way communication game. Alice receives a message, and Bob receives a set of possible distributions. Alice must send a bitstring such that Bob can identify the message. By applying Von Neumann’s Min-max Theorem to this zero-sum game, the authors demonstrate that no coding scheme can circumvent the calculated redundancy limits.

For upper bounds, the paper analyzes randomized coding schemes. These schemes assume Alice and Bob share an infinite random string (shared randomness). Alice transmits a prefix of this string that is unique to her message under the receiver's distribution $Q$.

Key Results and Insights

The paper provides a comprehensive characterization of the redundancy required in both settings:

  • Redundancy is Logarithmic: Crucially, the overhead depends on the uncertainty factor $\alpha$ rather than the size of the message universe. This suggests that communication is relatively robust to distribution mismatch.
  • The Cost of Perfection: For error-free communication, the redundancy must be at least $2 \log \alpha - O(\log \log \alpha)$. This matches the known upper bound of $2 \log \alpha + 2$. The "doubling" of the log-uncertainty occurs because the sender must ensure the message is unique across a wider range of potential distributions to guarantee zero error.
  • The Efficiency of Error Tolerance: By allowing a failure probability $\epsilon$, the redundancy drops to $\log \alpha + \log(1/\epsilon) + 1$. The lower bound for this setting is $\log \alpha + \log(1/\epsilon) - O(\log \log \alpha)$. This indicates that the "price of uncertainty" is essentially halved if the system can tolerate a small error rate.
  • Computational Asymmetry: Beyond bit-length, the error-tolerant scheme is computationally more efficient for the sender. In the error-free case, the sender must exhaustively check for potential collisions against all possible $\alpha$-close distributions, a significantly more complex task than the $\epsilon$-error encoding.

Discussion and Future Work

While this work provides nearly tight bounds, several avenues for future research remain. First, there is a small gap in the lower-order terms—specifically the $O(\log \log \alpha)$ factor—that remains to be closed. Second, the current decoding process can be computationally expensive, as the receiver may need to search through many candidate messages.

Furthermore, the study focuses on a single-shot communication event. In a multi-message scenario, a receiver could potentially learn the source distribution $P$ over time, eventually reducing the redundancy to zero. Determining the exact point where learning-based schemes outperform uncertain-prior schemes is an open question. Finally, the results presented here rely on shared randomness; deterministic schemes are expected to have significantly higher redundancy, potentially scaling with the size of the message space.

Conclusion

This paper settles the first-order redundancy costs for source coding with uncertain priors. By proving tight lower bounds for both error-free and error-tolerant settings, the authors demonstrate that the cost of distribution mismatch is logarithmic in the uncertainty, and that allowing a small error probability significantly improves communication efficiency.

Summary updated

Abstract

We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a "prior" distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receiver's prior and the source distribution, respectively, as compared to the standard source coding problem. We consider two variants of this uncertain priors problem: the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1, and a setting introduced by Haramaty and Sudan, in which the receiver is permitted to fail with some probability $\epsilon$. In both settings, we obtain lower bounds that are tight up to logarithmically smaller terms. In the latter setting, we furthermore present a variant of the coding scheme of Juba et al. with an overhead of $\log\alpha+\log 1/\epsilon+1$ bits, thus also establishing the nearly tight upper bound.
BibTeX
@article{braverman2019price,
  author = {Mark Braverman and Brendan Juba},
  title = {{The Price of Uncertain Priors in Source Coding}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=TMl30X7iwc7},
}

Loading related content...

Figure