М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 146
Текст из файла (страница 146)
Нам будет удобно дать ее явное определение. Совместнвл энтропия величин Х и У определяется как Н(Х, У) аь — ~~~ р(х, у) 1ойр(х, у). (11.18) Это определение можно естественным образом обобщить на любое число случайных величин. Совместная энтропия является мерой полной неопределенности относительно пары величин (Х, У). Предположим, что мы узнали значение У. Это значит, что мы приобрели Н(У) бит информации о паре (Х,У). При этом все равно остается некоторая неопределенность относительно пары (Х,У), поскольку мы не знаем значение Х.
Энтропия Х при условии, что значение У известно, определяется как (П.19) Н(Х(У) ш Н(Х, У) — Н(У). Условная энтропия является мерой неопределенности Х при известном значении У. Взаимная информация между Х и У измеряет количество информации, которое является общим для Х и У. Давайте сложим количество информации, содержащееся в Х, Н(Х), и количество информации, содержыцееся в У. Та информация, которая является общей для Х и У, будет при этом учтена дважды, а информация содержащаяся только в Х или только в У,— лишь один рэз.
Поэтому, вычитая из полученной суммы совместную энтропию пары (Х, У), Н(Х, У), получим общую, или взаимную информацию Х и У: (11.20) Н(Х:У) ш Н(Х)+Н(У) — Н(Х, У). Отметим полезное равенство Н(Х:У) = Н(Х) — Н(Х~У), связывающее условную энтропию с взаимной информацией. Чтобы получить представление о том, как ведет себя шенноновская энтропия, мы приводим ниже некоторые простые соотношения между различными энтропиями. 11.2. Основные свойства энтропии 617 Теорема 11.3 (основные свойства шенноновской энтропии). (1) Н(Х, У) = Н(У, Х), Н(Х:У) = Н(У:Х). (2) Н(У~Х) > О и, таким образом, Н(Х:У) < Н(У), причем равенство имеет место тогда и только тогда, когда У является функцией от Х, У = 7(Х).
(3) Н(Х) < Н(Х, У), причем равенство имеет место тогда и только тогда, ко- гда У является функцией от Х. (4) Субадцитивность. Н(Х, У) < Н(Х) + Н(У), причем равенство имеет ме- сто тогда и только тогда, когда Х и У являются независимыми случайными величинами. (5) Н(У~Х) < Н(У) и, таким образом, Н(Х:У) > О, причем равенство имеет место тогда и только тогда, когда Х и У являются независимыми случайными величинами. (6) Сильная субаддитивность.
Н(Х, У, Я)+Н(У) < Н(Х, У) + Н(У, Я), при- чем равенство имеет место тогда и только тогда, когда Я вЂ” ~ У -+ Х является марковской цепью. (7) Введение дополнительных условий уменьшает энтропию. Н(Х~У, Я) < Н(Х~У). Многие из этих утверждений являются либо очевидными, либо доказываются элементарно, поэтому мы приведем лишь некоторые соображения. Доказагпельсгпео. (1) Очевидно из определений. (2) Поскольку р(х, у) = р(х)р(у~х), можно записать Н(Х, У) = — ) р(х, у) 1обр(х)р(у~х) — р(х) 1оя р(х) — ~ р(х, у) 1он р(у~х) Н(Х) — ~~~ р(х, у) 1оя р(у~х) (11.21) (11.22) (11.23) кк*,с~я ~ — кя.,с( — ~1) р(х)р(у) 1 ~р(х)р(у) р(х,у) 1п 2 ' 1 р(х,у) 1 1 — 1 — — (р(х)р(у) — р(х, у) = — = О.
(11.25) Субалдитивность доказана. Равенство достигается тогда и только тогда, когда Таким образом, Н(У~Х) = — 2;, р(х, у)1обр(у~х). Поскольку — 1обр(у(х) > О, то Н(У~Х) > О. Равенство здесь имеет место тогда и только тогда, когда У является однозначной функцией Х. (3) Следует из (2). (4) Для доказательства субадцитивности можно опять использовать тот факт, что 1об х < (х — 1)/ 1и 2, х > О, где равенство имеет место тогда и только тогда, когда х = 1. Мы находим, что 618 Глава 11. Энтропия и информация р(х, у) = р(х)р(д) для всех х и р.
Таким образом, неравенство субадцитивности превращается в равенство тогда и только тогда, когда Х и У независимые величины. (5) Следует из (4) и (1). (6) Сильная субаддитивность шенноновской энтропии доказывается аналогично обычной субаддитивности, хотя ее доказательство несколько сложнее. Мы предлагаем его в качестве упражнения (упр. 11.6). (7) Интуитивно ясно, что неопределенность Х при известных значениях У 'и г меньше чем неопределенность Х при известном У.
Для формального доказательства,нужно взять определения входящих в неравенство величин (1) и переписать его в виде н(х у,г)-н(у,г) <н(х,у)-н(у). (11.26) Это не что иное, как неравенство сильной субаддитивности, с точностью до перестановки слагаемых. Упражнение П.б (доказательство классической сильной субаддитивности). Докажите что Н(Х, У, г) + Н(У) < Н(Х,У) + Н(У, г), причем равенство имеет место тогда и только тогда, когда г -~ У вЂ” н Х является марковской цепью. Упражнение 11.7. Из упр. 11.5 следует, что взаимную информацию Н(Х:У) можно рассматривать как относительную энтропию двух распределений вероятностей, Н(Х:У) = Н(р(х,р)ир(х)р(у)). Представьте условную энтропию Н(У~Х) как относительную энтропию для двух распределений вероятностей. Используя полученное выражение, докажите, что Н(У)Х) > О, и определите условия, при которых имеет место равенство.
Различные соотношения между энтропиями удобно представить графически при помощи диаграммы Венка для энтропии (рис. 11.2). К этой диаграмме следует относиться лишь как к мнемоническому правилу для запоминания различных определений и свойств энтропии. Рис. 11.2. Соотношения между различными энтропиями. Прежде чем завершить изучение основных свойств условной энтропии и взаимной информации, рассмотрим цепное правило для условных энтропий.
11.2. Основные свойства энтропии 619 и Н(Х1,...,хи~У) = ~ Н(Х;~У,Х1,...,Х1 1). (11.27) Доиазапэеаьсгпво. Рассмотрим сначала случай а = 2, а затем применим индукцию по и. Используя определение условной энтропии, можно сделать следующие преобразования: Н(Х1, Хг~У) = Н(Х1, Хю У) — Н(У) (11.28) Н(Х1, Хэ1 У) — Н(Х1, У),+ Н(Х1, У) — Н(У) (11.29) = н(х,р,х,)+н(х,~, (11.30) что доказывает цепное правило для и = 2. Предположим, что для некоторого и правило доказано и докажем его для п+ 1. Используя полученный результат для и = 2, находим Н(Х„...,хи+1~У) = Н(хэ,...,Хи+1)У,Х1) + Н(Х1(У). (11.31) Перепишем первый член справа, используя предположение индукции Н(Х1,...,Х„+1)У) = ~1 Н(Х1,~У,Х1,...,Х1 1)+Н(Х1~У) (11.32) и+1 '1 Н(ХДХ„...,Х1 1), что доказывает цепное правило для п + 1. 'Упражнение П.8 (взаимная информация не является субадцитив- ной). Допустим, что Х и У вЂ” независимые случайные величины, принима- ющие значения О и 1 с вероятностью 1/2.
Пусть Я = Х ® У, где операция Ю— сложение по модулю два. Покажите, что в этом случае взаимная информация ие является субаддитивной, т. е., что н(х у: г) ~ н(х: г) + н(у: г). (11.34) Упражнение 11.9 (взаимная информация не является супераддитив- ной). Рассмотрим случайные величины Х1 ьз Хэ ы У1 ж Уэ, принимающие значения О и 1 с вероятностью 1/2. Покажите что в этом случае взаимная информация не является супераддитивной, т.
е., что Н(Х1 . У1)+ Н(хэ . Уз) ф Н(Х1,хэ. У1,Уэ). (11.35) Теорема 11.4 (цепное правило для условных энтропий). Пусть Х1,..., Х„ и У вЂ” произвольные случайные величины. Тогда 620 Глава 11. Энтропия и информация 11.2.4 Неравенство обработки данных Во многих приложениях информация, которую мы должны обрабатывать, уже была подвергнута воздействию каких-либо шумов и, таким образом, дошла до нас в искаженном виде. В теории информации существует важное неравенство — неравенство обработки данных, которое выражает тот факт, что информация, полученная из источника, с течением времени может тааько уменьшаться; потеря информации является необратимым процессом.
В этом разделе мы придадим этому утверждению более точную форму. Интуитивное понятие обработки данных можно формализовать при помощи марковских цепей случайных величин. Марковская цепь представляет собой последовательность случайных величин Х~ — > Хз — ~ °, такую, что Х„+~ не зависит от Хм..., Х„~ при условии, что величина Х„фиксирована. Можно записать р(Хвы — — х„+~~Х„= х„,...,Х~ = х~) = р(Х„+~ = х„+~~Х„= х„). (11 36) При каких условиях в марковской цепи происходит потеря информации, имевшейся в начальный момент? Неравенство обработки даннъх позволяет ответить на этот вопрос в терминах квантовой теории информации. Теорема 11.5 (неравенстно обработки данных). Пусть Х вЂ” > У вЂ” ~ Е— марковская цепь.
Тогда Н(Х) > Н(Хгб) > Н(Х: Е). (11.37) При этом Н(Х) = Н(Х:У) тогда н только тогда, когда по значению У можно восстановить значение Х. Этот результат интуитивно выглядит правдоподобно. Фактически утверждается, что если случайная величина Х под воздействием шума перешла в 1', а затем величина У поступила на вход некоторого обрабатывающего данные устройства со случайной величиной Е на выходе, взаимная информация между Е и Х будет всегда меньше, чем взаимная информация между У и Х. Доказательство. Первое неравенство в (11,37) уже было доказано в теореме 11.3.
Используя определения взаимной информации и условной энтропии, мы замечаем, что Н(Х:Е) < Н(Х:У) эквивалентно Н(Х~Ъ") < Н(Х~Е). Из того, что Х вЂ” У -+ Е является марковской цепью, следует (упр. 11.10), что Š— ~ У вЂ” ~ Х также является марковской цепью и, таким образом, Н(Х~У) = Н(Х~У, Е). Поэтому достаточно доказать, что Н(Х,У,Е) — Н(У, Е) = Н(Х~У,Е) < Н(Х~Е) = Н(Х, Е) — Н(Е). Это не что иное, как неравенство сильной субалдитивности, доказанное ранее.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
