Большинство из нас знакомы или, по крайней мере, слышали о энтропии Шеннона случайной величины, , и обо всех связанных с этим теоретико-информационных мерах, таких как относительная энтропия, взаимная информация и так далее. Есть несколько других мер энтропии, которые обычно используются в теоретической информатике и теории информации, такие как мин-энтропия случайной величины.
Я начал видеть эти так называемые энтропии Реньи чаще, когда просматриваю литературу. Они обобщают энтропию Шеннона и мин-энтропию и фактически предоставляют целый спектр энтропийных мер случайной величины. Я работаю в основном в области квантовой информации, где также часто рассматривается квантовая версия энтропии Реньи.
То, что я не понимаю, почему они полезны. Я слышал, что часто с ними аналитически легче работать, чем, скажем, с энтропией Шеннона / фон Неймана или мин-энтропией. Но они также могут быть связаны с энтропией / мин-энтропией Шеннона.
Может ли кто-нибудь привести примеры (классические или квантовые) того, когда использование энтропий Реньи является «правильным решением»? То, что я ищу, - это какой-то «умственный крючок» или «шаблон», позволяющий узнать, когда я захочу использовать энтропии Рени.
Благодарность!
Ответы:
Рассмотрим пытается сделать атомные догадки по неизвестной случайной величины , распределенной по некоторому конечному множеству A . В энтропии Шеннона предполагается, что вы можете выполнять запрос побитно, т. Е. Если A = { 1 , … , N }, вы можете спросить:X A. A={1,…,N}
Является ли ?X∈{1,…,N/2} (предположим, что четное или использовать функции пола / потолка)N
В криптографии и некоторых сценариях декодирования это нереально. Пытаясь угадать неизвестный пароль, вам нужно сделать атомарные запросы, т.е. запросить, если является конкретным значением.X
Оказывается , что ожидаемое число запросов угадать случайную величину , то плотно зависит от энтропии Реньи порядка 1 / 2. Так что некоторые высшие моменты. НапримерX 1/2.
а числитель является по существу логарифмом Рения энтропии порядка Можно также сделать Шеннон энтропия очень велик , а энтропия Реньи и ожидание числа догадок очень мало. Если вы полагаетесь на энтропию Шеннона для обеспечения безопасности, в этом случае у вас будут проблемы.1/2.
Также см. Соответствующий вопрос « Угадайте низкое значение энтропии при нескольких попытках».
Некоторые ссылки:
источник
Энтропия Реньи в некотором смысле аналогична -нормам, поэтому давайте сначала вспомним, почему эти нормы полезны.ℓp
Предположим, у нас есть вектор чисел . Мы хотим иметь одно число , которое представляет, в каком - то смысле, как делает типичный элемент в выглядеть.a∈Rn a
Один из способов сделать это - взять среднее число чисел в , что примерно соответствует норме ℓ 1 : E 1 ≤ i ≤a ℓ1 . Это часто бывает полезно, но для некоторых применений имеют следующие проблемы:первых, ℓ 1 норма не дает нам хорошую верхнюю границу на наибольшем элементе, потому что если есть один большой элемент и много нулей, то ℓ 1 норма будет значительно меньше, чем самый большой элемент. С другой стороны, ℓ 1E1≤i≤n[|ai|] ℓ1 a ℓ1 ℓ1 норма также не дает нам хорошей оценки того, насколько малы элементы , например, сколько нулей имеет a - эта проблема возникает точно в том же сценарии, что и раньше.a a
Конечно, когда элементы много дисперсии, например, в крайнем случае , как указано выше, ни один номер не может дать решить обе проблемы выше. У нас есть компромисс. Например, если мы хотим знать , самый большой элемент, мы можем использовать л ∞ норму, но тогда мы потеряем всю информацию о более мелких элементах. Если нам нужно количество нулей, мы можем посмотреть на норму ℓ 0 , которая является просто размером поддержки a .a ℓ∞ ℓ0 a
Теперь, причина для рассмотрения норм состоит в том, что они дают нам весь непрерывный компромисс между двумя крайностями. Если мы хотим получить больше информации о больших элементах, мы берем p, чтобы быть больше, и наоборот.ℓp p
То же самое относится и к Рению энтропии: энтропия Shanon является как норма - это говорит нам кой - что о «типичной» вероятность элемента, но ничего о дисперсии или крайностях. Мин-энтропия дает нам информацию об элементе с наибольшей вероятностью, но теряет всю информацию об остальном. Размер поддержки дает другую крайность. Энтропии Реньи дают нам непрерывный компромисс между двумя крайностями.ℓ1
Например, много раз энтропия Реньи-2 полезна, потому что она, с одной стороны, близка к энтропии Шенона и, таким образом, содержит информацию обо всех элементах распределения, а с другой стороны дает больше информации об элементах с наибольшим вероятность. В частности, известно, что границы энтропии Реньи-2 дают границы минимальной энтропии, см., Например, Приложение A здесь: http://people.seas.harvard.edu/~salil/research/conductors-prelim. .ps
источник
Энтропия Реньи (порядка 2) полезна в криптографии для анализа вероятности столкновений.
Эти факты полезны в криптографии, где коллизии могут иногда вызывать проблемы и включать атаки.
Для некоторого анализа других применений в криптографии я рекомендую следующую кандидатскую диссертацию:
Кристиан Качин. Меры энтропии и безусловная безопасность в криптографии . Докторская диссертация, ETH Zurich, май 1997.
источник
Этот другой ответ об обмене стеками и этот пост в блоге могут быть очень полезны, чтобы быстро понять основной пример,
/physics/73424/deriving-entanglement-entropy-from-renyi-entropy
https://johncarlosbaez.wordpress.com/2011/02/10/rnyi-entropy-and-free-energy/
Грубо говоря, энтропии Реньи знают о возбужденных состояниях квантовой системы, но энтропия запутанности знает об основных состояниях. ПРЕДУПРЕЖДЕНИЕ: эта интуиция может быть ужасно грубой, но может быть хорошим «умственным крючком»: я был бы ОЧЕНЬ рад узнать о лучшем и точном способе сказать это!
Всегда есть много вопросов о существовании и правильности, когда кто-то пытается сделать эти аналитические продолжения - но для кого-то вроде меня, воспитанного на ежедневной диете интегралов по путям Фейнмана, это очень распространенная проблема, и мы есть много инструментов для решения этих проблем. Три хороших документа для изучения этих вопросов: http://arxiv.org/pdf/1306.5242.pdf , http://arxiv.org/pdf/1402.5396.pdf , http://arxiv.org/pdf/1303.7221. .pdf (последняя из этих статей может быть более легкой отправной точкой). Эта презентация также может помочь, https://www.icts.res.in/media/uploads/Talk/Document/Tadashi_Takayanagi.pdf.
То, что энтропия Реньи говорит в терминах квантовой теории сложности, может быть волнующим вопросом! Можно ли считать индекс Реньи параметризацией иерархии классов сложности? Это должно быть весело, если правда! Дай мне знать :)
источник
Энтропия Реньи нашла свой путь в определения количественного информационного потока , области или исследования безопасности. См . Обзорную статью Дж. Смита .
источник