The price of uncertainty in communication

Mark Braverman, Brendan Juba

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. [5]. This problem generalizes the classical source coding problem in information theory, in which the receiver knows the source distribution exactly, that was first considered in Shannon's work [6]. 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 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. [5] 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 [3], 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 by presenting both a variant of the coding scheme of Juba et al. with an overhead of log α+log 1/ϵ+1 bits, and a lower bound that matches up to an additive O(log log α) bits. Our lower bounds are obtained by observing that a worst-case, one-way communication complexity problem can be embedded in the sources and priors that any any uncertain priors coding scheme must address.

Original languageEnglish (US)
Title of host publication2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages924-927
Number of pages4
ISBN (Electronic)9781509018239
DOIs
StatePublished - Apr 4 2016
Event53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 - Monticello, United States
Duration: Sep 29 2015Oct 2 2015

Publication series

Name2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015

Other

Other53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
CountryUnited States
CityMonticello
Period9/29/1510/2/15

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'The price of uncertainty in communication'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., & Juba, B. (2016). The price of uncertainty in communication. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 (pp. 924-927). [7447106] (2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ALLERTON.2015.7447106