Духин А.А. Теория информации
Подождите немного. Документ загружается.
ГЛАВА ПЕРВАЯ
ЭНТРОПИЯ
и
ИНФОРМАЦИЯ
ВЕРОЯТНОСТНЫХ
СХЕМ
§1
(1.1.1)
АКСИОМАТИЧЕСКОЕ ВВЕДЕНИЕ В ТЕОРИЮ ЭНТРОПИИ
ВЕРОЯТНОСТНЫХ СХЕМ
Исходным понятием для построения рассматриваемой теории является по-
нятие вероятностной схемы. Пусть (Q, М, Р) - вероятностное пространство,
- полная группа попарно несовместимых событий.
Определение 1.1. Пара А = ({а|},(p(aj))) называется вероят-
ностной схемой.
Говорят, что вероятностная схема А дискретна, если число событий {aj
не более чем счётно. В этом случае А будем записывать в виде:
^р(а,),..., р(а
к
),...
где а
к
- исход вероятностной схемы, р(а
к
) - вероятность исхода,
£р(а
к
) =1, р(а
к
)>0.
к
Если число событий {а
к
} более чем счётно, то вероятностная схема А на-
зывается непрерывной. Тогда её задают, описывая множество возможных ис-
ходов и указывая с помощью плотности распределения вероятностей р(х) ве-
роятностное распределение на исходах. На протяжении данного курса будем,
как правило, рассматривать конечные вероятностные схемы.
Важной характеристикой схемы является энтропия - средняя мера нерав-
новероятности исходов схемы. Энтропия и близкое понятие информация по-
разному определялись рядом авторов. Приведём некоторые из этих
определений.
Согласно Р. Хартли
1
количество информации, содержащееся в сообщении,
должно удовлетворять двум требованиям:
a. Пусть сообщение Т,, записанное в алфавите Aj, [А^п^ имеет длину
i?,,
а сообщение Т
2
, записанное в алфавите А
2
, |А
2
|=п
2
, имеет длину
(
2
•
Тогда если выполнено iij
1
=П2
2
,
то сообщения Т
г
и Т
2
несут одина-
ковое количество информации.
b.
Количество информации, содержащееся в сообщении, пропорционально
его длине.
1
См. Библиографию [98].
13
§ I.
АКСИОМАТИЧЕСКОЕ
ВВЕДЕНИЕ
В ТЕОРИЮ ЭНТРОПИИ ВЕРОЯТНОСТНЫХ
СХЕМ
Из этих положений Хартли получил формулу для количества информации
в
сообщении:
I
=
fogi/, (1.1.2)
где п=|А|
-
мощность алфавита,
I -
длина сообщения.
К. Шеннон рассматривал порождение сообщений
в
условиях вероятностной
схемы:
А
=
Ip.=
i,
o<
Pi
<i.
^p(»l)»~»P(«iW
i=i
Относительно количества информации, содержащегося
в
сообщении
Т
дли-
ны
t
t
составленном
по
схеме независимых испытаний, высказываются сле-
дующие требования:
a. Пустое сообщение не содержит информации.
b.
Количество информации, содержащееся
в
сообщении, пропорционально
его длине.
По Шеннону
2
, количество информации, содержащееся
в
сообщении
Т =
=а^ ,...a
ir
равно:
1<Т)=П,
(ИЗ)
п
где
I =
-]£pjA>g
pj -
энтропия вероятностной схемы,
или
количество
i=l
информации, приходящееся на один символ порождённого сообщения.
Величина
а (а >
1)
-
основание логарифмов, определяет единицу измерения
количества информации. Если
а = 2, то
информацию измеряют
в
двоичных
единицах битах; если
а =
е,
то
информация измеряется
в
натуральных еди-
ницах натах; если
а
= 10,
то
информация измеряется
в
десятичных единицах
дитах
3
А.
Я.
Хинчин
к
определению энтропии вероятностной схемы подошёл
с
ак-
сиоматических позиций.
В его
работе
4
установлено,
что
энтропия конечной
вероятностной схемы однозначно определяется
с
точностью
до
постоянного
множителя при задании системы аксиом.
Аксиомы
ХИНЧИНА
1.
н(р
19
...,р
п
)
-
ненулевая непрерывная по переменным р
]9
...,р
п
в
симплексе
0<
Р|
<1,
Pl
+ ...+p
n
=l.
2.
н(р,,...,р
п
)
-
симметрична по переменным pj,p
2v
..,p
n
.
2
См.
Библиографию
[76].
* От
английских
слое
«Ш>,
«nut»,
adit»
соответственно.
4
См.
Библиографию
[69].
14
ГЛАВА
i.
ЭНТРОПИЯ
и
ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
3.
Н(р
15
р2,.-1Рп50)
=
H(pi,P2v»>Pn).
4.
H(q
n
,...,q
lm
;q
21
,...q
2in
;...;q
n
i,...,q
nm
)
= н(р„...,р
я
) + Spj н[
^-,-,Зм
i=l
V
Pi Pi
Pi= 4ii
+
+
Я|т
(»
= W).
5.
H(p
lv
..,p
n
)<Hf-
v
..
9
-
Система аксиом Фаддеева
5
эквивалентна системе аксиом Хинчина
и
позволяет получить
тот же
результат.
Аксиомы
ФАДДЕЕВА
1'.
н(р,
1
-р)
непрерывна
при 0 < Pj ^
1
и
положительна хотя
бы в
одной
точке.
2'.
н(р,,р
2
,...,р
п
)
симметрична
по р
1?
...,р
п
.
где
3'.
При п > 2
H(p
lr
..,p
n
_,;q
1
,q
2
)
=
н(р
1
,...,р
п
)+р
п
нГ^
3
-,^1,
\Рп
Рп)
Рп=Ч\+Чг
Разница
в
этих системах аксиом заключается
в
том,
что
аксиома 1.1.5 (экст-
ремальность функции энтропии) заменяется требованием положительности
энтропии
в
одной точке. Аксиомы Хинчина 1.1.3
и
1.1.4 заменяются аксиомой
1.1.3'.
Аксиома
1.1.3'
естественна,
так как
неопределённость схемы
А
j>i>~>Pti-i;qi,q2>/
отличается
от
неопределённости схемы
v
..,a
n
__j,a
n
А
=
VPlv-
5
Pn-l9Pn>
на неопределённость, происходящую
от
подразделения
а
п
на два
подсобытия
b|,b
2
с
условными вероятностями
—. Эта
неопределённость должна
Рп
Рп
быть преодолена только
в
случае, если реализуется событие
а
п
,
вероятность
которого равна
р
п
.
Если рассматривать энтропию
как
количественную меру неопределённости
в реализации вероятностной схемы,
то
последняя аксиома естественна.
Установим равносильность аксиом
1.1.2, 1.1.3,
1.1.4 и
1.1.2', 1.1.3',
сле-
дуя упомянутой работе Фаддеева
6
.
s
См.
Библиографию [63].
'Там*
15
§ l. АКСИОМАТИЧЕСКОЕ
ВВЕДЕНИЕ
в ТЕОРИЮ
ЭНТРОПИИ
ВЕРОЯТНОСТНЫХ
СХЕМ
Лемма 1. Из аксиом
1.1.2,
1.1.3, 1.1.4 следует, что Н(1,0) = 0.
Доказательство,
Подсчитаем Н(-,0,0) двумя способами:
2 2
a. По аксиоме 1.1.3:
Н(НД0) = Н(Н);
2 2 2 2
b.
По аксиоме
1.1.2:
H(i,i,O,0)
=
H(|,O,i,O).
Применим аксиому
1.1.4:
Н(|
,0,1,0)
=
Н(1,1)
+
1н(1,0)
+
1н(1,0)
=
Н(1,1)
+ Щ1,0).
Отсюда следует, что
Н(1,0) = 0. А
Лемма 2. Из аксиом
1.1.2.
1.1.3, 1.1.4 следует аксиома 1.1.3'.
2п
Доказательство. Рассмотрим набор r
lv
..,r
2n
, r
t
> 0 X
r
i
==
среди ^
i=l
есть п-1 нуль. Из аксиом 1.1.2 и 1.1.3 следует, что H(ri,...,r
2n
) перестановка-
ми аргументов можно представить в виде:
Н (р
ь0;
р
2
,0;...;
p
n
-i,0;
q
l9
q
2
).
Применим аксиому
1.1.4:
H(p
b
0;...;p
n
_
1
,0;q
1
,q
2
) =
= H(
Plv
..;
Pn
_
l9
p
n
) +
Pl
H(i,o) +...+
Pn
^H(i,0) +
PB
H[5L,SI =
VPn
Pnj
= H(p
lv
..;p
n
^,p
n
)
+РП
Н^,32
VPn
Pn
Лемма 3. Из аксиом
1.1.2',
1.1.3' следует, что Н(1,0) = 0.
Доказательство. Подсчитаем двумя способами Н(!,!,0).
2 2
H
(
I,I,O)=H(I,I
)+
IH(I,O).
нф! Д»)
= Н(0,| ,|) = Н(0,1)+щ! ,1).
16
Глава
I.
ЭНТРОПИЯ
И ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
Следовательно, Н(1,0) =
0.
•
Лемма 4. Из аксиом
1.1.2'.
1.1.3' следует аксиома 1.1.3.
Доказательство.
H
(Piv>p
n
-i;Pn>0)
=
H(p
1
,.»,p
n
_i;p
n
) +
p„H(i,o)
=
= H(pi,...,p
n
_i;
Pl)
). •
Лемма 5. Из аксиомы 1.1.3' следует
H(Pi,.»,p
n
-i; qi,»,q
m
) = H(
Plv
..,р„_!,р
п
)
+р
п
н
4
vPn Pn
Здесь m >
2,
p
n
= q,
+...+q
m
.
Доказательство. При m = 2 утверждение леммы совпадает с аксиомой
1.1.3'.
При т>3 лемма доказывается индукцией по т.
Лемма 6. Из аксиом
1.1.2', 1.1.3'
следует
Н(ЧП
v>qjmi
;q21v»
5
q2m
2
»4nl
э—>Чпт
а
)
~
=
Н(р
1
,...,р
и
)
+ 1р
|
н(
1=1
^Pi'"" Pi J
Здесь
Р1
=
Чп
+...+
Ч[т$
.
Доказательство. Нужно п раз применить лемму 1.1.5 к каждой группе ар-
гументов, что возможно в силу симметрии. Приняв m
1
=m
2
= ... =m
n
= m, по-
лучим, что из аксиом
1.1.2', 1.1.3'
следует аксиома
1.1.4.
Установлена равносильность групп аксиом
1.1.2, 1.1.3,
1.1.4 и
1.1.2',
1.1.3'.
А
Перейдём к доказательству теоремы единственности функции энтропии.
Введём определение:
F(n) =
H^,...,~j,
при n > 2 и F(1) = 0.
Применяя лемму 1.1.6 к случаю
1115=1112=
... =m
n
= m Чп
=
—~, получим
mn
F(mn) =
F(m)
+ F(n).
Применим лемму 1.1.5 к Н|
In n
(1.1.4)
17
§ 1. АКСИОМАТИЧЕСКОЕ ВВЕДЕНИЕ В
ТЕОРИЮ
ЭНТРОПИИ
ВЕРОЯТНОСТНЫХ
СХЕМ
1 1 1 п-1
н = н -,— + —н
n nJ In n J п
п-1.
Обозначим Г|
п
= Н
= F(n)- — F(n-1).
Лемма 7. При п ->
СО
_ F(n)
-»0HA,
n
=F(n)-F(n-l)->0.
Доказательство. В силу непрерывности Н(рД-р) при р е [0,1]
т|
п
=
нГ—,-5—1)
—>
Н(0Д) = 0, при п ->
оо.
Далее,
nr|
n
= nF(n) - (n-l)F(n-l).
Отсюда, складывая эти соотношения для k =
1,2
г
..,п,
имеем:
nF(n)=
к=1
Получаем
П П
к=1
п +
1
2п
~ 2 » п(п + 1)
Однако Ъ^Чк " среднее арифметическое первых — -
п(п + !)^
=1
2
НОВ
стремящейся к нулю последовательности ЛиЛг'Лг'Лз'Лз'Лз
>—
Следовательно,
2
чле-
п(п + 1)~
Далее,
2,kri
k
-> Он ц
в
=~A-Z->
о,
при п 00,
1
A,
n
= F(n) - F(n-1) = Г|
п
F(n-1) -> 0. Лемма доказана. А
В силу формулы
(1.1,4)
функция F(n) будет определена при всех натураль-
ных п, как только зададим значения функции F на простых числах.
Именно, если n^/jj*
1
,...где р\^р
%
- простые, то
F(n)=a, F(
Pl
)+...+a
s
F(/?
s
).
Положим,
F(/>)=
C
P
^G
P
>
Г
Д
Е
Р ~ простое число. (1.1.5)
18
ГЛАВА
1. ЭНТРОПИЯ И ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
Тогда
F(n) = а, с log рх +... + a
s
c
ft
log
p
s
.
=
F{p
.
)
.
1
^lLi
ogipi
.
l)+Cpihg(pi
-1)-Ц
Р1
-i) =
Лемма 8. Среди чисел с
р
(р =2Д5,7
Г
..) существует наибольшее.
Доказательство. Допустим противное и покажем, что это предположение
противоречит предположению о непрерывности Н(Р,1-р) при р= 0.
Действительно, если в последовательности
с
р
(р -
23,5,7,...)
нет
наибольшего числа, то можно построить бесконечную последовательность
простых чисел Р\^Рг^Р\ так, что pj= 2, р\ - есть наименьшее простое
число, такое, что
c
pj
>c
/?j_i
•
Из способа построения этой последовательности
ясно,
что как только простое число q меньше р-
х
, то t
q
<с
рх
.
Пусть i > 1 и q^
1
,...,<з^
8
есть каноническое разложение числа р\-Л.
Рассмотрим
А.
А
=РСй)-Р(л-1)
=
Р\
l
<>g
Pi Л-1 j=:l
J П
*
J J
Ясно,
что
s
Z<*j(c
p|
-*
qi
)log qi > (c
p{
-c
2
)log2> (c
p2
-c
2
)fog2,
так как
q^<P[
t
c^< c^. и в силу чётности (pj-1) среди q$ присутствует
число 2 с ненулевым показателем.
Далее, при i ->
оо
Следовательно,
(
с
/?
2
~C2)/og
2 < 0, что невозможно. А
Таким же образом устанавливается, что среди с
р
существует наименьшее.
19
§ 1. АКСИОМАТИЧЕСКОЕ
ВВЕДЕНИЕ
В ТЕОРИЮ
ЭНТРОПИИ
ВЕРОЯТНОСТНЫХ
СХЕМ
log
— + 2>](с
р
-с
ч
)&вд2
_ш / „m „га 1 , «
p
m
/ogp
m
p
m
-i
p
При переходе к пределу при m -»
со
получим (с^- с
2
) log 2 < 0, что невоз-
можно. Таким образом, для всех р' имеет место (с
р
*< с
2
).
Совершенно таким же образом устанавливается, что (с^'> с
2
) при всех р\
Лемма доказана. •
С учётом доказанных лемм
1.1.7,
1.1.8,
1.1.9 в системе аксиом Фаддеева
может быть доказана:
Теорема 1.1. Справедливо представление функции Н(р,,р
2
,...>Р
П
)
п J
H(p„p
2
,...,p
n
) = c^Pi/og — (с>0). (1.1.6)
i=i Pi
Доказательство. Рассмотрим случай п = 2
Пусть р = - при натуральных г и s. При
s
соединив аргументы в две группы из г и s-r элементов. Получим:
г [11
Пусть р = - при натуральных г и s. Применим лемму 1.1.6 к Н
s I s s
Лемма 9. Функция F(n) = clogn, где с - постоянное.
Доказательство. Достаточно установить, что все равны друг другу. До-
пустим, что найдётся такое простое число р \ что
Ср'>с
2
.
Обозначим через
р то простое число, для которого с
р
принимает наибольшее значение. Тогда
Ср>с
2
и р > 2.
Пусть m - натуральное число и q^ ^qf
%
= р
т
-1.
Рассмотрим:
к
рт
=
Цр
л
)-Щр
т
-1)~
=
F(
/?
m
)-^^tog(
/
7
m
4)+c
p
tog(p
m
-l)--F(p
m
--l)
=
logp
m
. F(p
m
) р
т
р
т
20
ГЛАВА
I.
ЭНТРОПИЯ
И ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
Отсюда
Н(р,1-р) = F(s)-pF(r)-(l-p)F(s-r) =
= с log s - р
с
log г - (1-р) с log
(s
-
г)
=
S
S 1 1
=
С
(Р log - + (1-р) log ) = с(р log - + (1-р) log - ).
г s
—
г р 1-р
В силу непрерывности Н(р Д-р) полученная формула может быть распрост-
ранена и на иррациональные значения р. Постоянная С > 0 в силу положи-
тельности Н(р,1-р), хотя бы в одной точке.
Переход к общему случаю осуществляется методом математической индук-
ции
на основании аксиомы 1.1.3'. А
Выводы этой фундаментальной теоремы Д. К. Фаддеева о представлении
функции энтропии для дискретной вероятностной схемы позволят в дальней-
шем характеризовать производительность источника информации, оценивать
возможности сжатия информации, получить формулу для вычисления про-
пускной способности дискретного канала связи.