Adivinhando um baixo valor de entropia em várias tentativas

Suponha que Alice tenha uma distribuição sobre um domínio finito (mas possivelmente muito grande), de modo que a entropia (Shannon) de μ seja superior limitada por uma constante arbitrariamente pequena ε . Alice desenha um valor x de μ e, em seguida, pede a Bob (que sabe μ ) que adivinhe x .$\mu$$\mu$$\varepsilon$$x$$\mu$$\mu$$x$

Qual é a probabilidade de sucesso de Bob? Se for permitido apenas um palpite, é possível diminuir o limite dessa probabilidade da seguinte forma: a entropia superior limita a min-entropia, para que exista um elemento com probabilidade de pelo menos . Se Bob escolher esse elemento como seu palpite, sua probabilidade de sucesso será de 2 - ε .$2^{-\varepsilon}$$2^{-\varepsilon}$

Agora, suponha que Bob está autorizado a fazer várias suposições, dizem suposições, e Bob ganha se uma de suas suposições é correta. Existe um esquema de adivinhação que melhora a probabilidade de sucesso de Bob? Em particular, é possível mostrar que a probabilidade de falha de Bob diminui exponencialmente com t ?$t$$t$

A melhor aposta de Bob é adivinhar os valores com maior probabilidade.$t$

$t$

$\delta$$-x\log x$$\mu$$a,b,\ldots,b;b,\ldots,b,c$$a\geq b\geq c$$a+(t-1)b = 1-\delta$$c = \delta-\lfloor\frac{\delta}{b}\rfloor b$$t-1+\lfloor\frac{\delta}{b}\rfloor$$b$$s = \lfloor\frac{\delta}{b}\rfloor$$b$$s$

$X$$N$$N+H(X)$$1/2$

Essa é parte da razão pela qual as pessoas examinaram as entropias de Renyi.