Духин А.А. Теория информации
Подождите немного. Документ загружается.
41
§ 4. ВЫПУКЛОСТЬ СРЕДНЕЙ
ВЗАИМНОЙ
ИНФОРМАЦИИ
ВЕРОЯТНОСТНЫХ
СХЕМ
Без доказательства приведём теорему, описывающую строение поверхности
1(А;В).
Теорема 4.2. Средняя взаимная информация 1(А;В), рассмотренная
как функция
(p(a
t
),...,
р(а
т
))е£,
не имеет локальных
минимумов или седловых точек. Если 1(А;В) имеет нес-
колько локальных максимумов Р!(А),...,Р
Х
(А), то для
всех их, а также для всех точек симплекса, определяе-
t _ t
мых соотношением р
0
= ]£ajP
i
(A) а
}
^0, , значе-
i=i i=i
ние средней взаимной информации будет одним и тем же.
Согласно теореме 1.4.2 средняя взаимная информация не может иметь раз-
личные значения локальных максимумов. Если же в ряде локальных максиму-
мов достигается одно максимальное значение средней взаимной информации,
то это же среднее значение будет достигаться в любой точке, принадлежащей
выпуклой линейной оболочке, построенной на упомянутых локальных мак-
симумах.
Свойство выпуклости взаимной информации вероятностных схем исполь-
зовано в доказательстве теоремы 5.2.2, на которой основан метод нахождения
пропускной способности канала.
§5
В параграфе будут приведены определения энтропии
и
взаимной информа-
ции
для
непрерывных вероятностных схем.
Непрерывная вероятностная схема
А
задается множеством исходов
Q е
(-оо,оо)
и плотностью распределения вероятностей
р(х).
Энтропией схемы
А
называется величина
00
Н(А)
= -
Jp(x) log p(x)dx. (1.5.1)
-00
Для объединённой вероятностной схемы АВ, заданной множеством исходов
Q
е R
2
и
совместной плотностью распределения вероятностей р(х,у), энтропия
вводится аналогично:
00 00
H(AB)
= -J
Jp(xy)/
0
gp(xy)dxdy. (1.5.2)
-00-00
Частные
и
условные распределения находятся
по
формулам:
00 00
р(х)= jp(x,y)dy;
q(y)=
Jp(x,y)dx;
-00 -00
q(y/x
)
=
^f,
P
(x/y)
= ^f.
P«
Р(У)
Условная энтропия вероятностной схемы
В
относительно схемы
А
вычис-
ляется
по
формуле:
оо оо
Н(В
/ А)
= - J
Jp(xy) log q(y / x)dxdy. (1.5.3)
-00-00
Взаимная информация исходов
а е A, b е В
определяется следующим
об-
разом:
I(a;b) = /og-^-. (1.5.4)
p(a)q(b)
При этом предполагается,
что
p(a)*0,q(b)*0.
Интегрируя (1.5.4)
по
объединённой вероятностной схеме, получим выраже-
ние
для
средней взаимной информации
1(А;В)
= - ]
]p(xy)/og J*M>-dxdy.
(1
.5.5)
P(x)q(u)
Введённые величины связаны между собой следующими соотношениями:
ЭНТРОПИЯ
И
ВЗАИМНАЯ ИНФОРМАЦИЯ НЕПРЕРЫВНЫХ
ВЕРОЯТНОСТНЫХ
СХЕМ
43
§
5.
Выпуклость средней взаимной информации вероятностных схем
1( А; В) = Н(А) - Н(А/ В) = Н(В) - Н(В/А),
(1.5.6)
I (А; В) + Н( А / В) + Н(В / А) = Н( АВ). (1.5.7)
Если для конечных вероятностных схем введённые характеристики имели
определённый информационный смысл, то в ряде случаев для непрерывных
вероятностных схем такого толкования провести не удаётся. Более того, при
определённом подборе параметров, задающих плотности распределения ве-
роятностей, энтропийные характеристики могут принимать и отрицательные
значения. Они не инвариантны по отношению к преобразованию вероятност-
ных схем и не могут быть истолкованы как математические ожидания от соот-
ветствующих собственных информации.
Теоремы, доказанные в §§ 2, 3, имеют место для соответствующих величин,
введённых в этом параграфе.
***
Рассмотренные в первой главе энтропийные и информационные характерис-
тики вероятностных схем будут использованы во второй главе и, в особен-
ности, в заключительной главе. Основные понятия второй главы, введённые
Шенноном, получили развитие в работах
А.
Я.
Хинчина, Д. К. Фаддеева,
Р.
Пинскера и др.
ЗАДАЧИ
1.
Рассмотрим три урны, содержащие шары белого, синего и красного цве-
тов.
Состав шаров в этих урнах следующий:
a) 21 белый шар, 0 синих и 0 красных шаров;
b) 10 белых, 10 синих и 1 красный шар;
c) 7 белых, 7 синих и 1 красный шар.
Сравнить значения энтропии соответствующих вероят-
ностных схем, реализующихся при извлечении одного шара из
каждой урны.
2. В урне содержится п шаров, из которых m шаров белого цвета. После-
довательно без возвращения извлекаются 2 шара.
Пусть А и В - вероятностные схемы с двумя исходами, соответствую-
щими результатам испытаний при первом и втором извлечениях шаров.
Вычислить Н(А), Н(В), Н(АВ).
3. Найти энтропию вероятностной схемы, вероятности исходов
которой определяются:
а) Биномиальным распределением В(п,р)
Указание. Вычисления провести двумя способами:
- исходя из определения Н(А);
- используя представление биномиально распределённой случайной
величины в виде суммы индикаторов.
Ь) Распределением Пуассона
4.
В урне п шаров, из которых m белых. Из урны с возвращением извле-
каются шары до появления белого шара. Пусть к - число извлечений до
появления белого шара, к е N.
а) Найти энтропию вероятностной схемы
p
+
q
= l.
Р($„=Ю =
к!
к = 0,1,2...; X
>
0.
А =
к,
Р(к),
Ь) Исследовать изменение энтропии Н(А) при
\) п ->
оо,
m - фиксированном;
45
ЗАДАЧИ
ii)
Urn
— = 1.
П-»00
П
с) Изобразить график функции H(A;p).
5.
Задана объединённая вероятностная схема
АВ:
АВ
=
J(U)
(1,2)
(1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) (4,1) (4,2)
(4,3)^
[l/б
0 1/6 0 1/6 0 1/6 0 1/6 0 1/6 о
Найти:
Н(А), Н(В),
Н(А/В),Н(В/А) Н(АВ),
1(А;В).
6. Заданы две независимые случайные величины:
-
=
f° М -
=
f°
l
)
IPI qJ' U q
2
/
Pi+qi
=i
1
=
1,2.
Пусть
£
= ii,
Ф
т|
2
, где
Ф
-
операция сложения по модулю 2. Рассмотрим три
вероятностные схемы:
А
=
[
" • "
~|;В
= Г" |;С =
Pt
qi ) к Р2 чз J ^ Рз 4з;
a) Необходимо:
\)
сравнить значения I(C/(A,B)), l(C/A);
ii)
подсчитать l(c/A)
при
условии, что
р
2
= q
2
=0,5;
iii)
показать,
что
Н(С)>Н(А), Н(С)^ЩВ).
b)
Будут
ли
справедливы
эти
неравенства, если отказаться
от предположения независимости
Tj^Tfe?
7.
Рассмотреть объединённую вероятностную схему
АВ.
При
каких усло-
виях величина H(A)-H(A/bj):
a) положительна,
b)
равна нулю,
C)
отрицательна?
8. Пусть вероятностная схема
А
имеет бесконечное множество исходов
aj
i€N.
46
ГЛАВА I. ЭНТРОПИЯ И ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
1) Подобрать такие значения вероятностей, чтобы энтропия
Н(А) достигала наибольшего значения при условии, что
00
^кр(а
п
) - есть заданная фиксированная величина.
2)
Чему равно значение энтропии Н(А) при найденном распре-
делении ?
9.
Задана вероятностная схема:
А =
*1»
U>(
a
i)> р(
а
п);
Доказать, что
Н(А) = р(»
и
У<«-Ц +
(1
- Р(а
N
)>OG—J—
+
(1
- р(а
п
))Н(В),
Р(а
п
)
1-Р(
а
п)
где
В =
к
р(ЬО,
Р(Ь
П
_Д
h р(ь
к
) =
р(
а
к
)
1-р(а
п
)
10.
Показать, что ЩА)^Н(В), где
»19
, в =
bj,
b
B
^(b,),
q(b
n
)
J>(*i)> -> P(
a
nV
p(ai) = q(bi)
i =
l,...,n-2;
Ч(
а
п-1)
= 4(
a
n) = <*P(
a
n-l)+
(1
-
<*)p(a
n
), 0 £ a £ 1
11.
Как изменится величина энтропии дискретной вероятностной
схемы, если:
a) уменьшить максимальное значение вероятностей исходов,
b)
увеличить максимальное значение вероятностей исходов ?
12.
Задана конечная вероятностная схема ABC.
a) Установить, справедливы или нет следующие соотношения:
\) 1(АВ;С)£1(А;С),
й) 1( А;С / В) +
1(С;В)
>
1(С; В
/ А) +1(
А;С),
III)
Н(АВ/С)>Н(А/С),
IIII)
Н(АВС) + Н(А)<Н(АВ) + Н(АС).
b)
При каком условии эти неравенства обращаются в равенства?
47
ЗАДАЧИ
13.
Подберите соответствующее вероятностное распределение на
исходах объединённой вероятностной схемы ABC, чтобы не
выполнялись неравенства:
a) 1(А;В)<1(А;В/С),
b) 1(А;В)>1(А;В/С).
14.
Докажите справедливость равенств:
1(А;В/С) = 1(В;С/ А) -
1(А;В)
-
1(В;С)
=
1(С;
А/В) -
1(А;В)
- 1(А;С).
15.
Пусть вероятности исходов объединенной вероятностной схемы ABC
удовлетворяют соотношениям:
p(abc) = р(а)р(Ьс) для V(abc) е ABC.
Покажите, что отсюда следуют:
I(b;c/a) = I(b;c),
I(a;b/c) = I(a;b) = 0.
16.
Пусть вероятности исходов объединённой вероятностной схемы ABCD
удовлетворяют соотношениям:
p(abcd) = p(ab)p(cd) для V(abcd) е ABCD.
Покажите справедливость равенств:
l((ac);(bd)) = I(a; b) + I(a; d / b) + I(c;b /
а)
+ I(c;d / ab).
17.
Пусть исходы вероятностных схем А и В связаны соотношением:
a = ab + f3,VaeA,be=B.
Найти связь между энтропиями схем Н(А) и Н(В).
18.
Пусть вероятностные схемы А и В зависимы таким образом, что исхо-
ды схемы В однозначно определяют реализацию схемы А, то есть в слу-
чае реализации исхода b е В справедливо:
p(a(b)/b) = l.
1) Покажите, что в случае такой зависимости выполняется
равенство Н(А/В) = 0.
2)
Покажите, что справедливо и обратное утверждение: исхо-
ды схемы А однозначно определяются исходами схемы В,
если Н(А/В) = 0.
48
ГЛАВА I. ЭНТРОПИЯ И
ИНФОРМАЦИЯ
ВЕРОЯТНОСТНЫХ
СХЕМ
a) Вычислить Н(А), Н(А + В).
b) Сравнить Н(А) + Н(В) и ЩА + В).
c) Рассмотреть эти же вопросы для независимых равномерно
распределённых на [02J вероятностных схем.
22.
Рассмотреть три вероятностные схемы А
1
,А
2
,А
3
, вероятностные рас-
пределения которых заданы плотностями:
fi(x) = i * е
2а
' х
G
(-оо,оо).
При
этом
о\ < о\ < а
3
.
Сравнить значения энтропии Н(А
1
),Н(А
2
),Н(А
3
).
23.
Для вероятностной схемы А, распределение которой задано
плотностью:
подобрать такое значение параметра а, чтобы выполнялись:
е
a) Н(А) = 0,
b)
Н(А)<0.
19.
Пусть f
A
(x), f
B
(x) - плотности распределения вероятностных схем А и
В,
отличающиеся лишь математическим ожиданием.
Покажите, что Н(А) = Ы(В).
20.
Пусть непрерывная вероятностная схема А задается плотностью распре-
деления вероятностей f
A
(x). Пусть
f
A
(x)>0
при xe[a,b] и f
A
(x) = 0
при х'е
[a,b].
a) Покажите, что Н( А) < log (b - а).
b) Для какой плотности неравенство из пункта "а" обращает-
ся в равенство ?
21.
На отрезке [o,l] заданы две независимые вероятностные схемы А и В,
плотности распределения вероятностей которых таковы:
49
ЗАДАЧИ
24.
Вычислить энтропию вероятностной схемы А, распределение
которой задано плотностью:
[О х <
О.
25.
Пусть непрерывная вероятностная схема А = (А
15
А
2
) имеет двумерную
нормальную плотность распределения вероятностей со следующими па-
раметрами:
а
н
а
2
- математические ожидания,
|шу| i,j = l,2 - матрица вторых моментов.
a) Записать двумерную плотность распределения вероятнос-
тей
f\(x,y)
и частные распределения рд^(х), Рд
2
(У)-
b)
Вычислить Н(А), Н(А
1
),ЩА
2
), I(Aj;A
2
).
c) Сравнить величины Н(А) и H(Aj) + H(A
2
).
26.
Пусть для функции f
(х),
определенной в симплексе
выполняется неравенство:
М
(Щ)
+ М
(х
2
)
<
f
(А,,Х,
+
Х
2
х
2
),
где
Х
{
>0
i = 1,2 Х,+Я.
2
=1;
x^ej^.
Показать, что это свойство может быть распространено
на любое конечное число слагаемых:
^>0 i =
l,...,m
^1=1;
x
i^
x
m
e
Z
n
*
27.
Покажите, что если f
}
(x),f
2
(x) хе^- выпуклые кверху функ-
ции, то а^ОО + а^ОО* где а
]
+а
2
=1, а
1?
а
2
>0 - также вы-
пуклая функция.
28.
Покажите, что энтропия дискретной вероятностной
схемы является выпуклой кверху функцией, заданной на
симплексе
50
Г
ЛАВА
I.
ЭНТРОПИЯ
И ИНФОРМАЦИЯ ВЕРОЯТНОСТНЫХ
СХЕМ
29.
Покажите, что функция f(x) = -x//*x - выпуклая вверх на ин-
тервале
(0,оо)
функция.
30.
Покажите, что энтропия непрерывной вероятностной схемы
является выпуклой вверх функцией в области всех функций
плотности вероятностей.