М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 145
Текст из файла (страница 145)
е. энтропия определяет оптимальное сжатие, которое может быть достигнуто. Приведенное вьппе функциональное определение энтропии в терминах сжатия данных является очень характерным для теории информации, как классической так и квантовой. Общее правило состоит в том, что любую фундаментальную меру информации моаюнв определить как количественную оценку физических ресурсов, необходимых для решения некоторой задачи по вбрабопжв данных.
эпражнение 11.1 (вычисление энтропии). Найдите энтропию, связанную с подбрасыванием (а) «честной» монеты, (б) «честной» игральной кости. Что произойдег с энтропией, если монета или кость «нечестные»? э'пражнение 11.2 (интуитивное подтверждение определения энтропии). Предположим, что мы хотим измерить количество информации, которое получаем, узнав, что в результате некоторого случайного эксперимента произошло событие Е.
Для этого будем использовать «информационную функцию» 1(Е), определенную на множестве возможных событий. Сделаем следующие предположения: 1. 1(Е) зависит только от вероятности события Е, так что можно записать Х = 1(р), где р Е [О, Ц вЂ” вероятность. 2. Х(р) — гладкая функция. 3 1(1нХ) = Х(р) + 1(д), где р,д ) О. (Если есть два независимых события, вероятности которых р и в, то информация о том, что произошли оба события, равна сумме количеств информации о том, что произошло каждое из них.) Покажите что 1(р) = 1«1обр, где й — произвольная константа. Если теперь рассмотреть множество взаимно-исключающих событий с вероятностями рм..., р„, то средняя информация, которую мы получаем, узнав о том, какое именно из этих событий произошло, равна 1«2 '» р; 1ойрь С точностью до постоянного коэффициента оно совпадает с шенноновской энтропией.
11.2 Основные свойства энтропии 11.2.1 Двоичная энтропия Энтропия случайной величины, принимающей только два различных значения, настолько полезна, что мы дадим ей специальное название двоичная энтропия и определим как Ня»(Р) ш — Р1о8Р— (1 — Р) 1о8(1 — Р), (11.8) 11.2. Основные свойства энтропии 613 где р и 1 — р — вероятности двух возможных значений. Если из контекста ясно, что речь идет о двоичной энтропии, мы будем обозначать ее просто Н(р). График двоичной энтропии изображен на рис. 11.1. Заметьте, что Н(р) = Н(1 — Р), а максимальное значение Н(р), равное 1, достигается в точке р = 1/2. На примере двоичной энтропии можно понять многие общие свойства энтропии. Одно из особенно интересных свойств касается поведения энтропии при смешивании двух или более распределений вероятностей.
Пусть, например, у Алисы есть две монеты: серебряная и золотая, причем вероятность того, что выпадет «орел» равна рд„для золотой монеты и рдэ для серебряной монеты. Предположим, что Алиса выбирает с вероятностью 9 серебряную монету и с вероятностью 1 — д золотую, после чего подбрасывает монету и сообщает Бобу результаты подбрасывания («орел» или «решка»). Какое количество информации при этом получает Боб? Интуитивно ясно, что оно не может быть меньше, чем среднее от количеств информации, полученных при подбрасывании каждой из монет.
Формально это можно выразить так: Н(«ри + (1 Р)рд) Д ЧН(ри) + (1 Ч)Н(рд). (11.9) Как правило, зто неравенство является строгим, поскольку Боб получает не только информацию о том, как упала монета («орел» или «решка»), но также некоторую дополнительную информацию, а именно какую монету бросала Алиса. Например, если рд„= 5/6, а рдя = 1/3, и Боб узнал, что выпал «орел», то ему естественно предположить, что была брошена золотая монета. Несложно убедиться, что (11.9) действительно выполняется.
Это соотношение является примером более общего свойства вогнутости, с которым мы встретимся в гл. 9 при обсуждении различных мер информации. Напомним, что вещественная функция называется вогнутой, если для любого р в интервале от 0 до 1 мы имеем /( * + (1 — Р)у) > И(х) + (1 — Р)/(у). (11.10) То, что двоичная энтропия является вогнутой функцией, легко увидеть из рис. 11.1; если соединить любые две точки на графике отрезком, то график обязательно пройдет над этим отрезком.
Мы будем часто использовать свойство вогнутости энтропии, как классической, так и квантовой. Может показаться, что приведенные выше рассуждения слишком тривиальны, чтобы привести к интересным выводам; однако, множество весьма глубоких результатов теории квантовой информации основано на искусном применении свойств вогнутости классической и квантовой энтропии.
Более того, в квантовом случае интуиция часто не позволяет понять, какими именно свойствами вогнутости должна обладать энтропия. Упражнение 11.3. Докажите, что двоичная энтропия Нд,(р) принимает максимальное значение при р = 1/2. Упражнение 11.4 (вогнутость двоичной энтропии). Из рис. 11.1 видно, что двоичная энтропия является вогнутой функцией.
Докажите, что это действительно так, т. е. что Ндв(РЯ«+ (1 — Р)хз) ~ РНдв(Я1) + (1 Р)Ндв(хз), (11.11) 614 Глава 11. Энтропия и информация а.в ох оо ог ог оэ о о оэ аг оз во а Б о.о о 7 о.в 0.9 г Рис. 11.1. График двоичной внтрооии Н(р) 11.2.2 Относительная энтропия Существует очень полезный аналог энтропии, который является мерой разли- чия двух распределений вероятноСтей одной и той-же переменной х. Это — от- носитавьнел энтроаил. Пусть имеются два распределения вероятностей р(х) и д(х) переменной х.
Определим отпносишельнрю энтропию р(х) по отношению к д(х) как Н(р(хфд(х)) ы ~~~ р(х) 1оя — = — Н(Х) — ~ ~р(х) 1ояд(х). р(х) й(х) (11.12) Имеется в виду что — О 1оя О = О при р(х) > О и — р(х) 1оя О = оо. В чем состоит полезность относительной энтропии и почему она является хорошей мерой различия двух распределений? Приведенная ниже теорема позволяет понять, почему выражение (11.12) можно рассматривать как меру различия. Теорема 11.1 (неотрицательность относительной энтропии).
Относительная энтропия неотрицательна, Н(р(х) Цц(х)) > О, причем равенство имеет место тогда и только тогда, когда р(х) = д(х) для всех х. где О < р, хг, хг < 1. Докажите также, что двоичная энтропия строго еогнртед функция, т. е. что (П.11) превращается в равенство только в тривиальных случаях хг = хю р = О, Р = 1. 11.2.
Основные свойства энтропии 615 Докалаоилэспыо. В теории квантовой информации часто применяется неравенство !ой х !и 2 = !их < х — 1, х > О. Оно превращается в равенство тогда и только тогда, когда х = 1. Перепишем его в виде — !ойх > (1 — х)/!и 2 и заметим, что Н(р(х)/!д(х)) = — ~р(х) !оя— И') р(х) ы Ф-,— ",,) 1 — (р(х) — д(х)) 1 — — (1-1) = О. !п2 (11.13) (11.14) (11.15) (11,16) Равенство в (11.14) имеет место тогда и только тогда, когда д(х)/р(х) = 1 для всех х, т.
е. когда два распределения совпадают. Полезность относительной энтропии связана еще с тем, что многие другие энтропийные величины можно рассматривать как частные случаи относительной энтропии, а ее свойства можно использовать для нахождения свойств других энтропийных величин. Например, неотрицательность относительной энтропии можно использовать для доказательства следующего фундаментального факта. Пусть р(х) — распределение вероятностей случайной величины Х, которая принимает д различных значений. Обозначим через с(х) = — 1/4 равномерное распределение вероятностей той же величины Х. Тогда Н(р(х)((д(х)) = Н(р(х)(~1/с() = -Н(Х) — ~р(х) !ой — = !ойг(-Н(Х).
(11.17) 1 Н Применяя теорему 11.1, получаем !оба — Н(Х) ) О, причем равенство имеет место тогда и только тогда, когда Х вЂ” равномерно распределенная случайная величина. Хотя этот факт и элементарен, он весьма важен и мы сформулируем его в виде теоремы. Теорема 11.2.
Пусть Х вЂ” случайная величина, принимающая 4 различных значений. Тогда Н(Х) < !ойд, причем равенство имеет место тогда и только тогда, когда Х вЂ” равномерно распределенная случайная величина. При изучении классической и квантовой энтропии мы часто будем выражать интересующие нас энтропийные величины через относительную энтроэГпражнеииэ 11.5 (субаддитивность шенноновской энтропии). Докажите, что Н(р(х, р)))~р(х)р(у)) = Н(р(х)) + Н(р(р)) — Н(р(х,у)). Используя этот результат, покажите, что Н(Х, У) < Н(Х) + Н(У), где равенство имеет место тогда я только тогда, когда Х и У вЂ” независимые случайные величийы.
616 Глава 11. Энтропия и информация 11.2.3 Условная энтропия и взаимная информация Пусть Х и У вЂ” две случайные величины. Как связано количество информащзи, содержащееся в Х, с количеством информации, содержащимся в У? В этом разделе мы введем два понятия — условную энтропию и взаимную информацию, которые помогут ответить на этот вопрос. Их определения выглядят достаточно формально, а интерпретация не всегда очевидна. Заметим, чго основная мотивация этих определений состоит в том, что указанные величины позволяют рассматривать вопрос о потребляемых ресурсах, который более подробно обсуждается в гл. 12, а их интерпретация зависит от рассматриваемого ресурса. Мы уже использовали совместную энтропию пары случайных величин в предыдущем разделе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
