Math @ Duke

Publications [#326888] of Robert Calderbank
Papers Published
 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. 941948, ISBN 9781509018239 [doi]
(last updated on 2017/12/14)
Abstract: © 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

