Deviner une faible valeur d'entropie en plusieurs tentatives

Supposons qu'Alice ait une distribution sur un domaine fini (mais peut-être très grand), de telle sorte que l'entropie (Shannon) de soit délimitée par une constante arbitrairement petite . Alice tire une valeur de , puis demande à Bob (qui connaît ) de deviner .$\mu$$\mu$$\varepsilon$$x$$\mu$$\mu$$x$

Quelle est la probabilité de réussite de Bob? S'il n'a qu'une seule supposition, alors on peut limiter cette probabilité comme suit: l'entropie limite la min-entropie, donc il y a un élément qui a une probabilité d'au moins . Si Bob choisit cet élément comme estimation, sa probabilité de succès sera de .$2^{-\varepsilon}$$2^{-\varepsilon}$

Supposons maintenant que Bob soit autorisé à faire plusieurs suppositions, disons , et Bob gagne si l'une de ses suppositions est correcte. Existe-t-il un schéma de devinettes qui améliore la probabilité de réussite de Bob? En particulier, est-il possible de montrer que la probabilité de défaillance de Bob diminue exponentiellement avec$t$$t$ ?

Le meilleur pari de Bob est de deviner les valeurs avec la plus grande probabilité.$t$

Si vous êtes prêt à utiliser l'entropie Rényi à la place, la proposition 17 de Boztaş ' Entropies, Guessing and Cryptography indique que la probabilité d'erreur après devine est au plus 1 - 2 - H 2 ( μ ) ( 1 - log $t$ oùnest la taille du domaine. Certes, la dépendance à l'égard detest assez mauvaise, et Boztaş était peut-être concentré sur un régime différent de l'entropie.

Pour l'entropie de Shannon, vous pouvez essayer de résoudre le problème de la double optimisation: étant donné une probabilité de défaillance fixe , trouvez l'entropie maximale d'une telle distribution. En utilisant la convexité de - x log x , nous savons que la distribution μ a la forme a , b , … , b ; b , … , b , c , où a ≥ b ≥ c , a + ( t - 1 ) b = 1 - $\delta$$-x\log x$$\mu$$a,b,\ldots,b;b,\ldots,b,c$$a\geq b\geq c$$a+(t-1)b = 1-\delta$, et . Nous avonst-1+⌊$c = \delta-\lfloor\frac{\delta}{b}\rfloor b$valeurs qui obtiennent une probabilitéb. Conditionnement surs=⌊$t-1+\lfloor\frac{\delta}{b}\rfloor$$b$, nous pouvons essayer de trouverbqui minimise l'entropie. Pour la valeur correcte des, ce sera un point interne (auquel la dérivée disparaît). Je ne sais pas comment obtenir des estimations asymptotiques en utilisant cette approche.$s = \lfloor\frac{\delta}{b}\rfloor$$b$$s$

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

C'est en partie la raison pour laquelle les gens ont continué à examiner les entropies de Renyi.