Духин А.А. Теория информации
Подождите немного. Документ загружается.
81
§ 4. ЭРГОДИЧЕСКИЕ
ИСТОЧНИКИ.
ТЕОРЕМА МАК-МИЛЛАНА
любого наперёд заданного положительного числа. С учётом (2.4.13) получаем
доказательство леммы. А
Сделаем два замечания:
1.
Для произвольной функции f(x) введём в рассмотрение её положительную
часть:
ff(x) f(x)>0,
(х)
\ 0 f(x)<0.
Выразим |f(x)|, используя введённое обозначение:
|f(x)|
=
2
f
+
(x)-f(x). (2.4.14)
2.
При доказательстве леммы 2.4.3 будем также использовать очевидное нера-
венство:
(logxf^^-,
х>0. (2.4.15)
Лемма 4.3. Для дискретного стационарного эргодтеского источника,
произвольных е > 0, 6 > 0, достаточно большого т и любого
£>т имеет место:
>е
(2.4.16)
Доказательство.
Применим неравенство Чебышева в простейшей форме.
Для суммируемой неотрицательной случайной величины имеет место:
Р(^5)
(2.4.17)
Оценим вероятность события, фигурирующего в условии леммы
2.4.3,
с ис-
пользованием неравенства (2.4.17):
^ogq
m
(c<)-i/ogpM
log
Р(с?)
1
>еу =
>£z\<,—Е
£г
log
Р(С<)
Для математического ожидания модуля используем представление (2.4.14):
log
q
m
(
c
^)
Р(с<?)
= 2Е
log
q
m
(
c
i)
Р(с^)
-Е
log
q
m
(^)
К
первому слагаемому применим оценку (2.4.15). В результате получим:
82
ГЛАВА
11.
Источники
СООБЩЕНИЙ
?ihogq
m
(c
e
)-hogp{c
e
)\
£ъ
2!
°8
е
Е
\ Чт(
с
^)
P(Cf)
.
•Elog
>е|<
(2.4.18)
Р(с<>)
Подсчитаем математическое ожидание выражения, стоящего
в
квадратных
скобках:
'q«(c,)
N
-Е
Р(с^)
Р(с?)
J
=
T
p(c
,)4m(£i)
= 1
it
°
P(C,)
»
mH
m
+ (£-
m)H
(m+1)
- ffl,
Подставим полученные значения математических ожиданий
в
формулу
(2.4.18):
>е}<
hogq
m
(c
(
)-hogp(c
(
)
-2/oge
+
m
Hm +
(1
_m
)H(m+1)
_
H
^
(2.4.19)
£ •"• е
>el
+
И
(
Hffl
-н<
т+1
>)+ н<
т+1
>
- н,
e
* e
v m ;
*
Зададимся величиной
8' =
8e. Пусть
m
возрастает
и при
этом
£>т - не
фиксированная величина.
Выбором достаточно большого
m
можно добиться, чтобы
(2.4.20)
можно
е
£ 3
Положим,
что это
выполняется
при m >
m^S').
Выбором
m с
учётом того,
что lim H
m
= lim
Н
(т+,)
= ,
—
<1
т-*ж>
т—>оо
£
добиться, чтобы
1
{ т
' 3
(2А21)
Положим,
что
неравенство (2.4.21) выполняется
при
m>m
2
(8').
Наконец,
с
учётом того,
что lim
H
(m+1)
= lim = ,
выбором
m
можно
получить:
Н
(т+1)
-Н,
<
8'
3 (2-4.22)
Положим,
что
неравенство (2.4.22) выполняется
при
m>m
3
(S').
83
§ 4.
ЭРГОДИЧЕСКИЕ
ИСТОЧНИКИ.
ТЕОРЕМА МАК-МИЛЛАНА
Выбирая m
0
(5
,
)
=
max(m,,m
2
,m
3
) получаем одновременное выполнение
неравенств (2.4.20), (2.4.21), (2.4.22).
Для оценки вероятности события
-Jogq
m
(c^)--logp(c
e
)\
при m > m
0
(8')
и
при
£
> т получаем:
rJ°S4m(^)-^Ogp(c
£
)\
8'
> г\><—
= 5. А
е
С использованием лемм
2.4.1,
2.4.2,
2.4.3
докажем фундаментальную
теорему.
Теорема Мак-Миллана. Пусть последовательность
Cg
порождена дис-
кретным стационарным эргодическим источни-
ком
[A,P(S)].
Тогда
для
произвольных
е>0,
5>0 существует целое число <£
0
(s,6) такое,
что
при £>
£
0
(г,5)
I
1
/
1
XX
>е
)
<5,
(2.4.23)
где
р(с^) -
вероятность реализации последовательности
С£
=aj
iv
..,a^,
а Н
да
-
энтропия источника.
Доказательство. Из леммы 2.4.1 получаем
lim
H
m
= Н
00
m-юо
По определению предела для Ve > 0 3m
0
(e) такое, что m > m
0
(e)
(2.4.24)
Из леммы 2.4.2 для Ve>0 3m
0
(e) такое, что £
> £
0
,
выполняется:
pQ/ogq
m
(c,)
+ H<
m+1
>>e
>
(2.4.25)
Согласно лемме 2.4.3 для
Ve
>
0
и
соответствующего 8'
>
0
для m >
m„(e)
и
i
>
m будет выполняться:
^0gq
M
(
C
?)-^£P(M
>ej<8'.
(2.4.26)
Оценим вероятность события, фигурирующего
в
формулировке теоремы
с
использованием (2.4.24), (2.4.25), (2.4.26):
84
ГЛАВА
11. Источники СООБЩЕНИЙ
r
-logp(c
e
)-R
a
>е> =
р|-
hogp(c
f
)
+
-
e
logq
m
(c
e
)-\log
4m
(c
e
) - H<
m+1)
+ H<
m+1
> - H,
;}
+
p{|/ogq
m
(c,)
+
H<
m+1
>>e}
>8^
<P
+ P
-logp(c
e
)
+
\logq
m
{cA
H
(m+1)
•Hj>e}:
£38'.
Полагая 8' =
—,
получаем, что для достаточно больших £ будет выполнять-
ся неравенство (2.4.23), что и доказывает теорему Мак-Миллана. •
Выводы, сделанные из первой теоремы Шеннона для источников без памяти
(теорема 2.2.1) и марковских источников (теорема 2.3.1), справедливы и для
теоремы Мак-Миллана.
Имеет место свойство информационной устойчивости. Собственная инфор-
мация последовательности, порождённой эргодическим стационарным источ-
ником, удовлетворяет соотношению:
l(c
e
)
=
log
-
1
=
Н„
•р(с^)
<
2
-
4
-
27
)
Используем вероятностную трактовку соотношения (2.4.27). Последователь-
ности, порождённые стационарным эргодическим источником, обладают свой-
ством равнораспределённости
p<c,)s.-'
H
-.
(2.4.28)
Свойство равнораспределённости позволяет оценить количество последова-
тельностей, порождённых источником такого типа:
|С,|а-
Р(с^)
= а
(2.4.29)
Эргодические источники являются наиболее близкими с вероятностной
точки зрения моделями осмысленных сообщений. Поэтому формулу (2.4.29)
можно рассматривать как оценку числа литературных текстов длины I, в
алфавите А, где Н
л
понимается как энтропия текста на один знак.
ЗАДАЧИ
1.
Источник без памяти [A,p(s)]=[{0,l},p(0) =
3/4,p(l)
= l/4] порождает
последовательности, длины I знаков, c^eQ.
a) Задаваясь постоянными г| =
0,01;
ti = 0,05, подобрать число
£
0
е N, такое, чтобы выполнялось неравенство 2.2.2.
b) Для заданных
т]
=
0,01,
г| = 0,05 найти верхнюю и нижнюю
границы числа последовательностей в классе
2.
Рассматривается источник без памяти:
[A,p(s)H{0,l},
p(0) = q, р(1) = р, p + q = l].
Сравните |c^(Tij)| и
|c^
2
(r|
2
)|,
если
T|i
>T
h'
при
£\-£
г
,
и
t
x
>t
t
,
при
Л1=Л2-
3.
Источник [A,p(s)] задан диаграммой:
О
1
и таблицей переходных вероятностей:
P
0
(S
1
/S
1
) = l/2, P
0
(S
2
/S
1
) = l/2
P
1
(S
2
/S
2
)=l/2
P
1
(S
1
/S
2
)=l/2,
где
P
e
(Sj/S
l
)=P|j(e) - условная вероятность перехода источника из со-
стояния S, в состояние Sj с одновременным по-
рождением символа 6,
P
0
(S
0
) = P
D
(S
2
) = 1/
2
- начальное распределение на состояниях.
Необходимо:
a) найти вероятностное распределение на символах алфавита
А =
{0,1},
b) найти матрицу переходных вероятностей p(S|/Sj)=||Py||,
i,j
=
l,2,
c) найти предельное распределение на состояниях источника,
d) подсчитать энтропию источника на знак.
86
ГЛАВА
П.
Источники
СООБЩЕНИЙ
\ А
А • «1
»2
а
з
а
1
0,2
0,05 0,15
а
2
0,15 0,05
од
а
з
0,05 0,2 0,05
1)Найти
вероятностную схему А.
2)
Используя таблицу, задать марковский источник l(A;p(s)),
предполагая, что последующая порождённая источником бук-
ва зависит лишь от предыдущей.
3)
Для построенного источника подсчитать
Н
(1
\Н*
2
\...,Н*
к)
.
4) Найти lim Н
(к)
к->°о
6. Марковский источник [A,p(s)] задан следующей диаграммой:
1
0
Начальное распределение
р
0
(81)
=
р
0
(
8
2)~1/2.
Вероятности порождения символов а
£
(а| =0,1) в зависимости от сос-
тояния источника
Sj(j
= l,2) заданы величинами:
P(0/Si) = 0,8, P(l/Si) = 0,2,
P(0/S
2
) = 0,6, P(l/S
2
) = 0,4.
Необходимо:
а) найти вероятностное распределение, порождаемое на сим-
волах алфавита А источника и на биграммах (г^) е
4
= 0Д;
4.
Источник без памяти [A,p(s)] задан алфавитом А = {од} и распределе-
нием на его символах: р(0) = q, р(1) = р, р + q = 1, p,q £ 0.
Подсчитать математическое ожидание и дисперсию п
символов, порождённых источником.
5.
Вероятностное распределение на исходах (a^aj) объединённой вероят-
ностной схемы (А,А) задано таблицей:.
87
ЗАДАЧИ
b)
подсчитать шаговую энтропию и энтропию на знак. Найти
энтропию данного источника.
Марковский источник [A,p(s)j задаётся алфавитом символов:
А =
{а
1?
а2,аз,а
4
},
начальным вероятностным распределением на символах:
p
0
(a,) = l/4 i = l,...,4,
и матрицей переходных вероятностей:
(1/2 1/4 1/8 1/S)
1/4 1/8 1/8 1/2
1
1/8 1/8 1/2 1/41
,1/8 1/2 1/4 1/8J
Появление очередного знака в последовательности, порождаемой ис-
точником, зависит только от предыдущего знака.
Вычислить:
a) Н
(к)
- шаговую энтропию источника,
b)
Н
к
- энтропию источника на один знак,
c) энтропию источника = lim Н
(к)
.
к—» со
8. Марковский источник [A,p(s)] задан алфавитом символов:
А
=
{
А
1>
а
2>
а
зЬ
начальным распределением на множестве состояний:
(Po(
S
1
XPo(
s
2XPo(
s
3>) = (W)
и таблицей переходных вероятностей: Q = p(a
s
/Sj)
i, j = 1,2,3:
88
ГЛАВА
11.
Источники
СООБЩЕНИЙ
Q =
Sj'-.a,
a
2
«3
s
i
1/2 1/4 1/4
s
2
0
1/2
1/2
1
0
0
a) Найти вероятностное распределение на символах алфавита
А.
b)
Найти матрицу переходных вероятностей:
Р=Ы=1Р(5]/«|)1
м=м.
c) Классифицировать состояние S
{
. Найти предельное распре-
деление на множестве состояний.
6) Найти предельную энтропию источника.
9.
Марковский источник [A,p(s)] задан алфавитом символов:
А
=
{
а
1>
а
2>
а
3'
а
4}>
начальным распределением на множестве состояний:
(Po(
s
o)»Po(
s
l)»Po(^)»Po(
s
3)»Po(
s
4))=
(1А0,0,0),
диаграммой переходов:
и соответствующей таблицей переходных вероятностей Q = p(aj/Sj)
i
=
1,...,4;
j = 0,1,2,3,4:
Q =
Sj
a
i
a
l
«2 «3
a
4
So
0,3 0,0 0,7
0,0
S
!
0,7 0,125 0,075 0,1
s
2
0,3
0,5 0,0
0,2
S3
0,5
0,1
0,1
0,3
s
4
0,3 0,5
0,0 0,2
89
ЗАДАЧИ
a) Указать, какие состояния являются возвратными и невоз-
вратными.
b)
Указать все имеющиеся неразложимые подцепи и определить
период всех периодических подцепей.
a) Найти матрицу переходных вероятностей:
P =
||Pij||
= ||p(Sj/Si)|| iJ = 0,...,4.
b)
Провести классификацию всех состояний.
c) Провести разбиение множества состояний на неразложимые
классы.
6) Выделить среди них периодические и эреодические классы.
е)
Подсчитать вероятности поглощения эргодическими класса-
ми.
Т)Для периодических классов определить периоды.
д)
Для каждого эргодического класса найти предельные ве-
роятности.
h)
Подсчитать предельную энтропию в каждом из эргодичес-
ких классов.
10.
Марковский источник порождает последовательность двоичных
символов. В начальный момент времени источник пребывает в
состоянии S
0
. Таблицей задаётся функционирование источника для
дальнейших шагов.
90
ГЛАВА
II.
Источники
СООБЩЕНИЙ
c) Найти предельное значение вероятности каждой неразложи-
мой подцепи.
d) Найти асимптотическое значение энтропии на символ для
каждой неразложимой подцепи.