Odgadywanie niskiej wartości entropii przy wielu próbach

Załóżmy, że Alice ma rozkład $\mu$ w skończonej (ale być może bardzo dużej) domenie, takiej jak entropia (Shannon) $\mu$ jest górny ograniczony dowolnie małą stałą $\varepsilon$. Alice rysuje wartość$x$ od $\mu$, a następnie pyta Boba (kto wie $\mu$) zgadywać $x$.

Jakie jest prawdopodobieństwo sukcesu dla Boba? Jeśli można mu tylko zgadywać, wówczas można obniżyć to prawdopodobieństwo w następujący sposób: górna entropia ogranicza min-entropię, więc istnieje element, który ma prawdopodobieństwo co najmniej$2^{-\varepsilon}$. Jeśli Bob wybierze ten element jako przypuszczenie, jego prawdopodobieństwo powodzenia będzie$2^{-\varepsilon}$.

Załóżmy, że Bob może na przykład zgadywać $t$zgaduje, a Bob wygrywa, jeśli jedno z jego domysłów jest prawidłowe. Czy istnieje schemat zgadywania, który zwiększa prawdopodobieństwo sukcesu Boba? W szczególności, czy można wykazać, że prawdopodobieństwo awarii Boba maleje wykładniczo wraz z$t$?

Najlepszym wyborem Boba jest odgadnięcie $t$ wartości z największym prawdopodobieństwem.

Jeśli zamiast tego chcesz użyć entropii Rényi, Propozycja 17 w Entropies, Guessing and Cryptography Boztaşa stwierdza, że ​​prawdopodobieństwo błędu po$t$ domysły są co najwyżej

$$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),$$ gdzie $n$to rozmiar domeny. To prawda, zależność od$t$ jest dość zły i być może Boztaş skupił się na innym reżimie entropii.

W przypadku entropii Shannona można spróbować rozwiązać problem podwójnej optymalizacji: biorąc pod uwagę ustalone prawdopodobieństwo awarii $\delta$, znajdź maksymalną entropię takiego rozkładu. Używając wypukłości$-x\log x$, wiemy, że dystrybucja $\mu$ ma formę $a,b,\ldots,b;b,\ldots,b,c$, gdzie $a\geq b\geq c$, $a+(t-1)b = 1-\delta$, i $c = \delta-\lfloor\frac{\delta}{b}\rfloor b$. Mamy$t-1+\lfloor\frac{\delta}{b}\rfloor$ wartości, które uzyskują prawdopodobieństwo $b$. Uwarunkowane na$s = \lfloor\frac{\delta}{b}\rfloor$, możemy spróbować znaleźć $b$co minimalizuje entropię. Dla prawidłowej wartości$s$, będzie to punkt wewnętrzny (w którym pochodna zniknie). Nie jestem pewien, jak uzyskać asymptotyczne szacunki przy użyciu tego podejścia.

Niestety nie ma dobrej odpowiedzi na twoje pytanie. John Pliam [praca doktorska, 2 artykuły z serii LNCS] jako pierwszy zauważył rozbieżność między entropią Shannona a oczekiwaną liczbą domysłów. Jego pracę dyplomową można łatwo znaleźć w Internecie. W sekcji 4.3, wybierając odpowiedni rozkład prawdopodobieństwa dla$X$ (zależne od arbitralnej dodatniej liczby całkowitej $N$), który pochodzi z podobnych do siebie drzewek huffmanów, pokazuje, że zgadując w malejącym porządku prawdopodobieństwa, trzeba zrobić więcej niż $N+H(X)$ zgaduje, zanim osiągnie prawdopodobieństwo sukcesu $1/2$.

Jest to jeden z powodów, dla których ludzie badali entropie Renyi.