Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#326888] of Robert Calderbank

Papers Published

  1. 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 (April, 2016), pp. 941-948, ISBN 9781509018239 [doi]
    (last updated on 2018/12/10)

    © 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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320