Духин А.А. Теория информации
Подождите немного. Документ загружается.
§
2
В этом параграфе определены понятия энтропии объединённой вероятност-
ной схемы, условной энтропии; доказана важная теорема о связи энтропии
объединённой вероятностной схемы и энтропии составляющих её частных
схем.
Рассмотрим вероятностные схемы:
А =
В =
Pl>'"?P
m
/
Ь(,...
9
Ь
П
1=1
kj^O,
iq,= l.
^4u^4
n
J j
=
l
Вообще говоря, схемы А, В не предполагаются независимыми, то есть
p(ajb j) * p|q
j,
i = 1,..., m; j = I,,..,
n
(1.2.1)
(1.2.2)
Определение
2.1.
Назовем схему С - объединённой
вероятностной схемой с
множеством исходов су
==
a
t
bj
и
вероятностным распределением
p(ll),...,p(mn)J'
если для вероятностей p(ij) выполняют-
ся следующие соотношения:
m п
Zp(4)
s
qj;
SP(U)
=
PI;
ХР(Ч)
= 1
-
С =|
c
ll
v
"'
V|nn
i=i
i-i
(Ч)
(1.2.3)
Для объединённой вероятностной схемы будем использовать обозначе-
ние С = АВ.
Понятие объединённой вероятностной схемы естественным образом рас-
пространяется на произвольное конечное множество конечных вероятностных
схем.
Для простоты записи для условных вероятностей будем использовать сле-
дующие обозначения:
Р(Ш = PiP(bj /Щ) = PiPy = qjP(aj /bj) = qjPjj
ЭНТРОПИЯ ОБЪЕДИНЕННОЙ ВЕРОЯТНОСТНОЙ СХЕМЫ.
УСЛОВНАЯ ЭНТРОПИЯ И ЕЕ СВОЙСТВА
ГЛАВА
I
Определение
2.2.
Энтропией объединённой вероят-
ностной схемы
A3
называется величина:
H(AB)=-Ep(ij)/ogp(ij).
(U)
(1.2.4)
Преобразуем выражение
Н
(АВ):
ЩАВ)
=- EpOJVog P(U)=~ ЕР(У)^
PiPij
=
(ij) <Ш
= - EpOJVog
Pi
-
1РШ)/0£
РЦ = - EPI*« PI -
1Р(Ш^ Pij
=
(ij) (4) (О (U)
= H(A)-Ip(ij)/og
Pi
j.
(4)
Отсюда следует:
H(AB)
-
H(A) =
- Zp(ij)/og
Рц
(1 2.5)
(Ш
Определение
2.3.
Величина
н(в/ A)=- Zp(U)'°&Pij
называет-
(U)
ся условной энтропией вероятно-
стной схемы
В
относительно схемы
А.
(12.6)
В определении 1.2.3 вероятностные схемы
А и В при
необходимости можно
рассматривать
как
объединённые схемы.
Наряду
с
энтропией
н(в/
А)
вводят
следующую условную энтропию:
(1.2.7)
Определение
2.4.
Величина
Hi
= H(B/a,)=
^-EpflyaOfogpfljj/ai)
=-£Ру>0£Рц
(j) (J)
называется условной энтропией
ее-
роятностной схемы
В
относительно
исхода
а
;
е А.
Имеет место:
н(в
/А)=-Е2л>(Ц)/в«
Рч
=
-Е£р|Рц
log
Ру
=
0)(j) (00)
=£Р|(-ЕРЦ*«
Pij)
=
ZpiHi
(i)
0) 0)
Полученное равенство дает основание назвать энтропию
Н(В/А)
средней
условной энтропией.
23
§ 2.
ЭНТРОПИЯ
ОБЪЕДИНЁННОЙ
ВЕРОЯТНОСТНОЙ
СХЕМЫ. УСЛОВНАЯ
ЭНТРОПИЯ
И ЕЕ СВОЙСТВА
Формула (1.2.5) может быть переписана в новых обозначениях следующим
образом:
Н(АВ)-Н(А) = Н(В/А). (1.2.5')
Если вероятностные схемы А и В статистически независимы, то есть
Ри
=
4j.
то:
н(в/
А)=-
Ep(ij)fog
Рц = -£qj hg qj= H(B).
(4) (j)
Аналогично можно ввести условную энтропию Н(В/А).
Докажем важное соотношение между энтропией объединённой вероят-
ностной схемы и энтропиями составляющих схем.
Теорема 2.1. Для любых двух конечных вероятностных схем справед-
ливо неравенство:
Н(АВ)<Н(А)
+
Н(В).
(1.2.8)
Равенство в (1.2.8) имеет место тогда и только тогда,
когда схемы A u В независимы.
Доказательство. Обозначим hy = p(ij) -
p
t
qj;
i = l,...,m; j =
l
v
..,n,
Заме-
тим, что:
Zh
ij
= £p(ij)-£p
i
£q
j
=0.
(4) (Ц) (i) (j)
Пусть f
(x)
- непрерывная на [x, x + h]. функция, имеющая конечную произ-
водную в каждой точке интервала (х, х + h) (h ^
0).
По теореме Лагранжа о ко-
нечных приращениях получаем:
f(x + h)-f(x) = hf (x + 0h); О<0<1.
Положим
f(x) = /ogx; х =
Psqj;
Ь=Ь
у
; 0 = в
1у
Тогда имеем:
log Р(Ш - log p
s
q j - hy
[log
(pjqj + вцЬц)]
1
Соотношение
log Р(У) =
/0£Р|
+fogqj +
Piqj+^ijbij
Piqj+Qyhy
усредним по вероятностной схеме
AB
и умножим на (-1):
h(ij)p(ij)
Н(АВ) = Н(А) + Н(В) - log е £
(ij)Pi4i+®iihy
ГЛАВА
!
Оценим разность:
Н(АВ)
-
Н(А)
-
Н(В)
=-/oge£
h
ij(Pi4j
+h
ip_
=
-
l
°g
e
Z
h
ii
(i,j) Pi4i+©ijhjj
h
К-®
ц
ь
ч
+р,^+Е
ц
ь
ц
]
=
'fr-®q)
h
u
Pi4j
+0
ij
h
ij
(U) (i.j)!
hg&-0
u
)
Piqj+©ijhij
Так как log e > 0, (1 - ©у) > 0, Vij, то знак суммы определяется знаком
знаменателя в каждом слагаемом.
При hy > 0 знаменатель положителен. Если hy < О, то
Pi4j + ©yhy * РЛ}
+
hy = P(ij) * 0.
Следовательно, рассматриваемая разность отрицательна. Откуда вытекает,
что:
Н(АВ)<Н(А) + Н(В).
Если схемы независимы, то
Н(А/В)=Н(А) и Н(АВ) = Н(А) + Н(В).
Докажем обратное утверждение, если
Н(АВ) = Н(А) + Н(В),
то это возможно, когда
Piqj+©ijhij
Так как каждое слагаемое неотрицательно, то равенство этой суммы нулю
возможно тогда, когда Н^=0, Vij. То есть p(ij) =
Pi4j,
Vij. Это и означает
статистическую независимость вероятностных схем А
и
В.
А
2
(У)!
Замечание
2.1.
Используя неравенство
^ Sl.R*Ip,-£
qj
-l,
V
41
41
можно легко получить ещё одно доказательство
1
теоремы 1.2.1.
(1.2.9)
1
Доказательство неравенства
(1.2.9)
приведено
в
Приложении
(см.
П.11).
25
§ 2.
ЭНТРОПИЯ ОБЪЕДИНЕННОЙ ВЕРОЯТНОСТНОЙ
СХЕМЫ.
УСЛОВНАЯ
ЭНТРОПИЯ
И
ЕЕ
СВОЙСТВА
Прологарифмируем
обе
части неравенства:
i=l
-Xq.togq^-^q.togPi-
(12
-
10)
Заметим,
что:
H(A) + H(B)
- -£p(ij)[fog
Pi
+
fog
Ч]
]= -£p(ij)fog
Pi
q
r
(U)
(u)
В силу неравенства (1.2.10) получаем:
Н(А)
+
Н(В)
>
-£р(ф/о£ Р(Ч)=Н(АВ).
А
(и)
Замечание
2.2.
Доказательство теоремы
2
может быть получено
с
использованием неравенства: х
-
1
>
/я х, х >
0.
(1.2.11)
Неравенство имеет естественную геометрическую интерпретацию:
Y
Рис.
2.1
Рассмотрим:
Н(АВ)-Н(А)-Н(В)
=
=
ZPi
fo
#
Pi
+
S
q
i
/og
q
J ZpW)^
P('J)
=
=]£p(y)tog
Pi
+
Хр(У)
/о
£
4j
-
2)p(4)fog
P(4)
=
lo
%
e
Zp(iJ)fc—•
(U)
(ij) (ij) (ij) Pji
2
Доказательство неравенства
(1.2.11)
приведено
в
Приложении
(см. П.1).
26
ГЛАВА
I. ЭНТРОПИЯ и ИНФОРМАЦИЯ BEРОЯТНОСТНЫХ
СХЕМ
Сумма в последнем соотношении берётся по тем
(i, j),
для которых p(Ij) >0.
Для этих слагаемых Pj > 0, р^ > 0.
Следовательно, неравенство (1.2.11) может быть применено для каждого
слагаемого
Н(АВ) - Н(А) - Н(В) < log
eZp(iJ)|
(ij)
Pi
-1
loge
Zpi4j-Zp^>
.(U) (U)
0.
Приведём ряд следствий, вытекающих из теоремы 1.2.1.
1°
Н(В/А)<Н(В).
(1.2.12)
Доказательство.
Н(В / А)
-
Н(В) = -2>(ij)fog Ру + 5>(ij)fog
4j
= 5>(4)fog^- =
(U)
= £p(U^g^2S:togej;p(U)|
оЗ)
Р<Ч) ш) '
(ij)
P(4)
(ij)
Pij
= 0.
2°
Неравенство (1.2.12) остается справедливым и в случае, когда
А=
(АА
Г
)
- объединённая вероятностная схема.
Н(В/А,,...,А
Г
)^Н(В).
(1.2.13)
Н(А„...,А
Г
)£
£н(А
к
).
к=1
Доказательство.
P0iv,i
r
)
= POI )
Р(>2
/
Ч
)-РОг '
»1
>-Л-1
)•
Прологарифмируем полученное равенство:
log p(i,i
r
)
=
log
p(i,)+log
p(i
2
/1!)+...
+ log p(i
r
/
i,
,...,i
r
_i).
Умножим это соотношение на
-p(i,,...,i
r
)
и просуммируем по вероятност-
ной схеме А|,...,А
Г
:
27
§ 2.
ЭНТРОПИЯ
ОБЪЕДИНЕННОЙ
ВЕРОЯТНОСТНОЙ
СХЕМЫ.
УСЛОВНАЯ
ЭНТРОПИЯ
И ЕЕ СВОЙСТВА
Выразим
q(c^/aj):
fl
f
c
/a^-
q
(
C
/
a
j)-P
(a
^
/b
k)^
nrf
/к * ^
q(c^ / aj) - у v - - p(c, /
b
k
a
f
).
fll
a
J
P(
A
I/b
k
)
-
2)p(ti»...HrV^P(iir..»ir)
=
(Ч,.ЛГ>
= -
ZpOiv.-HrV^POi)-
2p0i»-»i
r
V^P(i2/!i)---
D!^I
R
)
(ILV..,I
R
)
-
£POi
>~>«
r
)
to
£ p(i
r
Ul) =
OLV..,I
R
)
= H( A,) + H(A
2
/ A,)+... + H(A
r
/ AiA
r
.!).
В силу следствий 1° и 2°:
H(A
k
/A
lv
..,A
k
^H(A
k
).
Следовательно, неравенство (1.2.13) доказано. А
4° Для любых трёх конечных вероятностных схем А, В, С справедливо нера-
венство
Н(С/АВ)^Н(С/В).
Доказательство. Предположим, что реализовалось событие b
k
е В.
Апостериорное распределение в схемах
АС,
А, С обозначим:
р(а^/Ь
к
)=
Ч
(а
|С
Д
p(a
l
/b
k
)=q(a
i
),
р(с,/Ь
к
)
=
Ч
(сД
Наряду со схемами А, С, АС введём и схемы А', С, (АС)' с апостериорным
распределением.
Из следствия 1° имеем:
Н(С/А')<;Н(С'). (1.2.14)
В терминах условных энтропии перепишем (1.2.14) следующим образом:
Н(С') = -Eq(c,yog q(c,) =
-£р(с,
/b
k
)/og р(с, /Ь
к
) = Н(С/Ь
к
).
(О (О
Н(С/А') =
=
"Z4(
A
I)Z^
c
^
/A
I)
TO
S 4<
с
г
/A
I) =
"Z4(
A
I)4(^
l&i)log q(c^ /aj).
<i) (О <M)
28
ГЛАВА
1. ЭНТРОПи я и
ИНФОРМАЦИЯ
ВЕРОЯТНОСТНЫХ
СХЕМ
Н(С7 А')=
-Ip(as
/Ь
к
)1р(с^ /Ь
к
а,Уо*р(с,
/b
k
aj) =
(О
М
=
Ep(aj/b
k
)H(C/b
k
a;).
0)
]>>(a
1
/b
k
)H<C/b
k
a
l
)SH(C/b
k
).
(1.2.14')
(i)
Умножая
обе
части равенства (1.2.14')
на р(Ь
к
) и
суммируя
по
вероят-
ностной схеме
В,
имеем:
00
<i)
(к)
То есть
Н(С/АВ)<Н(С/В).
5° Для любых
г
конечных вероятностных схем А
19
А
2
,...,А
Г
справедливо нера-
венство:
Н(A
r
/
A,
v
..,A
r
_!)
<
Н(A
r
/
А
2
,
А
3
А
г
_,).
А
(1.2.15)
Результаты, изложенные
в
данном параграфе, будут
по
существу исполь-
зованы
во
второй
и
пятой главах
для
получения соответствующих энтропий-
ных оценок (см.
гл. II, § 1; гл. V, § 1).
§3
В рассматриваемом параграфе вводятся понятия различных видов мер ин-
формации, заданных на конечных вероятностных схемах. Устанавливаются
связи между введёнными понятиями; приводится связь с энтропией вероят-
ностной схемы. Доказана теорема о невозрастании средней взаимной инфор-
мации при сюръективном отображении.
Рассмотрим две конечные вероятностные схемы:
Л m
Pi v>Pi»—9Pm>/ i=l
A =
Исследуем вопрос об измерении количества информации, содержащейся в
исходе а^ при условии, что исход bj €В реализовался. Естественно, что появ-
ление исхода bj изменяет безусловную априорную вероятность появления ис-
хода aj до апостериорной условной вероятности рj
2
= p(a
s
/bj). В качестве ко-
личественной меры такого изменения примем величину
р(а:/Ь:)
I(a
^
)=fog£
fe) d-3.1)
Если реализация исхода bj не влияет на вероятность появления исхода a
i?
то есть если эти исходы независимы, то p(aj) = p(aj/bj), и введённое коли-
чество информации, как следует из формулы (1.3.1), будет равно нулю.
Можно рассматривать количество информации, получаемое при реализации
исхода bj, если известно, что исход а
4
имеет место. Аналогично (1.3.1) полу-
чаем:
10^)= log = log-*-. м
P(bj) qj
Заметим, что имеет место равенство:
I(bj;a,)= log log log ^=1(а
|;
Ь
Л
).
(1
.
3в3)
4j Pi4j Pi
ВЗАИМНАЯ СОБСТВЕННАЯ, УСЛОВНАЯ ИНФОРМАЦИЯ
ВЕРОЯТНОСТНЫХ СХЕМ
30
ГЛАВА
I. ЭНТРОПИЯ и ИНФОРМАЦИЯ
ВЕРОЯТНОСТНЫХ
СХЕМ
РП Pii
Определение
3.1:
Величина I(a
i
;bj) =
/ag-
J
-=/og
—
J
Pi 4j
называется взаимной информацией
исходов а
;
и bj.
Для объединённой вероятностной схемы АВ мы построим случайную ве-
личину:
,l(a
i;
bj^
1
А
в(а|;Ь|)
=
^...,l(aj;bj
^
...,p(ij),.-. >
Своеобразие этой случайной величины состоит в том, что её значения опре-
деляются вероятностным распределением на исходах (ajbj).
Для среднего этой случайной величины введено обозначение:
IC^BJ^ElABCa^b^^IpCijJIta^bp^EipOJ)/^
(1 34)
(ij) i=ij=l Pi \ ' ' '
Определение 3.2: Величина
1(А;В)
называется средней
взаимной информацией вероятност-
ных схем А и В.
Из формул (1.3.3), (1.3.4) следует, что
1(А;В)=1(В;А).
В ряде случаев реализация исхода bj е В однозначно определяет реализа-
цию исхода aj е А, то есть:
p(a
i
/bj)=p
ji
=l.
1
Такие ситуации возможны, когда В с А. Тогда выражение (1.3.1) прини-
мает следующий вид:
I(a
i;
bj) =/og ^ =/og -J-.
(1
з
5)
Pi
Pi
v
'
1
Например, в урне п белых шаров и один черный; b - извлечён черный шар. В этих условиях
вероятность вынуть белый шар равна единице: Р(а
|
/ Ь ) = 1.
В силу симметрии полученного выражения можно дать следующее опре-
деление: