Beirami, Ahmad and Calderbank, Robert and Christiansen, Mark M. and Duffy, Ken R. and Medard, Muriel
(2018)
A Characterization of Guesswork on Swiftly Tilting Curves.
IEEE Transactions on Information Theory, 65 (5).
pp. 2850-2871.
ISSN 0018-9448
Abstract
Given a collection of strings, each with an associated probability of occurrence, the guesswork of each of them is their
position in a list ordered from most likely to least likely, breaking ties arbitrarily. Guesswork is central to several applications
in information theory: Average guesswork provides a lower bound on the expected computational cost of a sequential decoder
to decode successfully the transmitted message; the complementary cumulative distribution function of guesswork gives the error
probability in list decoding; the logarithm of guesswork is the number of bits needed in optimal lossless one-to-one source coding;
and guesswork is the number of trials required of an adversary to breach a password protected system in a brute-force attack. In
this paper, we consider memoryless string-sources that generate strings consisting of i.i.d. characters drawn from a finite alphabet,
and characterize their corresponding guesswork. Our main tool is the tilt operation on a memoryless string-source. We show that
the tilt operation on a memoryless string-source parametrizes an exponential family of memoryless string-sources, which we refer
to as the tilted family of the string-source. We provide an operational meaning to the tilted families by proving that two memoryless
string-sources result in the same guesswork on all strings of all lengths if and only if their respective categorical distributions
belong to the same tilted family. Establishing some general properties of the tilt operation, we generalize the notions of weakly
typical set and asymptotic equipartition property to tilted weakly typical sets of different orders. We use this new definition to
characterize the large deviations for all atypical strings and characterize the volume of weakly typical sets of different orders. We
subsequently build on this characterization to prove large deviation bounds on guesswork and provide an accurate approximation
of its probability mass function.
| Item Type: |
Article
|
| Additional Information: |
This is the preprint version of the published article, which is available at A. Beirami, R. Calderbank, M. M. Christiansen, K. R. Duffy and M. Médard, "A Characterization of Guesswork on Swiftly Tilting Curves," in IEEE Transactions on Information Theory, vol. 65, no. 5, pp. 2850-2871, May 2019, doi: 10.1109/TIT.2018.2879477. Cite this version as arXiv:1801.09021 [cs.IT] |
| Keywords: |
Tilting; Ordering; Guesswork; One-to-One Codes; Renyi Entropy; Information Geometry; Weakly Typical Set; |
| Academic Unit: |
Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: |
13477 |
| Identification Number: |
https://doi.org/10.1109/TIT.2018.2879477 |
| Depositing User: |
Dr Ken Duffy
|
| Date Deposited: |
03 Nov 2020 15:20 |
| Journal or Publication Title: |
IEEE Transactions on Information Theory |
| Publisher: |
IEEE |
| Refereed: |
Yes |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric