Вероятность: основные понятия, структура, методы. - Скороход A.B.

1=1

Поэтому

<*..■■•.*„>№ <*„...,,Я)6*$.....*П)

/ (лг,,...,л-„)^Х„ С и..--.^п)'

Пусть /и (Л) — число точек множества Л. Тогда будем иметь

2 2 (>-

"'/Да'1".....-

- 2 »(*8!.....-.>)-»(,,......%г."(«8!.....•■>>)<

(дг,,...,л:п)еЛ'„

< 2 .....^п5§:...,7я).

Таким образом,

а^<2-П(я+я(,м 2 _ .....^п^ё;...,-,)+«,.

(*1.....^б^л

(Л'1,...,^Л)(<А'П

Покажем теперь, что можно выбрать так Х„, чтобы «у было
меньше, чем 2е,. Обозначим через Ь число точек Х„, 5 — число
точек Хп, и—число точек 5(")1,...л-л), 1) —число точек (хи...,хп),
для'которых (ух, ..., уп)^1х\,...,х ), число и можно считать не
зависящим от (хх, ..., хп)£Хп, а число V не зависящим от
(Уи...,Уп)Ь и ^ $$,....,„).

Средняя ошибка по возможным выборам будет
«= 2 (С?ГЧи<81 + (С'Г2_,г(Я+Я(11'?Н26)Х

X 2 2 2 7 (я) (Уи •■■,Уп)18(п) _ X

*ЛС*Я (лг,,...,л:п)ехл(г/..--.г/л)5(^>--^л) (*«.....хп)

(хап)£х„

Х(Уи Угд<

17—2550 249

<Ё1+ 2 2 (Уи---,Уп)Х

(*„...,*„)€*„

х и/„..., уп) (сггс;^-"^"'»-»)»

= 8, 4- (С?)-С-22--«("+"№)-25) х

х 2 ( 2 75(") (уь---.у«)У=

=в1 + (с^Гс^-"^^1^2^^ (и .....,л)).

Заметим, что г)т(и5{")„...,^)) = к Поэтому

а< 81 + 2-в(//+//(11,£)-2в^ • < е, +2^£2-я^+Я(Г1'=)-М).

Та*к как для достаточно больших /г 5<2*(Л,+6), и<2"(Яит+6),
то

а<81 + 25й"+1.^. 2пН.

Можно подсчитать, что Х1<2п{Н{т)+('\ ^ >2*(Я(|)~6) и, значит,

а<е1+276"+12"(Я--/(|'т,)),
и последнее выражение можно сделать сколь угодно малым, если
// + 7б</(5, г)). Очевидно существуют такие Л*П) что <а.

Теорема доказана.
3.2. Обобщения.

а) Эргодический источник сообщений. Пусть
теперь поток сообщений, вырабатываемый источником инфор-
мации, есть стационарный эргодический процесс \%п, п^ч
со значениями в конечном множестве Z.

Лемма 1. Если Я = Я(£„)—энтропия стационарного про-
цесса {£п}, то для всяких е>0 и 6>0 можно указать такое
п0, что при п>По можно указать такое подмножество Z„crZ,г,
что:

1) число точек (2],..., гп) не превосходит 2п<н+6),

2) 2 Р&=*ь ...,£„ = *„}> 1-е,

3) Я-й^о^Р ...Лп=2п}<Н+Ь.

Доказательство. Нам удобно считать, что стационар-
ный процесс {£„} определен для всех целых п (его можно оче-
видным образом доопределить). Положим

Ф„(г)=Р{£0=;гА-,, Е-* • • •, £-»}, Ф(г) = Р{&,=гДь ...}.

Тогда Mlog2q>(£0) = Я, M|log2q>n(£o)—1°&*(ф(£о)|-»-0 и с веро-
ятностью 1

п

lim ~log2 Q (£„ &s, ..., С„) = Hm -1 У М£* I £i. ■ • • • = Я,

п-*оо

где С}(ги ..., г„) = Р(£! -г,, ..., £„=гл), ?*(гй |гь ..., гк_Л =
= Р{1,к = гк\1,х, ■ ■-Лк-\}- Пусть для данных е>0 и б>0

Р{|й-1ой0(£„ .... £„)-//|<б}>1-8.

Положим = |(г!, ..., гп): ~ \о& С{ (гх, . .., гп) — Н | < б|, тогда
выполнены условия 2) и 3), а число т (Еп) удовлетворяет не-
равенству т (2„)2~"(Я+6)< 1, так что выполнено и 1).

б) Эргодический стационарный канал свя-
з и. Пусть канал связи стационарен, т. е. если на вход канала
подается стационарный процесс & = 0, +1,...}, то процесс
{{%ь, г)й), &=0, ±1,...}, где {ла} — процесс на выходе, также
стационарен. (Здесь нам удобно рассматривать процессы, за-
данные для всех целочисленных моментов времени. В том слу-
чае, когда канал связи имеет конечную память т, стационар-
ным будет процесс {(|й, щ), к^т), если{£й, &=1, 2,...} —
стационарен.) Будем называть канал связи зргодическим,
если процесс {(£й, г|й), & = 0, ±1, ±2,...} эргодичен, каков бы
ни был эргодический процесс {|й, /г = 0, ±1, ±2,...}. Эргоди-
ческой пропускной способностью эргодического канала связи
будем называть

эир/({£„}, {Лп}).

где супремум берется по всем эргодический Х-значным про-
цессам {!„, п = 0, ±1, ±2,.. . )

Лемма 2. Пусть канал связи эргодичен и {£п, п =
= 0, ±1, ±2,...}.— эргодический процесс. Тогда для всех
е>0 и 6>0 существует такое па, что для п~>п0 можно указать
такие множества ХпсХп, У„с:Уп, \^п^ХпХУп, что

1) ^2т(Хп)^п(Н({1п})+8), ^2т(¥п)^п(Н({цп}+б)),
1оё2т (№„) (Я({(£„, п„)}) +6),