Allerton 2015 Paper Abstract

Close

Paper ThA6.2

Braverman, Mark (Princeton University), Juba, Brendan (Washington University in St. Louis)

The Price of Uncertainty in Communication

Scheduled for presentation during the Regular Session "Information Theory and Source Coding" (ThA6), Thursday, October 1, 2015, 08:50−09:10, Visitor Center

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on November 19, 2019

Keywords Information Theory, Source Coding and Compression

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. This “uncertain priors” coding problem was intended to illuminate aspects of natural language communication, and has applications to adaptive compression schemes. We consider the question of how much longer the messages need to be in order to cope with the uncertainty that the sender and receiver have about the receiver’s prior and the source distribution, respectively, as compared to the usual source coding problem.

We obtain lower bounds for one-way communication using uncertain priors that are tight up to low-order terms. Specifically, we consider two variants of the uncertain priors problem. First, we consider the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1. We find that in this setting, the overhead of 2 log α+O(1) bits achieved by that scheme when the prior is α-close to the source is optimal up to an additive O(log log α) bits. We also consider a setting introduced in the work of Haramaty and Sudan, in which the receiver is permitted to fail to recover the message with some positive probability ε. In this setting, we find that the optimal overhead is essentially log α + log 1/ε bits.

 

 

All Content © PaperCept, Inc..


This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2019 PaperCept, Inc.
Page generated 2019-11-19  13:12:45 PST  Terms of use