Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
неравенстве обработки данных:
если X Г -> Z, то I(X : Z) ^ I(X : Y). (7)
Выражение X -> Y -> Z означает, что величины X, Y и Z образуют
последовательность (марковскую цепь), где Z зависит от Y, но не зависит
напрямую от X, т. е. р(х, у, z) = p(x)p(y\x)p(z[y). Смысл данного
неравенства заключается в том, что величина Y (информационный процессор)
передает величине Z не больше информации о X, чем сама получает.
2.2. Сжатие информации
Предварительно определив объем информации согласно уравнению (1),
необходимо доказать, что он действительно является удобной мерой
информации. С первого взгляда даже подход к этой задаче не является
очевидным. Один из основных вкладов классической теории информации
заключается в обеспечении подходящих методов рассмотрения информации. Для
описания данных методов рассмотрим простую ситуацию: предположим, что
некто (традиционно это Алиса) знает значение величины X и желает сообщить
его Бобу. Здесь можно ограничиться простейшим случаем, когда величина X
принимает лишь два возможных значения: "да" либо "нет". Будем говорить,
что Алиса является "источником" с "алфавитом" из двух символов. Алиса
общается с Бобом с помощью двоичных цифр (нули и единицы). Будем
определять объем информации, содержащейся в величине X, посредством
определения среднего количества битов, которые Алиса должна передать Бобу
для того, чтобы он узнал значение X. Очевидно, она должна передать
значение 0, если величина X принимает значение "да", и 1 - если принимает
значение "нет". Таким образом, для каждого переданного значения X объем
информации равен одному биту.
2.2. Сжатие информации
27
Однако, что произойдет, если определить величину X как случайную, но с
большей вероятностью принимающую значение "нет", чем "да"? (В качестве
примера подойдут решения, исходящие от субсидирующей организации.) В этом
случае более эффективная передача может быть обеспечена, если Алиса будет
придерживаться следующих действий.
Пусть р обозначает вероятность того, что величина X равна 1, а 1 - р -
вероятность того, что X = 0. Алиса должна ждать, пока для сообщения не
наберется п значений величины X, причем п должно быть достаточно большим.
Среднее число единиц последовательности из п значений равно пр, и,
следовательно, число единиц в любой заданной последовательности близко к
этому значению. Предположим, что величина пр является целым числом. Тогда
вероятность появления последовательности, содержащей пр единиц, равна:
рпр( 1 - р)п~пр = 2~пН{р). (8)
Читатель может убедиться, что обе части данного выражения действительно
равны между собой, причем в правой части неявно указывается путь
обобщения аргумента. Такая последовательность называется типичной. Говоря
более точно, все члены множества последовательностей удовлетворяют
неравенству
2-п(Н(р)+е) ^ р(последовательность) ^ 2~п(-н1'р^~?\ (9)
Здесь можно показать, что п значений, собранных Алисой, образуют типичную
последовательность с вероятностью, большей, чем 1 - е при достаточно
больших значениях п вне зависимости от того, несколько мало е. Это
значит, что Алисе не нужно отправлять Бобу п битов для того, чтобы он
узнал п значений величины. Она должна лишь сообщить ему, какую типичную
последовательность она имеет. Предварительно они должны договориться об
обозначении типичных последовательностей: например, они могут
договориться нумеровать их в порядке возрастания двоичной величины
(двоичного значения). Алисе нужно передать не всю последовательность, а
только ее обозначение. Чтобы понять, насколько эффективен данный метод
общения, достаточно показать, что вероятности появления типичных
последовательностей, количество которых составляет 2пН^р\ равны.
Очевидно, что для передачи одной из 2пН^ последовательностей Алисе
необходимо отправить пН(р) битов. Более того, Алиса не сможет сделать
общение
28
Глава 2
более эффективным (т. е. передавать меньшее число битов), поскольку
события, связанные с появлением типичных последовательностей,
равновероятны: дальнейшее оперирование информацией не будет продуктивным.
Таким образом, объем информации, содержащийся в каждом значении величины
X первоначальной последовательности, равен Н(р), что соответствует
уравнению (1).
Математические подробности, появившиеся в вышеуказанных рассуждениях,
вытекают из 'закона больших чисел, который гласит, что при малых г, 6 и
для достаточно больших п выполняется неравенство
р(\т - пр\ < пе) > 1 - (10) •
где m - число единиц, содержащееся в последовательности п
значений. При больших п число единиц т будет отлично от
их среднего
количества пр на величину, как угодно малую по сравнению с п. Например, в
данном случае распределение нулей и единиц соответствует биномиальному:
р(п, т) = С{п, т)рт( 1 - р)п~т ~ (11)
~ 1 с-(т~пр)2/2<Т^2)
(Т'/2п
где нормальное (гауссово) распределение получено для п, пр -> ос,
среднеквадратичного отклонения <т ~ \Jпр( 1 -") и С(п, т) = -------------
-------------.
