Allerton 2015 Paper Abstract

Close

Paper ThA6.5

Beirami, Ahmad (Duke University & MIT), Calderbank, A. Robert (Duke University), Christiansen, Mark (National University of Ireland,Maynooth), Duffy, Ken (Hamilton Institute, National University of Ireland,Maynooth), Makhdoumi, Ali (MIT), Médard, Muriel (MIT)

A Geometric Perspective on Guesswork

Scheduled for presentation during the Regular Session "Information Theory and Source Coding" (ThA6), Thursday, October 1, 2015, 09:50−10:10, Visitor Center

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on November 19, 2019

Keywords Information Theory, Security and Trust, Performance Analysis

Abstract

Guesswork is the order 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 a tilt operation on probability distributions, and show that the family of finite-alphabet i.i.d. distributions parametrized by the tilt operation belongs to the exponential family, which we call the tilted family of the distribution. 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 larger 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. We also derive precise asymptotic expansions of the moments of guesswork. These results also recover the average codeword length of one-to-one compression as a special case.

 

 

All Content © PaperCept, Inc..


This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2019 PaperCept, Inc.
Page generated 2019-11-19  13:11:22 PST  Terms of use