Beirami, Ahmad and Calderbank, Robert and Christiansen, Mark M. and Duffy, Ken R. and Makhdoumi, Ali and Medard, Muriel
(2015)
A Geometric Perspective on Guesswork.
In: 53rd Annual Allerton Conference on Communication, Control, and Computing, 30 September - 2 October 2015, Monticello, IL.
Abstract
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.
| Item Type: |
Conference or Workshop Item
(Paper)
|
| Keywords: |
Ordering; Guesswork; One-to-One Codes;
Renyi Entropy; Laplace’s Method; |
| Academic Unit: |
Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: |
6762 |
| Depositing User: |
Dr Ken Duffy
|
| Date Deposited: |
11 Jan 2016 16:42 |
| 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