Adivinando un bajo valor de entropía en múltiples intentos

9

Supongamos que Alice tiene una distribución sobre un dominio finito (pero posiblemente muy grande), de modo que la entropía (Shannon) de está limitada por una constante arbitrariamente pequeña . Alice extrae un valor de , y luego le pide a Bob (quién sabe ) que adivine . $\mu$ $\mu$ $\varepsilon$ $x$ $\mu$ $\mu$ $x$

¿Cuál es la probabilidad de éxito de Bob? Si solo se le permite una conjetura, entonces se puede reducir esta probabilidad de la siguiente manera: la entropía limita más que la entropía mínima, por lo que hay un elemento que tiene una probabilidad de al menos . Si Bob elige este elemento como su suposición, su probabilidad de éxito será . $2^{-\varepsilon}$ $2^{-\varepsilon}$

Ahora, suponga que Bob tiene permitido hacer múltiples conjeturas, decir conjeturas, y Bob gana si una de sus conjeturas es correcta. ¿Existe un esquema de adivinanzas que mejore la probabilidad de éxito de Bob? En particular, ¿es posible demostrar que la probabilidad de falla de Bob disminuye exponencialmente con ? $t$ $t$

it.information-theory pr.probability O meir
fuente

10

La mejor apuesta de Bob es adivinar los valores con mayor probabilidad. $t$

Si está dispuesto a utilizar la entropía de Rényi en su lugar, la Proposición 17 en Entropías , adivinanzas y criptografía de Boztaş establece que la probabilidad de error después de adivina es como máximo $t$ dondees el tamaño del dominio. De acuerdo, la dependencia dees bastante mala, y tal vez Boztaş se centró en un régimen diferente de la entropía.

1 - 2^{- H_{2} (μ) (1 - \frac{\log t}{\log n})} \approx \ln 2 (1 - \frac{\log t}{\log n}) H_{2} (μ),

$1 - 2^{-H_2(\mu)\left(1-\frac{\log t}{\log n}\right)} \approx \ln 2 \left(1-\frac{\log t}{\log n}\right) H_2(\mu),$

n

$n$

t

$t$

Para la entropía de Shannon, puede intentar resolver el problema de la optimización dual: dada una probabilidad de falla fija , encuentre la entropía máxima de dicha distribución. Usando la convexidad de , sabemos que la distribución tiene la forma , donde , $\delta$ $-x\log x$ $\mu$ $a,b,\ldots,b;b,\ldots,b,c$ $a\geq b\geq c$ $a+(t-1)b = 1-\delta$ y . Tenemos $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$ valores que obtienen probabilidad. Condicionamiento en $t-1+\lfloor\frac{\delta}{b}\rfloor$ $b$ , podemos intentar encontrarque minimice la entropía. Para el valor correcto de, este será un punto interno (en el que la derivada desaparece). No estoy seguro de cómo obtener estimaciones asintóticas utilizando este enfoque. $s = \lfloor\frac{\delta}{b}\rfloor$ $b$ $s$

Yuval Filmus
fuente

¡Gracias por la respuesta! Probé el enfoque de optimización que sugiere, pero no pude obtener buenas estimaciones.

O Meir el

Hola Yuval, después de un poco más de trabajo, parece que este enfoque de optimización proporciona la solución. Desafortunadamente, en este caso también, el error disminuye solo logarítmicamente inverso en el número de conjeturas. ¡Gracias!

O Meir el

7

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

Esta es parte de la razón por la cual la gente pasó a examinar las entropías de Renyi.

kodlu
fuente

Adivinando un bajo valor de entropía en múltiples intentos

Respuestas: