Guessing with a Bit of Help

Entropy

卷:22

Ofer Shayevitz¹  Nir Weinberger² 

[1] Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA;

[2] Institute for Data, Systems, and Society and Laboratory for Information &

关键词: boolean functions;    fourier analysis;    guessing moments;    guessing with a helper;    hypercontractivity;    maximum entropy;    strong data-processing inequalities;   

DOI  :  10.3390/e22010039

来源: DOAJ

【 摘 要 】

What is the value of just a few bits to a guesser? We study this problem in a setup where Alice wishes to guess an independent and identically distributed (i.i.d.) random vector and can procure a fixed number of k information bits from Bob, who has observed this vector through a memoryless channel. We are interested in the guessing ratio, which we define as the ratio of Alice’s guessing-moments with and without observing Bob’s bits. For the case of a uniform binary vector observed through a binary symmetric channel, we provide two upper bounds on the guessing ratio by analyzing the performance of the dictator (for general $k\ge 1$ ) and majority functions (for $k=1$ ). We further provide a lower bound via maximum entropy (for general $k\ge 1$ ) and a lower bound based on Fourier-analytic/hypercontractivity arguments (for $k=1$ ). We then extend our maximum entropy argument to give a lower bound on the guessing ratio for a general channel with a binary uniform input that is expressed using the strong data-processing inequality constant of the reverse channel. We compute this bound for the binary erasure channel and conjecture that greedy dictator functions achieve the optimal guessing ratio.

【 授权许可】

Unknown