A geometric perspective on guesswork
Conference Paper
Guesswork is the position at which a random string drawn from a given probability distribution appears in the list of strings ordered from the most likely to the least likely. We define the tilt operation on probability distributions and show that it parametrizes an exponential family of distributions, which we refer to as the tilted family of the source. We prove that two sources result in the same guesswork, i.e., the same ordering from most likely to least likely on all strings, if and only if they belong to the same tilted family. We also prove that the strings whose guesswork is smaller than a given string are concentrated on the tilted family. Applying Laplace's method, we derive precise approximations on the distribution of guesswork on i.i.d. sources. The simulations show a good match between the approximations and the actual guesswork for i.i.d. sources.
Full Text
Duke Authors
Cited Authors
- Beirami, A; Calderbank, R; Christiansen, M; Duffy, K; Makhdoumi, A; Medard, M
Published Date
- April 4, 2016
Published In
- 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
Start / End Page
- 941 - 948
International Standard Book Number 13 (ISBN-13)
- 9781509018239
Digital Object Identifier (DOI)
- 10.1109/ALLERTON.2015.7447109
Citation Source
- Scopus