A geometric perspective on guesswork

Published

Conference Paper

© 2015 IEEE. 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