Угадай низкую величину энтропии при нескольких попытках

Предположим, Алиса имеет распределение $\mu$над конечной (но, возможно, очень большой) областью, такой, что энтропия (Шеннона) ограничена сверху произвольно малой постоянной . Алиса получает значение из , а затем просит Боба (который знает ) угадать .$\mu$$\varepsilon$$x$$\mu$$\mu$$x$

Какова вероятность успеха для Боба? Если ему разрешено только одно предположение, то эту вероятность можно понизить следующим образом: верх энтропии ограничивает мин-энтропию, поэтому существует элемент с вероятностью не менее . Если Боб выберет этот элемент в качестве своей догадки, вероятность его успеха будет .$2^{-\varepsilon}$$2^{-\varepsilon}$

Теперь предположим, что Бобу разрешено делать несколько догадок, скажем , и Боб выигрывает, если одна из его догадок верна. Существует ли схема угадывания, которая повышает вероятность успеха Боба? В частности, возможно ли показать, что вероятность отказа Боба уменьшается экспоненциально с ?$t$$t$

Лучший выбор Боба - угадать значения с наибольшей вероятностью.$t$

Если вы готовы вместо этого использовать энтропию Реньи, в предложении 17 в «Энтропиях, догадках и криптографии» Бозташа говорится, что вероятность ошибки после угаданий составляет не более где - размер домена. Конечно, зависимость от довольно плохая, и, возможно, Бозташ сфокусировался на другом режиме энтропии.$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$

К сожалению, нет хорошего ответа на ваш вопрос. Джон Плиам [кандидатская диссертация, 2 статьи в серии LNCS] был первым, кто наблюдал несоответствие между энтропией Шеннона и ожидаемым количеством догадок. Его тезис легко найти в Интернете. В разделе 4.3, выбирая подходящее распределение вероятностей для (в зависимости от произвольного положительного целого числа ), которое исходит от самоподобных деревьев Хаффмана, он демонстрирует, что, угадывая в порядке убывания вероятности, нужно сделать больше, чем догадки до того, как вероятность успеха достигнет .$X$$N$$N+H(X)$$1/2$

Это одна из причин, почему люди продолжали изучать энтропии Реньи.