Редактировать:
Основываясь на комментарии ОП, один из способов понять разницу между догадками и энтропией Шеннона заключается в следующем:
Шеннон: Допустим, у нас есть случайная переменная для кодирования. Учитывая его распространение, можно использовать код Хаффмана или другую процедуру исходного кодирования, и ожидаемая длина кодовых слов в этом коде тесно связано с энтропией Шеннона случайной величины. Кодовое дерево Хаффмана описывает рекурсивный процесс, в котором произвольно сильный запросы могут быть сделаны из случайной величины. Например, можно спросить, для $X\in {1,\ldots,N\}$ вопрос
Является $X \leq N/3$?
и выберите левую ветвь дерева от корня, если ответ положительный. В случае с Хаффманом мы хотим свести дерево к минимуму, и хотя мы используем приятную процедуру «слияния» листьев снизу вверх, в конце концов, если вопрос стоит выше, то $Pr[X\leq N/3]\приблизительно 1/2.$ Мы разделяем влево/вправо в точке, которая уравновешивает вероятности двух поддеревьев.
догадки: В этом контексте запрос не может быть произвольно мощным обычно он атомарный. Я имею в виду, что при построении дерева нам разрешено задавать вопрос в форме
Является $Х=1$?
Например. Предполагая $Пр[Х=1]$ есть наибольшая атомарная вероятность вида $Пр[Х=х]$ куда
$x\in \{1,2,\ldots,N\}$ это лучший вопрос, чтобы свести к минимуму количество догадок. В этом случае у вас все еще будет дерево, но структура стоимости изменится, вы не можете исключить поддерево, если ответ Нет вы можете только исключить значение $Х=1.$ Это то, что приводит к Угадыванию энтропии или $H_{1/2}(X).$
Приложения, в которых это используется, включают атаки с угадыванием грубой силы. Вы не можете спросить Первая буква пароля A? вам нужно ввести полный пароль и либо войти, либо получить отказ. Вот почему вы не можете использовать атомарные вопросы и спрашивать о частях неизвестной строки.
Задний план:
Здесь было некоторое обсуждение энтропии угадывания (которая на самом деле является энтропией Реньи порядка 1/2) в приведенных ниже вопросах:
различия между энтропиями Шеннона и угадывания
безопасность аутентификации по паролю с учетом энтропии
Таким образом, если вас беспокоит среднее количество догадок для определения неизвестной случайной величины, вам следует использовать энтропию догадок, а не энтропию Шеннона, поскольку первая тесно связана с ожидаемым количеством догадок.
Энтропия Реньи порядка $\альфа$ определяется
$$
H _ {\ alpha} (X) = \ frac {1} {1- \ alpha} \ log \ left (\ sum_ {x} Pr (X = x) ^ {\ alpha} \ right)
$$
куда $\alpha \in [0,1) \cup (1,\infty).$ Он подчиняется
$$
\lim_{\alpha\rightarrow 1} H_{\alpha}(X)=H(X).
$$
Это было показано Джоном Плиамом (см. здесь ) что если $Х$ представляет собой дискретную случайную величину с $ млн $ точек в его поддержку $Н(Х)$ может быть близок к своему максимальному значению $\лог М$ в то время как вероятность оптимального угадателя, обнаружившего фактическое значение $Х$ в $к$ последовательных вопросов намного меньше, чем $2^{Н(Х)}=М.$
Причем не только ожидаемое количество догадок, но и произвольные моменты
числа догадок можно связать с энтропиями Реньи разного порядка.
Одним из результатов ожидания является то, что ожидаемое количество догадок для
определять
случайная величина $Х$ (для оптимальной последовательности угадывания)
ограничен сверху
$$2^{H_{1/2}(X)-1}$$
куда $H_{1/2}(X)$ обозначает энтропию Реньи порядка $\альфа=1/2$ и также называется угадывающей энтропией. Более того, он ограничен снизу (для всех угадывающих последовательностей)
$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \ приблизительно 2^{H_{1/2}(X)} / H_{max}(X)$ $
куда $H_{макс}(Х)$ максимальная энтропия $\лог М$ либо в Реньи
или дело Шеннона.
