MURAL - Maynooth University Research Archive Library



    A Geometric Perspective on Guesswork


    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.

    [img]
    Preview
    Download (573kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year