Dispersion of the discrete arbitrarily-varying channel with limited shared randomness

Oliver Kosut; Jörg Kliewer

doi:10.1109/ISIT.2017.8006727

Dispersion of the discrete arbitrarily-varying channel with limited shared randomness

Oliver Kosut, Jörg Kliewer

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

The second-order behavior of the discrete memoryless arbitrarily-varying channel is considered in the fixed error regime when the encoder and decoder share randomness that is independent from the adversarial choice of state. The dispersion (coefficient of the second-order term) is exactly characterized for most channels of interest when infinite shared randomness is allowed, and it is shown that precisely the same dispersion is achievable with only O (log n) bits of shared randomness. We also show that the dispersion is identical to that of the non-adversarial channel induced by the adversary simply choosing an i.i.d. state sequence according to the correct distribution. Further, we present some remarks on the connection to the compound channel, as well as on cost constraints for input and state sequences.

Original language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory, ISIT 2017
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1242-1246
Number of pages	5
ISBN (Electronic)	9781509040964
DOIs	https://doi.org/10.1109/ISIT.2017.8006727
State	Published - Aug 9 2017
Event	2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany Duration: Jun 25 2017 → Jun 30 2017

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Other

Other	2017 IEEE International Symposium on Information Theory, ISIT 2017
Country/Territory	Germany
City	Aachen
Period	6/25/17 → 6/30/17

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2017.8006727

Cite this

Kosut, O., & Kliewer, J. (2017). Dispersion of the discrete arbitrarily-varying channel with limited shared randomness. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 1242-1246). Article 8006727 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8006727

@inproceedings{2d4184494cb8401895864345e3bcb79f,

title = "Dispersion of the discrete arbitrarily-varying channel with limited shared randomness",

abstract = "The second-order behavior of the discrete memoryless arbitrarily-varying channel is considered in the fixed error regime when the encoder and decoder share randomness that is independent from the adversarial choice of state. The dispersion (coefficient of the second-order term) is exactly characterized for most channels of interest when infinite shared randomness is allowed, and it is shown that precisely the same dispersion is achievable with only O (log n) bits of shared randomness. We also show that the dispersion is identical to that of the non-adversarial channel induced by the adversary simply choosing an i.i.d. state sequence according to the correct distribution. Further, we present some remarks on the connection to the compound channel, as well as on cost constraints for input and state sequences.",

author = "Oliver Kosut and J{\"o}rg Kliewer",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Symposium on Information Theory, ISIT 2017 ; Conference date: 25-06-2017 Through 30-06-2017",

year = "2017",

month = aug,

day = "9",

doi = "10.1109/ISIT.2017.8006727",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1242--1246",

booktitle = "2017 IEEE International Symposium on Information Theory, ISIT 2017",

address = "United States",

}

Kosut, O & Kliewer, J 2017, Dispersion of the discrete arbitrarily-varying channel with limited shared randomness. in 2017 IEEE International Symposium on Information Theory, ISIT 2017., 8006727, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1242-1246, 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 6/25/17. https://doi.org/10.1109/ISIT.2017.8006727

Dispersion of the discrete arbitrarily-varying channel with limited shared randomness. / Kosut, Oliver; Kliewer, Jörg.
2017 IEEE International Symposium on Information Theory, ISIT 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 1242-1246 8006727 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Dispersion of the discrete arbitrarily-varying channel with limited shared randomness

AU - Kosut, Oliver

AU - Kliewer, Jörg

PY - 2017/8/9

Y1 - 2017/8/9

N2 - The second-order behavior of the discrete memoryless arbitrarily-varying channel is considered in the fixed error regime when the encoder and decoder share randomness that is independent from the adversarial choice of state. The dispersion (coefficient of the second-order term) is exactly characterized for most channels of interest when infinite shared randomness is allowed, and it is shown that precisely the same dispersion is achievable with only O (log n) bits of shared randomness. We also show that the dispersion is identical to that of the non-adversarial channel induced by the adversary simply choosing an i.i.d. state sequence according to the correct distribution. Further, we present some remarks on the connection to the compound channel, as well as on cost constraints for input and state sequences.

AB - The second-order behavior of the discrete memoryless arbitrarily-varying channel is considered in the fixed error regime when the encoder and decoder share randomness that is independent from the adversarial choice of state. The dispersion (coefficient of the second-order term) is exactly characterized for most channels of interest when infinite shared randomness is allowed, and it is shown that precisely the same dispersion is achievable with only O (log n) bits of shared randomness. We also show that the dispersion is identical to that of the non-adversarial channel induced by the adversary simply choosing an i.i.d. state sequence according to the correct distribution. Further, we present some remarks on the connection to the compound channel, as well as on cost constraints for input and state sequences.

UR - http://www.scopus.com/inward/record.url?scp=85034052412&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034052412&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2017.8006727

DO - 10.1109/ISIT.2017.8006727

M3 - Conference contribution

AN - SCOPUS:85034052412

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1242

EP - 1246

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017

Y2 - 25 June 2017 through 30 June 2017

ER -

Dispersion of the discrete arbitrarily-varying channel with limited shared randomness

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this