## A geometric perspective on guesswork

Publication ,  Conference
Beirami, A; Calderbank, R; Christiansen, M; Duffy, K; Makhdoumi, A; Medard, M
Published in: 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015
April 4, 2016

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.

## Published In

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

April 4, 2016

## Start / End Page

941 / 948

### Citation

APA
Chicago
ICMJE
MLA
NLM
Beirami, A., Calderbank, R., Christiansen, M., Duffy, K., Makhdoumi, A., & Medard, M. (2016). A geometric perspective on guesswork. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015 (pp. 941–948). https://doi.org/10.1109/ALLERTON.2015.7447109
Beirami, A., R. Calderbank, M. Christiansen, K. Duffy, A. Makhdoumi, and M. Medard. “A geometric perspective on guesswork.” In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015, 941–48, 2016. https://doi.org/10.1109/ALLERTON.2015.7447109.
Beirami A, Calderbank R, Christiansen M, Duffy K, Makhdoumi A, Medard M. A geometric perspective on guesswork. In: 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015. 2016. p. 941–8.
Beirami, A., et al. “A geometric perspective on guesswork.” 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015, 2016, pp. 941–48. Scopus, doi:10.1109/ALLERTON.2015.7447109.
Beirami A, Calderbank R, Christiansen M, Duffy K, Makhdoumi A, Medard M. A geometric perspective on guesswork. 2015 53rd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2015. 2016. p. 941–948.

## Published In

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

April 4, 2016

941 / 948