книги / Математическая теория энтропии

132,	Гл. 2. Энтропия и информация

Итак, система (2(S), ST, ц, Т) является сильно перемеши­ вающей и, следовательно, эргодической, поэтому в силу эргодической теоремы

					п—1
				lim	У* л: ° Т; (со) =			£	(х)
				п-*°° /-0
п. в. и в Lj. С другой стороны,
Е ( х ) =		5 p ( d © ) ( - l o g / o 2)(<0					= -	£	f ( s ) l o g f ( s ) =	H & ) .
		S(S)				1	s e S
Таким	образом,
				lim | / ( V		Т -/^(ю ) =			Л(Т)
				n-»oo rt	V/-0	/
п. в.	и в	Lt, и		в этом	примере		А(Т, 1) [и А(Т), поскольку
| — образующее				разбиение] действительно является скоростью
создания		информации.
Теорема			Шеннона — Макмиллана — Бреймана утверждает,
что это справедливо и в общем случае.
Теорема			2.58	(Шеннон — Макмиллан — Брейман).						Пусть
(Q,	Р, Т) — эрзодическая динамическая система. Если | — такое

измеримое разбиение пространства ее состояний, что Н (£) < оо, го

			Hm			Т - '|) = А(Т, I)
			п-юо п \/ -0				/
п. в. и в L\.
Доказательство. Поскольку							преобразование Т				эргодично,
а функция		/(|/V J1 ,T -/|)			лежит			в L,	(по	теореме 2.18), из
эргодической теоремы следует,							что
й" т т г £			' Ь Ц т-'«) •Т*м -£ { / {г/1 т-'|)}
п. |в. и	в	L,.	В	силу	того			что	# ( |)	< оо,	величина
B ^ (V W T ^ T 4 l)}, т.				е. Я (|/vr_I Т				/|),	есть скорость создания
информации		А(Т, |).		Таким образом, для доказательства тео­
ремы достаточно			показать,		что
Е>(п) =	■Ат1(v			т-'i) - гтт Е / (s/v						т-'t) • т

2.10. Теорема Шеннона		133
п. в. и в L,. Многократно используя формулу (2.12),		получим
I ( v т - ;| ) =	z ’ / ( T “V ,-Y + I т " ' 0 + 1 (т ~п^ ’
после чего применение	формулы (2.26) к каждому слагаемому
в правой части дает
/ ( Vo r ' i ) - g o / ( i / V T _/I ) о т*
(на протяжении этого	доказательства под 7 (|/V /« |	Trt
мы понимаем 1(%)°Тп). Таким образом,

ITTЁ|' (УVт_'0- ' (б/,У,т_'г)I -т*’

и теорема будет доказана, если мы покажем, что правая часть этого неравенства стремится к нулю в L, и п. в.

Сходимость в Lx доказать легко, поскольку из формулы замены переменной и того обстоятельства, что Т сохраняет меру, следует, что

5 Р (do) |/ (|/"v Т-;|)		- I (У	T-'l) | О т*(со) =
	=	5 Р (io) | / ( |/V * Т - '|) -			/ ( | / V , т		| .
По теореме 2.18 эта		последовательность интегралов сходится
к нулю, и, следовательно, D(n)-*- 0 в L,.						труднее.1)
Доказательство	сходимости		п.	в. . несколько
Зафиксируем целое число N и			определим		функцию 1Ы соот­
ношением
/„ <«.>	[ / ( £/ v , т - 'б ) - '			( е / v , - r - 'i ) |м .
Тогда для п > N
тттz |7« уУ'О - 1			т"'е) I •т*<•>>
> d n -	Л-0			Z	W	M .	<2-56>
				k ~ n - N

*) Эта часть доказательства при переводе изменена. — Прим, перев.

134	Гл. 2. Энтропия и информация

Поскольку N фиксировано, а функция 1Ы лежит в L, по лемме 2.17, из эргодической теоремы следует, что п. в.

n —N —l

И т т т т £ IN^ k H = \E(INl

(2.57)

k-О

Кроме того,

n —N —l

тЬ- Е /.<•т*м= 2 v,-т‘« - -^гт £ w « =

Л - 0	ft-О
	n —N—l
=тЬ Е ^ “т‘<“)-^+гт=лг Е «•■'*(•)
к—О	ft“О
Поскольку функция /0 лежит ’в L|,	из эргодической теоремы
следует, что п. в.

(2.58)

f t - n - N

Переходя в (2.56) к пределу при п-+оо и используя фор­ мулы (2.57) и (2.58), получаем, что

lim п+	1 Е	| '	( {/V *	( i / v Т - ■Ч) | . T* (») <	E (/„)
для всех	tif	и	почти	всех а. Поскольку 1ц-+ 0 в Lt,	теорема
доказана.

Вта теорема может быть распространена практически с тем же доказательством и на случай, когда преобразование Т неэрго-

дичйо: Тогда (l/rt)/(V /ljT -/l)->-/5 п. в. и в Lu где — неко­

торая функция на Q с математическим ожиданием h(Т, I) 1). Доказательство см. у Перри [116].

Свойство, сформулированное в приводимом ниже следствии, обычно называют свойством равномерной распределенности, а само это следствие — теоремой о равномерном распределении, поскольку в нем утверждается, что если | — измеримое разбие­ ние с конечной энтропией, то при достаточно больших п основ­

ная часть	элементов	разбиения |" =	имеет прибли­
зительно одну и ту же меру.
Пусть	| — конечное	разбиение с К элементами. Тогда раз­
биение	может содержать не более		К* = еп1ог К элементов.

!) Функция fi Т-инвариантна, а ее значение на эргодической компоненте С преобразования Т есть А(ТС, £f|C). — Прим, перев.

2.10. Теорема Шеннона

135

Если все эти элементы имеют одну и ту же меру, то она должна быть равна е~п1о*к. Оказывается, что в действитель­

ности большинство элементов разбиения £" имеет меру, близ­ кую к е~»л(т. I).

Следствие 2.54. Если I — измеримое разбиение пространства

состояний	эргодической динамической системы (Q,				Р, Т) и
Н (|) < оо,	то	для любого	б > 0 существует такое N,		что для
каждого п > N найдется			подмножество G(n) cz Q^n,		где £* =
— V"IoT- /|,		обладающее тем свойством, что
		Р^п (G(га)) > 1 —6
и для всех ® ^G (n)
		e -nihiT. *>+б] ^	/у ( { й}) < е-шмт. £>-«.
Доказательство. Из теоремы 2.53 следует, что
		Нш ^ / Г у Т ''0 ( ®		) “ А(Т, 5)
в L, и п. в.,		поэтому здесь также		имеет место и сходимость
по вероятности (т. е. по			мере). Тем самым существует такое
N (6), что	для	п > N (б)

Р {©; 1f 1( v V ' t ) (о ) - А(Т, £) | > б} < б.

Используя		определение /,		это	неравенство	можно записать
в виде
Pico:		Yt	1л(®)1““ logP(^) — лЛ(Т, |) |			> л б 1 < 6 .		(2.59)
	I	As ln				)
Составим		множество Q£n — G(п)			из тех элементов Д е Г . Для
которых			I — logP(,4) — лЛ(Т, £) | > лб,
т. е. положим
	G(л) =		{ N f (Л): | _	logр(Л) — nh (Т, £ )|< л б } .
Тогда	Р5л{Qj* — G (п)} < б			в силу неравенства (2.59).				Кроме
того,	если	6 e G	(л), то существует элемент			А е	такой, что
Р5л({©})==Р(Л)			и
	л[А(Т, 1 ) - 6 ] < - 1 э 2 Р(Л )<л[А (Т, |) +						б].
Тем самым					^ е - п ift(т. £>-*!.
		е - п ш т. 5)+в].^ р

Заметим, что из доказанного следствия вытекает, что при достаточно больших л множество G (л) (называемое множеством

136 Гл. 2. Энтропия и информация

правильных точек) содержит не более чем ехр (я [А (Т, 1) + 6]}

и не	менее чем (1 — б) ехр {п [Л (Т, £) — 6]} точек. Следовательно,
если	| — разбиение из К элементов и Л(Т, £) < log К (это всегда
так,	за	исключением случая, когда £ — бернуллиевское разбие­
ние для		преобразования Т), то отношение числа точек в G(n)

к максимально возможному чиелу точек в Q^n не превосходит

exp [nh (Т, £) +		пб] = ехр{п[h(Т, |) + 6 —log#]},
	ехр (п log К)
т. е. для достаточно		малых	б это отношение экспоненциально
стремится к нулю при п-*- <*>._
Аналогично если (Т,_£) и (Т, |) —два_таких случайных про­
цесса, что	Л(Т, !)< Л (Т , |),		a G(n) и G (п) — множества пра­
вильных точек в факторпространствах по разбиениям \/"ZQT~%
и V y ijT - l	соответственно,		то | G (п) |/| G (п) | растет экспонен­

циально при п-*- оо. (Здесь |G (n)| обозначает мощность мно­ жества G(n).) Это наблюдение лежит в основе доказательств ряда теорем из теории информации и эргодической теории.

2.11. ЭНТРОПИЯ КАК ФУНКЦИЯ РАСПРЕДЕЛЕНИИ

В предыдущих разделах мы рассматривали энтропию как характеристику случайных испытаний, моделью которых слу­ жило вероятностное пространство или измеримое разбиение пространства Лебега. В некоторых приложениях, в частности в теории информации (см. Макелис [86]), энтропию считают функцией на множестве дискретных вероятностных распреде­ лений. При таком подходе можно доказать (теорема 2.57), что энтропия, взятая с противоположным знаком, является выпук­ лой функцией, что вполне естественно. В этом разделе мы покажем, как можно взглянуть на энтропию еще и с этой точки зрения.

Напомним, что функцией распределения или распределением на! конечном (или счетно-бесконечном) множестве S называлась неотрицательная функция /, удовлетворяющая соотношению

2 ls s S f(s )= 1. Поскольку всякая функция на конечном мно­

жестве может быть представлена в виде упорядоченного набора своих значений, множество всех распределений на заданном конечном множестве S можно рассматривать как совокупность упЬрядоченных наборов 15 1 неотрицательных вещественных чисел с суммой единица. [С этой точки зрения распределение на| S — это нормированный неотрицательный вектор из про­

странства R|S| или /((S).]

2.11. Энтропия как функция распределений	137
Определение 2.55. Дискретным вероятностным распределе­
нием называется упорядоченный набор (/>,, .... pN) N	неотри­

цательных вещественных чисел, таких, что £ t_, р4= 1.

Конечному измеримому разбиению | пространства Лебега, состоящему из N элементов, можно поставить в соответствие N1 дискретных вероятностных распределений, поскольку сущест­ вует N1 способов упорядочения множества {Р(Е): Е е !}. Если разбиение | упорядочено, то ему отвечает единственное дискрет­ ное вероятностное распределение.

Наоборот, пусть (ри р2.........pN) — дискретное веройтностное распределение, a (Q, 9~, Р) — непрерывное пространство Лебега, тогда существует упорядоченное разбиение | = {Л^ Л2........ Лдг} пространства Q, которому отвечает распределение(ри р2, .. .,p N). Для построения этого разбиения определим упорядоченное

разбиение	единичного	интервала	(/, SB, Я), полагая
		g P i ) ,	Л - 1 ,2 ........ N,
где ро= 0. Поскольку пространство (Q, 9", Р) изоморфно (/, SB, Я),
в качестве	множеств	Ак можно	взять образы Ек при любом
связующем	изоморфизме.

Определение 2.56. Пусть р — (ри ... , pN) — конечное дискрет­ ное вероятностное распределение. Его энтропия обозначается через Н (р) и составляет

	Я(р) — — ^ p tlo g p ,.
Заметим, что если		I — произвольное конечное разбиение,
а (ри	. . . , pN) — одно из	отвечающих ему распределений, то
Я (|) =	Я(р). Таким образом, все полученные нами результаты

об энтропии конечных измеримых разбиений могут быть пере­ формулированы для энтропии дискретных вероятностных рас­ пределений.

Приводимая далее теорема является тем не менее новой, поскольку в ней дискретные вероятностные распределения рас­ сматриваются как точки евклидова пространства.

Напомним, что подмножество К вещественного линейного пространства называется выпуклым, если отрезок, соединяю­

щий любые две точки ри Р г ^ К			(т. е. множество {ару + (1 — а) р2:
а е ( 0 , 1]}),	полностью содержится в К.			Вещественнозначная
функция f на выпуклом подмножестве К				линейного простран­
ства называется		выпуклой, если для любых точек ри р2 из К
и числа а е	[0,	1] выполнено	неравенство
	f (api + (1 — а) р2) <		af (/>,) + (1 — a) f (д*).

138 Гл. 2. Энтропия и информация

В частности, вещественнозначная дважды дифференцируемая функция на отрезке вещественной прямой выпукла, если еб вторая производная неотрицательна.

Через 20ы будем обозначать множество всех дискретных вероятностных распределений с N атомами. Легко убедиться в том, что &>ц— выпуклое подмножество R*. Кроме того, мно­ жество £DN компактно, поскольку оно замкнуто и ограничено в Rw.

Теорема 2.57. Энтропия непрерывна на множестве .20N диск­ ретных вероятностных распределений, рассматриваемом как под­ множество RN. Энтропия, взятая с противоположным знаком, является выпуклой функцией.

Доказательство. Поскольку функция — xlog* непрерывна на отрезке [0, 1], очевидно, что функция Я непрерывна на 20N. Функция xlog* выпукла на [0, 1], поэтому для любых а е [0,

и р,

" I

— Я (ар + (1 — a) q) = £ [apt + (1 — а) qt] log [apt + (1 — a) qt]< t-1,

N					N
< Z a [Pi log Pi] +					Z (1 — a) qt log qt = — aH (p) — (1 —a) H (q),
т. e. функция — Я					выпукла.
Теорема			2.58. Для любого р е				20N
					\ 0 <	Я (р) ^	log N.
Более	того,		Н (р) = О тогда и только тогда, когда одна из ком­
понент	р	есть 1		(т. 'е. р — крайняя				точка 20N),	и Я (р) =	log N
тогда	и	только		тогда,		когда p =		(l/N, 1/N,	... , 1/N)	(т. е.

р — барицентр 20ы).

Доказательство. Эта теорема является просто переформули­ ровкой теоремы 2.3.

Предположим теперь, что 5 =	{1, 2, ... , N}, и рассмотрим
пространство последовательностей	(2(5), 2Г). Пусть Т — сдвиг

в 2 (S), а р — Т-инвариантная вероятностная мера на (2(5), Эг). Начальное разбиение £0 пространства 2 (5), состоящее из цилинд­ рических множеств (со: со0 = г} = С(, является упорядоченным разбиением, которому отвечает дискретное распределение р° = = (р (С(), р (С2), • • • * Р (Cjy)).

Элементы разбиения loV T -1£o имеют вид CjflT-'C/. Упо­ рядочивая их лексикографически, получим дискретное рас­ пределение

р(2) = (р (с, п T -‘Ci), Р (С, п Т-1С2), .... рССдгЛ Т-'Сдг).

2.11. Энтропия как функция, распределений

139

Аналогичным образом, вводя лексикографический порядок на множестве элементов разбиения V "ljT - (|o. мржно получить дискретное распределение р(п) для любого п.

Из определения ясно, что Н (р(п)) = H(VjZoTr ^)> ПоЭтому

Пт 1я(р<")) = А(Т, Ы.

Л->оо п

Определение 2.59. Пусть р — инвариантная относительно сдвига мера на (S(S), 9Г), где 5== {1, 2, . . . N}. Энтропией меры р называется величина

Л (р)= lim -i- /f (p(n>). Л-»00 71

Теорема 2.60. Если S — {1, 2, ... , N} и р — любая инва­ риантная относительно сдвига вероятностная мера на (2(S), &~), то

Л (р)< — X P f b g p f\ <«i

где p°t — р {(о е 2 (S): ©„= »'}. Более того,

h(\i) = — X p f]log P f

тогда и только тогда, когда р является продакт-мерой, построен­ ной по распределению р(0) на S.

Доказательство. Утверждение теоремы — переформулировка следствия 2.28, поскольку Л(р) = А(Т, £0).

Следствие 2.61. Если S и р те же, что и в теореме 2.60, то

A (p)< logtf,

причем равенство достигается тогда и только тогда, когда р есть продакт-мера, полученная из равномерного распределения на S.

Доказательство.	Очевидно,		до
			поскольку — X<_i Р(0)1°6Р{0Х
^ log N, причем равенство		достигается тогда и только тогда,
когда p f)= 1/N для	i = \ ,	2,	.. . , N.

Заметим, что теорема 2,60 (или следствие 2.28) дает харак­ теризацию бернуллиевских случайных последовательностей. А именно, {хп} является последовательностью независимых одинаково распределенных случайных величин со значениями в (5, Р) тогда и только тогда, когда

Нш 1я(р<">) = Я(р«»),

П-+00П

140	Гл. 2. Энтропия и информация
где	р(°) — распределение	х0 [т. е. р(0) (i) = Р	(*'))], а р(п) — со­
вместное распределение		{х0, хи ... , xn_i).

2.12.ПРИМЕРЫ

Вэтом разделе собран ряд примеров динамических систем, для каждой из которых приводится значение энтропии. В тех случаях, когда энтропия нами еще не вычислялась, указывается способ вычисления или дается ссылка.

Впервых нескольких примерах показывается, как энтропия систем, полученных тем или иным образом из других систем, выражается через их энтропии.

2.12.1. Прямые произведения

|Пусть {(Q/, S*"h Pt, Tj): t = 1,2, ... , N) — конечное семейство динамических систем. Их обратимость или эргодичность не тре­ буемся. Прямым произведением этих систем называется система ( £ 2 , Р, Т), где пространство с мерой (£2, SF, Р) является про­

изведением				пространств й {, а преобразование Т действует на й
по	формуле			Т(юь ©2, ... , <одг)==(Т, (©,),			. . . , Тд^©*).
Энтропия преобразования Т. составляет
					л (т ) = Е л (т л .
					<-1
Это следствие теоремы 2.50.
2.12.2. Косые произведения
	Пусть		(й, ЗГ, Р,		Т) — динамическая		система,		а / — измери-
мар функция на й					со значениями в единичном				интервале (/,
9?,	А).	Определим			преобразование	Tf		пространства (£2 X /,
X 93,		Я X Л-) формулой
				Tf (со, у) = (Та, (*/ +		/(©))),
где	(у -{- / (©)) обозначает дробную часть							числа у + / (ю).
	Эти преобразования впервые рассматривались Лнзаи [12],
который			доказал,		что они являются		метрическими эндомор­
физмами,			и получил условия, обеспечивающие их эргодичность

и перемешивание. Энтропия этих преобразований была вычис­ лена Абрамовым [2], и для любой функции / она составляет A(f/) = A(T).

Преобразования Tf являются частным случаем более общих преобразований, которые могут быть определены следующим

образом.	Пусть	(У, Щ, р) — вероятностное пространство и для
каждого	© е й	задан	метрический	автоморфизм	Аа простран­
ства (У, <Ц, р)		таким	образом, что	отображение	(а, у)*—* А ау

2.12. Примеры	141
из (£2 ХУ» ^ " 'К еУ) в (У* ‘У) измеримо.	Косое произведение Р
действует в пространстве (Q X i'. & X	Р X р) по формуле

Р (ю, у) — (Та, Ашу). Если Аау = (*/ + / (©)), мы приходим к опи­ санному выше примеру. Если А4) = А для всех ©, тогда косое

произведение	Р — это	просто прямое	произведение	Т и	А.
Формула, связывающая		А(Р), А(Т) и некоторые функции,			за­
висящие от энтропий разбиений AZrl			пространства	состояний
динамических	систем (У, О/, р, Аи), была получена			Адлером
[5] и Абрамовым и Рохлиным [3]. См. также Ньютон [88].
2.12.3. Степени эндоморфизмов
Если (£2,	p t Т) — произвольная		динамическая	система,

А — положительное целое число и через Т* обозначена компо­

зиция преобразования Т с самим

собой А раз,

то (£2, iF, Р,

Т*) — тоже динамическая система.

В теореме 2.43 было дока­

зано, что А(Т*) = АЛ(Т) для

А = 0,

1, 2, . .. ,

а

если

преобра­

зование

Т

обратимо,

то

Л(Т*) =

| А | А(Т)

для

А =

0,

± 1 ,

±2, ....

2.12.4. Потоки

Измеримым

потоком

называется

семейство

{Т<: / вещест­

венное}

метрических

автоморфизмов

Т* пространства Лебега

(£2, $F,

Р),

такое,

что

Т0 — тождественное

преобразование,

TsoTt =

Ts+t для любых вещественных чисел s и t, и отобра­

жение

(ю, Он-^-Tj© из

(£2 X R>

X •2’) в

(£2,

измеримо.

(Здесь R обозначает множество вещественных чисел,

а & — о-

алгебру измеримых по Лебегу подмножеств R.)

что

A (Tt) =

Используя

теорему

2.43, легко

доказать,

= |/|А(Т,) для

любого

рационального t. Абрамов [2] показал,

что это

равенство выполнено и для

всех вещественных t,

и тем

самым энтропией потока {Т<: / е R } естественно считать A(Tt). Колмогоров [69] первоначально определял энтропию потока как sup (1/0 A (Tj).

<>о	потока (T J и {Т'} в пространствах (£2, $F, Р) и				(£2',
Два
OF', Р')	соответственно	изоморфны,	если существует	метриче­
ский изоморфизм S: £2-»-£2', такой,			что T joS ssS oT ,	для	всех
вещественных t. Ясно,		что изоморфные потоки должны иметь
одну и ту же энтропию.
Потоком Бернулли		называется поток, для которого система
(£2, ST,	Р, Tf) является	системой Бернулли при любом t.			(См.

разд. 2.12.9 и гл. 4.) Существование потоков Бернулли дока­ зано в [96], а в работе [100] Орнстейн показал, что все потоки Бернулли с конечной энтропией становятся изоморфными после подходящей замены времени. Из результатов этой работы