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

9

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

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

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

Или меир
источник

Ответы:

10

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

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

12H2(μ)(1logtlogn)ln2(1logtlogn)H2(μ),
nt

Для энтропии Шеннона вы можете попытаться решить проблему двойной оптимизации: с учетом фиксированной вероятности отказа найдите максимальную энтропию такого распределения. Используя выпуклость , мы знаем, что распределение имеет вид , где , и . У нас есть значения, которые получают вероятность . Обусловливая , мы можем попытаться найтиδxlogxμa,b,,b;b,,b,cabca+(t1)b=1δc=δδbbt1+δbbs=δbbчто сводит к минимуму энтропию. Для правильного значения это будет внутренняя точка (в которой производная исчезает). Я не уверен, как получить асимптотические оценки, используя этот подход.s

Юваль Фильмус
источник
Спасибо за ответ! Я попробовал подход оптимизации, который вы предлагаете, но не смог получить хорошие оценки.
Или Меир
Привет Юваль, после некоторой дополнительной работы, кажется, что этот подход к оптимизации дает решение. К сожалению, и в этом случае погрешность уменьшается только обратно-логарифмически в количестве догадок. Спасибо!
Или Меир
7

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

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

kodlu
источник