MURAL - Maynooth University Research Archive Library



    A Geometric Perspective on Guesswork


    Beirami, Ahmad, Calderbank, Robert, Christiansen, Mark M., Duffy, Ken R., 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.

    [thumbnail of KD-Geometric-Perspective.pdf]
    Preview
    Text
    KD-Geometric-Perspective.pdf

    Download (573kB) | Preview

    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: https://mural.maynoothuniversity.ie/id/eprint/6762
    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
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads